The solution of the problem was on the form
fibonacci(n+1) % m
The problem was that the sequence grows quite fast and overflows an integer.
In order to avoid that, you don't compute the fibonacci sequence and then extract its module, instead you compute the sequence with the module already applied.
That way you'll never overflow.
fib_mod[K] = (fib_mod[K-1]+fib_mod[K-2]) % module
Now, you said that computing the sequence for each case was a waste and that you could memorize it. But as you need to compute it with different module, I thought that you'll need to store several sequences (by instance, for 2, 4, 32). That was a mistake on my part.
Because the modules are on the form 1<<m, so you could store only for the biggest one (m=30)
1 2
|
fib_m = fibonacci_module(30e3, 1<<30)
fib_m[steps]%module
| |
By the way,
http://www.cut-the-knot.org/arithmetic/algebra/FibonacciMatrix.shtml
> But that causes the problem, or at least makes it hard to see.
When you learn to indent, you learn that you are not to be trusted with it ;)
Use a program to do the indenting (by instance clang-format)