-1

Possible Duplicate:
nth fibonacci number in sublinear time

I was creating a program which is related to the stair problem, i.e you have n stairs and the player can climb on the stairs using them one by one or skipping one ...

Now to solve this problem I needed nth (n+1)th term for the Fibonacci for n number of stairs, but the problem is my input range is 1 ≤ n ≤ 1000000.

And for that much greater value of n if I use the loop based method or recursion to calculate the Fibonacci the method takes very much time and space. That I do not have.

So please can you tell me some method in the Java or C to handle Fibonacci series up to that range with correct output?

Note: Please I do not need any solution which has recursion or loop.

Community
  • 1
  • 1
Aayush Rana
  • 1,303
  • 1
  • 12
  • 19
  • 1
    You need some form of recursion or loop, but you can do it in `O(log n)` steps. Is that good enough? – Daniel Fischer Feb 04 '13 at 14:59
  • 5
    It's trivial, select your favourite closed form for `Fn`, perhaps start reading here: http://mathworld.wolfram.com/FibonacciNumber.html – High Performance Mark Feb 04 '13 at 15:01
  • 2
    Note that Fn(1,000,000) is ~ e^(480,400) ... a very large number. Take care not to hit overflow problems. – Mikeb Feb 04 '13 at 15:05
  • 3
    @HighPerformanceMark While closed form is neat mathematically, when it comes to computing it is also `O(logN)` because it requires invoking exponent (which is O(logN) AFAIK), and is very numerically unstable because it involves real numebrs which are approximated using floating points (or fixed point - it will still be an approximation) – amit Feb 04 '13 at 15:08
  • It's very simple... just tell me (n-1)th & (n-2)th terms ;) – anishsane Feb 04 '13 at 15:10
  • 2
    Calculating the 1000000th value using a loop take 34 seconds in Java using BigInteger on my machine. If you include the time it takes to write and test the program, this will be the fastest in total. i.e. one minute ;) – Peter Lawrey Feb 04 '13 at 15:13
  • @anishsane and Daniel the recursive algo is quite expensive by performance .... in this case it would show an Stack overflow error – Aayush Rana Feb 07 '13 at 12:42

1 Answers1

1

Look at the following page, maybe it will help: https://www.nayuki.io/page/fast-fibonacci-algorithms

For me their Java example managed to calculate 1000000th Fibonacci number. It is 208988 digits long.

Nayuki
  • 17,911
  • 6
  • 53
  • 80
Mikhail Vladimirov
  • 13,572
  • 1
  • 38
  • 40