The Millionth Fibonacci Kata

[houjunchen]

In this kata you will have to calculate fib(n) where:

fib(0) := 0
fib(1) := 1
fin(n + 2) := fib(n + 1) + fib(n)

Write an algorithm that can handle n where 1000000 ≤ n ≤ 1500000.

Your algorithm must output the exact integer answer, to full precision. Also, it must correctly handle negative numbers as input.

HINT I: Can you rearrange the equation fib(n + 2) = fib(n + 1) + fib(n) to find fib(n) if you already know fin(n + 1) and fib(n + 2)? Use this to reason what value fib has to have for negative values.

HINT II: See http://mitpress.mit.edu/sicp/chapter1/node15.html

---

計算費式數列，參數可為負數。

提示1：在已知 fin(n + 1) 與 fib(n + 2) 的情況下，透過重新排列 fib(n + 2) = fib(n + 1) + fib(n) 就可以推算出 n 為負數時的值。
提示2：http://mitpress.mit.edu/sicp/chapter1/node15.html (用矩陣公式解)。

https://www.codewars.com/kata/the-millionth-fibonacci-kata

[houjunchen]

Pass

[bucker]

Pass