http://www.codewars.com/kata/53d40c1e2f13e331fc000c26/
Description:
The year is 1214. One night, Pope Innocent III awakens to find the the archangel Gabriel floating before him. Gabriel thunders to the pope:
Gather all of the learned men in Pisa, especially Leonardo Fibonacci. In order for the crusades in the holy lands to be successful, these men must calculate the millionth number in Fibonacci's recurrence. Fail to do this, and your armies will never reclaim the holy land. It is His will.
The angel then vanishes in an explosion of white light.
Pope Innocent III sits in his bed in awe. How much is a million? he thinks to himself. He never was very good at math.
He tries writing the number down, but because everyone in Europe is still using Roman numerals at this moment in history, he cannot represent this number. If he only knew about the invention of zero, it might make this sort of thing easier.
He decides to go back to bed. He consoles himself, The Lord would never challenge me thus; this must have been some deceit by the devil. A pretty horrendous nightmare, to be sure.
Pope Innocent III's armies would go on to conquer Constantinople (now Istanbul), but they would never reclaim the holy land as he desired.
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
Solution: O(log(n)) implementation of fibonacci using fast doubling
including negative fibonacci numbers handling
def fib(num):
if num >= 0:
return fib_helper(num)[0]
else:
return -fib_helper(-num)[0] if num %2 ==0 else fib_helper(-num)[0]
def fib_helper(num):
"Helper function for fibonacci()."
if num == 0:
return (0, 1)
elif num == 1:
return (1, 1)
else:
a, b = fib_helper(num // 2)
p = a * (2 * b - a)
q = b * b + a * a
return (p, q) if num % 2 == 0 else (q, p + q)
Another Solution by xcthulhu
def my_fib(n):
if n < 0: return (-1)**(n % 2 + 1) * fib(-n)
a,b,p,q = (1,0,0,1)
while n != 0:
if (n % 2) == 0:
(p,q) = (p * p + q * q, (2 * p + q) * q)
n /= 2
else:
(a,b) = ((b + a) * q + a * p, b * p + a * q)
n -= 1
return b
Yet Another Fast Solution with memoization
