Integers only, limit at -300k/300k for CPU limits on Google App Engine.
Wikipedia provides a nice description of Fibonacci numbers;
the algorithm is based on the matrix form
of Fibonacci numbers, in particular:
F2n-1 = F2n + F2n-1
F2n = (2Fn-1 + Fn)Fn
The implementation is very simple, yet blazing FAST and revolves around this Python function:
def fib(n, cache = {0:0, 1:1}):
if n not in cache:
if n % 2 == 0:
cache[n] = (2*fib(n//2-1) + fib(n//2)) * fib(n//2)
else:
cache[n] = fib((n+1)//2) ** 2 + fib(n//2) ** 2
return cache[n]
(for non-pythonic readers: cache is evaluated ONCE for the whole function and it doesn't reset
on every call, and // is the flooring division)
For NegaFibonacci numbers (Fibonacci numbers extended for negative indexes), I just follow
F-n = (-1)n+1Fn
I also implemented caching between sessions (via App Engine's memcache), but I decided against polling and saving EVERY number I calculate, since that would've slowed A LOT the calculation of small numbers, so in the end, I decided to cache only the numbers the user requested. I'm working on an archive with full source codes, but i need to clean up the code a bit (especially the Javascript part - GOD I hate Javascript).
Note to old browsers' users: if you have any problem regarding Javascript, let me know; you are still able to use the calculator by disabling it, but I wanna make the whole process as painless as possible - still, if you use IE3, you'll see <?xml version="1.0" encoding="utf-8"?> on top of the page, and I can't help that. Switch to Dillo, ELinks or another recent browser supporting XHTML. Also, I don't care about you.