Hacker News Reader

Comment by toth | Hacker News Reader

Very nice! Had never seen this trick.

One non-obvious aspect is that the function relies on using Python's big ints, even for pretty small values of n. You are calculating `2^(n(n+1))` for the numerator, so if n=8 you already get `2^72`, which you can't fit in a 64-bit int. This is even though the answer itself is very small: `F_8=21`.

This makes sense, because you are essentially packing all the previous Fibonnaci numbers into a bit string, so you need room for all of them without overlapping and that bit-string is going to necessarily be long.

View on HN

And since exponentation is logarithmic in the exponent, this algorithm is computing Fib(n) in O(log n) time. So while more compact than the matrix method or the field extension method or the doubling formula method, this reduces to the same complexity.

I'd venture to say that it is clear that we can't really do better than O(log n) just because the number of digits in Fib(n) is O(log n).

The number of bits in Fib(n) is O(n), not O(log n). Put differently, Fib(n) grows exponentially. To be precise, Fib(n) = (phi^n - (-phi)^(-n)) / sqrt(5). So the complexity to compute Fib(n) is O(n) time (or slower). And one algorithm that runs this fast is to compute the n-th power of [[1,1],[1,0]] (using repeated squaring and large integer arithmetic).

I stand corrected. I made the same mistake that I am attributing to others; to think that n-bit arithmetic operations are O(1) instead of O(n).

Indeed! I was trying in Julia and got [0, 1, 1, 2, 3, 5, 8, 0, 0, 0]. Had to use "big integers" to make it work past n=7:

  function f(n)
      b = big(2) << n
      return b^(n+1) ÷ (b^2-b-1) % b
  end

or for code golf:

  f(n;b=big(2)<<n)=b^(n+1)÷(b^2-b-1)%b

With "big" f.(1:10) gives the expected answer.

Reply on news.ycombinator.com