4 ms·

I mean if you want to have the value as a float I reckon the closed form will suit you just fine. You can try to do it with arbitrary precision integers, but o

I mean if you want to have the value as a float I reckon the closed form will suit you just fine. You can try to do it with arbitrary precision integers, but obviously the runtime can't be faster than the size of the answer, which technically makes it linear again. It can be quite fast though. I especially like Julia for this. 1) because you can just tell it to use arbitrary precision ints and 2) because you can write a power function that works for everything, floats, ints, matrices with arbitrary precision integers. Which gives one of my favourite one-liners: fib(n) = ((BigInt [1 1; 1 0])^n)[2,1] Last time I checked a manual implementation of exponentiation through squaring is just as fast as the native one. If I recall correctly the 10^9th fibonacci number is a few hundred megabytes, beyond that points things get a bit tricky.

Someone 3y ago
> If I recall correctly the 10^9th fibonacci number is a few hundred megabytes, It’s easy to prove that fib(n) < 2^n (If you need a hint: use induction), so it should be less than 10⁹ bits, or 128 megabytes. And that bound isn’t tight. A tighter one is 2log(phi) bits per step. That’s slightly less than 0.7, so that would make it less than 90 megabytes.
- contravariant 3y ago
  I may have remembered its size as an ASCII string.
pfdietz 3y ago
> You can try to do it with arbitrary precision integers, but obviously the runtime can't be faster than the size of the answer, which technically makes it linear again. The time will be dominated by the time to multiply integers in the final stage of the repeated squaring, which is superlinear in the number of bits. (1) (1) for fixed word size. One might instead argue it's a function of the number of words (# of bits/word size) and that the word size must eventually increase as integers get larger, asymptotically.

Someone 3y ago

> If I recall correctly the 10^9th fibonacci number is a few hundred megabytes, It’s easy to prove that fib(n) < 2^n (If you need a hint: use induction), so it should be less than 10⁹ bits, or 128 megabytes. And that bound isn’t tight. A tighter one is 2log(phi) bits per step. That’s slightly less than 0.7, so that would make it less than 90 megabytes.

contravariant 3y ago
I may have remembered its size as an ASCII string.

pfdietz 3y ago

> You can try to do it with arbitrary precision integers, but obviously the runtime can't be faster than the size of the answer, which technically makes it linear again. The time will be dominated by the time to multiply integers in the final stage of the repeated squaring, which is superlinear in the number of bits. (1) (1) for fixed word size. One might instead argue it's a function of the number of words (# of bits/word size) and that the word size must eventually increase as integers get larger, asymptotically.