std::map seems to find elements which are not there

Question

So I've tried to create a simple program to calculate n-th fibonacci number mod 10^9+7 using the doubling formula with F[0]=0 and F[1]=1. and the program seems to work on my computer with compilers VS2010 and CodeBlocks with MinGW however testing my program on ideone returns 0 for every input. It seems that after the first iteration F.find(n) actually finds elements which shouldn't exist. Here's my code (in VS2010 I just changed the includes).

#include <bits/stdc++.h>

using namespace std;
std::map<unsigned long long,unsigned long long> F;
unsigned long long fib(unsigned long long n)
{
    if(n==-1) return 0; // Shifting index by 1
    if(n==0) return 1;
    if(n==1) return 1;
    if(F.find(n) != F.end()) return F[n]; // This seems to be the problem,
    else
    {
        if(n%2==0) //
        {
            F[n/2-1] = fib(n/2-1)%1000000007;
            F[n/2] = fib(n/2)%1000000007;
            return F[n] = (F[n/2-1]*F[n/2-1]+F[n/2]*F[n/2])%1000000007;
        }
        else
        {
            F[n/2] = fib(n/2)%1000000007;
            F[n/2+1] = fib(n/2+1)%1000000007;
            return F[n] = (F[n/2]*(2*F[n/2+1]-F[n/2]))%1000000007;
        }
    }
}
int main() {
    unsigned long long int broj; 
    cin >> broj; // input the number
    cout << fib(broj-1) << endl;
    return 0;
}

Just a note, but `F.find(n)` will already find the element. It seems wasteful to search for it again with `F[n]` when you've just obtained a perfectly good iterator to what you are looking for. — François Andrieux, Jun 04 '18 at 19:05
Unrelated to your problem, but please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) — Some programmer dude, Jun 04 '18 at 19:06
`if(n==-1) return 0;` is suspicious where `n` is `unsigned`. — François Andrieux, Jun 04 '18 at 19:07
And especially do not compound the problem with [Why is “using namespace std” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) . Including the entire standard library AND pulling it all into the global namespace is a bad, bad idea. — user4581301, Jun 04 '18 at 19:09
I do get all of that this is for educational purposes only to make the code prettier in general when really coding I never use #include and using namespace std; , the code can be made more efficient but it'll be less readable. — kingW3, Jun 04 '18 at 19:11

Slava · Accepted Answer · 2018-06-04T19:14:06.940

9

You have issue with expressions like this:

F[n/2-1] = fib(n/2-1)%1000000007;

as order of evaluation of operator[] on std::map is not defined it may call it before fib(n/2-1) and create an empty element there. You should store cached value in function where you calculate it.

Also calling std::map::operator[] with the same key as you used with std::map::find is wasteful.

Possible fix:

   auto p = F.emplace( n, 0 );
   if( p.second ) { 
       // element was not there
       // calculate and store at p.first->second
   }
   return p.first->second;

edited Jun 04 '18 at 19:14

answered Jun 04 '18 at 19:08

Slava

43,454
1
47
90

1

*You should store cached value in function where you calculate it.* or use `F.insert(std::make_pair(n/2-1, fib(n/2-1)%1000000007));` – R Sahu Jun 04 '18 at 19:11
@RSahu that would lead to double lookup – Slava Jun 04 '18 at 19:12
I didn't think so but I might be mistaken. – R Sahu Jun 04 '18 at 19:15
2

@RSahu one lookup this insert, another one inside `fib(n/2-1)` how second one can be avoided? – Slava Jun 04 '18 at 19:17
I see what you mean. – R Sahu Jun 04 '18 at 19:18

score 0 · Answer 2 · answered Jun 04 '18 at 20:02

Another possible fix is to add two temp variables lets say unsigned long long a,b; and change the lines

F[n/2-1] = fib(n/2-1)%1000000007;
F[n/2] = fib(n/2)%1000000007;

To

a = fib(n/2-1)%1000000007;
b = fib(n/2)%1000000007;
F[n/2-1] = a;
F[n/2] = b;

This way it doesn't matter whether map creates the element then assign value. It also can optimize the following line

return F[n] = (F[n/2-1]*F[n/2-1]+F[n/2]*F[n/2])%1000000007;

To avoid searching for F[n/2-1] and F[n/2] into

return F[n] = (a*a+b*b)%1000000007;

std::map seems to find elements which are not there

2 Answers2