Magical Fibonacci Formulae | Hacker News Reader

Magical Fibonacci Formulae

orlp.net

153 pointsalexmolas23 comments

Love this! Remember a thread from years ago on 1/999999999999999999999998999999999999999999999999 giving the Fibonacci numbers (https://news.ycombinator.com/item?id=9815839 — was even linked from https://kottke.org/15/07/fibonacci-sequence-hidden-in-ordina...) — but that trick (using a fixed "base", in the terminology of this post) eventually runs into "overflow" issues (of the mathematical kind, not actual computer arithmetic overflow), so the idea here of using a base that varies with n is a really cool one.

I think the post says b=3^n and b=2^{n+1} were "experimentally found" to be enough, which raises the question: can we say what's the smallest base that would work, for a given n?

I think what you need is something that is at least as large as the largest Fibonaci number you are going to compute. Since the Fibonnaci numbers grow as `phi^n` where `phi` is the golden ratio (~= 1.618) if you want to use something of the form `A*b^n` you need `b >= phi` and to pick A to make it work out for small `n`. So, if you want integer `b` then 2 is the smallest you can do. But you could also do `b=1.7` or something like `A*17^n/10^n` if you want to use only integers.

They discuss in the article that the key thing is for the next Fibonacci number to not overflow, so you need f(n+1) < b hence b > φ^{n+1}/√5.

So to calculate the best base for the n'th Fibonacci number, compute the (n+1)th Fibonacci number and then add one to that, should do the trick. (Whoops, stack is overflowing, whyyyyyy)

I'm assuming that if 2^n doesn't work it's only because you get a wrong result for n=0? Then 1+2^n should beat both of these. And the issue there seems to be unrelated to precision, it is just that the denominator 1 – b^-1 – b^-2 < 0, which requires b > phi at all times, but in that case I am surprised that 3^n works at n=0. But, if you want to stay above phi, maybe b := 1 + 13*n // 8*n wastes a bit less memory.

> 1/999999999999999999999998999999999999999999999999

For anyone who only has floating-point handy, try `1.0/9899` for a faster-to-break-down but still illustrative example.

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.

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.

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).

When you are ready to jump headfirst down the Fibonacci rabbit hole try The Fibonacci Quarterly:

https://www.fq.math.ca/

Published continuously since 1963.

See also: "An integer formula for Fibonacci numbers" (article link isn't working though) https://news.ycombinator.com/item?id=11560122 (297 points | April 24, 2016 | 56 comments)

Found at https://blog.paulhankin.net/fibonacci/

Thanks. There's a follow up at https://blog.paulhankin.net/fibonacci2/

This is one of those posts that stays with you for a few days... Really interesting even though it is ultimately very basic...

Can a number representing pi be done the same way? What about the golden ratio?

I bet a magic number exists for those like 998999. Interestingly, 1,000,000 - 998999 is just 1001. Which if done recursively and added to the prior iteration starts counting. 1.001, 1.002 and so on.

In a way it seems that only 0 and 1 really exist with everything being able to be represented between the two, essentially making infinity = 1

A different way to get a result like this is to observe that the nth Fibonacci number is obtainable as the coefficient of x in x^n mod (x^2-x-1) via the usual matrix exponentiation argument, apply Kronecker substitution, and compute pow(b, n, b**2-b-1)//b.

I remember having to prove Binet's formula[1] for a math class and then going back to my CS classes and asking why they never showed us that it existed. I'm not sure they knew it existed either

[1](https://orlp.net/blog/magical-fibonacci-formulae/#an-interlu...)

Thanks for sharing. Very interesting. Added the formula to my fibonacci number algos collection at https://github.com/alidasdan/fibonacci-number-algorithms . Though simple, the new formula runs much slower than even the linear-time algo.

So, you created a function to generate a number containing digits of the Fibonacci sequence, then you used the generated number to create another function to compute a zfibonacci sequence, and thus you eliminated a need for looping or recursion.

Cool!

> f=lambda n:(b:=2<<n)*n*b//(b*b-b-1)%b

> [f(n) for n in range(10)]

> [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Or in Haskell, without the cute generating function tricks:

take 10 $ let f a b = a : f b (a+b) in f 0 1

    f = 0:1:zipWith (+) f (tail f)

In Python is possible to do something quite similar, using itertools:

    from itertools import pairwise, chain

    def f(): yield from chain([0,1], map(sum, pairwise(f())))

There's a Joel Grus post discussing it: https://joelgrus.com/2015/07/07/haskell-style-fibonacci-in-p...

The introduction of pairwise in 3.10 made possible to write it more compactly, when compared to the version discussed by Joel.

This article is about the cute generating function trick. Not exactly sure why you're showcasing the usual recursive fibonacci in haskell.

Is this method faster?

Reply on news.ycombinator.com