nth Fibonacci number in dynamic programming

Question

Every one know logic of Fibonacci series

Fib0 = 0
Fib1 = 1
Fibn = Fibn-1 + Fibn-2 , n > 1

my question is i have to calculate fib(n)%(100000000+7) and output should be according n

like for n=0 output 1

for n=5 output 5

for n=10 output 55

for n=100 output 24278230

and i successfully coded it also with tail recursion in scala

def fi( n : Int) : Long = { 
  def fib_tail( n: Int, a:Int, b:Int): Int = n match {
    case 0 => a 
    case _ => fib_tail( n-1, b, (a+b))
  }
  return fib_tail( n, 0, 1)
}


   l.map(x=> println(fi(x)%((math.pow(10, 8)).toInt +7  )))

it is working right for 0,1,5,10 but it is giving wrong output for 100 i want 24278230 for 100

any one give me some idea to get this output

Answer 1

My answer is a somewhat general solution for linear recurrence sequences. You would need some basic algebra knowledge in order to understand it completely.

Let we have a vector

and we multiply it with the matrix

We would receive:

Therefore, when we multiply the vector with this matrix we receive the next fibonacci number. But what would happen if we multiply the vector with T²?

In this way, we constructed the fibonacci number after the next one (the (n+3)-th one). Now what would we get if we start with the first two fibonacci numbers in this vector and multiply it with T^n-1?

So by multiplying our vector with the matrix T, raised to the (n-1)th power, we can get the n-th fibonacci number. We can compute T^n-1 in time O(log n) via exponentiation by squaring. And of course, we should do all our calculations by modulo 10⁸ + 7.

Here is a link of my implementation (in Java): http://pastie.org/8519742

This algorithm should work well and fast for all positive values of n up to 2¹⁰⁸.

Sample running time of the method (using the same time measurement as in Peter Lawrey's answer):

fib(1,000,000,000,000,000,000) is 8,465,404 took us 1022.8 to calculate
fib(100,000,000,000,000,000) is 60,687,801 took us 325.7 to calculate
fib(10,000,000,000,000,000) is 9,115,009 took us 247.2 to calculate
fib(1,000,000,000,000,000) is 8,361,917 took us 233.3 to calculate
fib(100,000,000,000,000) is 11,279,600 took us 218.3 to calculate
fib(10,000,000,000,000) is 72,758,000 took us 6027.7 to calculate
fib(1,000,000,000,000) is 82,461,898 took us 184.2 to calculate
fib(100,000,000,000) is 60,584,292 took us 180.4 to calculate
fib(10,000,000,000) is 68,453,509 took us 162.0 to calculate
fib(1,000,000,000) is 90,703,191 took us 145.4 to calculate
fib(100,000,000) is 21 took us 131.3 to calculate
fib(10,000,000) is 60,722,758 took us 112.0 to calculate
fib(1,000,000) is 72,117,251 took us 99.8 to calculate
fib(100,000) is 33,178,829 took us 92.3 to calculate
fib(10,000) is 49,520,320 took us 70.8 to calculate
fib(1,000) is 95,802,669 took us 60.1 to calculate
fib(100) is 24,278,230 took us 39.3 to calculate
fib(10) is 55 took us 27.0 to calculate
fib(1) is 1 took us 16.3 to calculate

However, with all that said, this is not the fastest algorithm for your problem. It is well known that the fibonacci numbers have periodical residues under some module. Quoting the wikipedia entry on fibonacci numbers:

It may be seen that if the members of the Fibonacci sequence are taken mod n, the resulting sequence must be periodic with period at most n²−1.

In other words, if you find this period (with for example, the tortoise and hare algorithm - linear complexity), you can also find the result of every fibonacci number modulo 10⁸+7.

Answer 2

Here is the fastest way I know for computing the fib%mod, but you only see a difference at about 1000+

public static void main(String[] args) {
    long mod = 100_000_007;
    for (int i = 100_000_000; i > 0; i /= 10) {
        long start = System.nanoTime();
        final long l = fibMod3(i, mod);
        long time = System.nanoTime() - start;
        System.out.printf("fib(%,d) %% %,d is %,d took %.1f us to calculate%n", i, mod, l, time / 1e3);
    }
}

// use a simple loop and % each time.
public static long fibMod(int n, long mod) {
    long a = 1, b = 1;
    if (n <= 2) return 1;
    while (n-- > 2) {
        long c = a + b;
        a = b;
        b = c % mod;
    }
    return b;
}

// mod is very expensive so only do this on every third iteration.
public static long fibMod3(int n, long mod) {
    long a = 1, b = 1;
    if (n <= 2) return 1;
    while (n > 5) {
        long c = a + b;
        a = b + c;
        b = (c + a) % mod;
        n -= 3;
    }
    while (n > 2) {
        long c = a + b;
        a = b;
        b = c;
        n--;
    }
    return b % mod;
}

prints

fib(100,000,000) % 100,000,007 is 21 took 546460.1 us to calculate
fib(10,000,000) % 100,000,007 is 60,722,758 took 54079.6 us to calculate
fib(1,000,000) % 100,000,007 is 72,117,251 took 5274.9 us to calculate
fib(100,000) % 100,000,007 is 33,178,829 took 506.0 us to calculate
fib(10,000) % 100,000,007 is 49,520,320 took 50.8 us to calculate
fib(1,000) % 100,000,007 is 95,802,669 took 5.2 us to calculate
fib(100) % 100,000,007 is 24,278,230 took 0.7 us to calculate
fib(10) % 100,000,007 is 55 took 0.3 us to calculate
fib(1) % 100,000,007 is 1 took 0.3 us to calculate

The fib(100) takes 0.7 micro-seconds as the code has been warmed up. If you loop in increasing size, it is not even compiled and takes about 3 micro-seconds.

Answer 3

I have coded it in C++, and it works well.

LL fi(int n, LL a, LL b) {
   if (n == 0) {
     return a;
  } else {
     return fi(n-1, b, (a+b) % 100000007);
   }
}

You should Mod here: fib_tail( n-1, b, (a+b) % MOD), else the result will be out of the range of Long.