Thread: Fibonacci sequence

1. Fibonacci sequence

Hi. Can somebody tell me where the solution is wrong?
The task: http://img338.imageshack.us/img338/8097/task.png
My solution: Ideone.com | Online C++ Compiler & Debugging Tool

PS. I use Fibonacci sequence to designate the number of combinations (2,3,5,8,13,21,34...)

2. This code is only 42 lines long, so you sould just post it here. Don't make us chase it.
I don't understand why you've involved a matrix or power function. It looks to me like all you have to do is to calculate the square of the Nth fibonacci number modulo 1000000007.
You aren't using your default arguments to the constructor so what's the point in having them?

3. I don't understand why you've involved a matrix or power function.
1. It calculates fib(n) mod 1000000007.
2. Calculates square and do the mod 1000000007.
3. Now my calculations look like this: ((fib(n) mod 1000000007)*(fib(n) mod 1000000007)) mod 1000000007

((fib(n) mod 1000000007)*(fib(n) mod 1000000007)) mod 1000000007 = (fib(n)*fib(n)) mod 1000000007

It looks to me like all you have to do is to calculate the square of the Nth fibonacci number modulo 1000000007
Exactly, you're right, but how I can implement it in the code?

4. Originally Posted by paut
((fib(n) mod 1000000007)*(fib(n) mod 1000000007)) mod 1000000007 = (fib(n)*fib(n)) mod 1000000007
Whilst that expansion is correct, the left hand side suffers less from arithmetic overflow than the right. It may be that you actually need to go the other direction, i.e. move the mod 1000000007 into the fib function, in order to prevent overflow.

It's hard to know what's wrong with your solution if you're using an online marking system that just gives correct/incorrect output.

Popular pages Recent additions