CODEWITHSUNDEEP
pythonpython-3.xfibonaccimodulo
Quiti
Quiti

Reputation: 132

Problems with modulo when calculating fibonacci

I'm trying to solve a problem that requires me to calculate Fibonacci numbers up to 10^18 mod 10^9+7. The online judge is saying that I get right answers on the small cases (where the modulo isn't required), but in larger cases I get wrong answers.

There is no problem with the algorithm otherwise, but the memoization aka saving the results into the dictionary table seems to have failed. I have no idea why.

luku = int(input())
table = {0:0, 1:1, 2:1}

def fib(num):

    if num in table:
        return table[num];

    if num % 2 == 0:
        puoli = num / 2;
        ans = (fib(puoli) * (2 * (fib(puoli + 1)) - fib(puoli))) % 1000000007;
        table[num] = ans;
        return ans;
    else:
        puoli = (num-1) / 2;
        ans = (fib(puoli + 1)*fib(puoli + 1) + fib(puoli)*fib(puoli)) % 1000000007;
        table[num] = ans;
        return ans;


print(fib(luku))

For example, with the input 54774730983471038 I'm getting 946469205 instead of the correct answer 795317107.

Upvotes: 1

Views: 119

Answers (1)

iBug
iBug

Reputation: 37297

Nothing wrong with memorizing.

Possibly to your surprise, the problem is that floating point precision (yeah, your numbers are truncated).

You should replace floating division operator / (single slash) with integer division operator // (double).

The following code, with the only fix mentioned above, works for me:

luku = int(input())
table = {0:0, 1:1, 2:1}

def fib(num):
    if num in table:
        return table[num];

    if num % 2 == 0:
        puoli = num // 2;
        ans = (fib(puoli) * (2 * (fib(puoli + 1)) - fib(puoli))) % 1000000007;
        table[num] = ans;
        return ans;
    else:
        puoli = (num-1) // 2;
        ans = (fib(puoli + 1)*fib(puoli + 1) + fib(puoli)*fib(puoli)) % 1000000007;
        table[num] = ans;
        return ans;


print(fib(luku))

See:

ibug@ubuntu:~ $ python3 t.py
54774730983471038
795317107

Upvotes: 3

Related Questions