[HN Gopher] Magical Fibonacci Formulae
___________________________________________________________________
Magical Fibonacci Formulae
Author : alexmolas
Score : 126 points
Date : 2023-12-11 10:05 UTC (12 hours ago)
(HTM) web link (orlp.net)
(TXT) w3m dump (orlp.net)
| asicsp wrote:
| 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)_
| wodow wrote:
| Found at https://blog.paulhankin.net/fibonacci/
| asicsp wrote:
| Thanks. There's a follow up at
| https://blog.paulhankin.net/fibonacci2/
| toth wrote:
| 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.
| cbolton wrote:
| 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.
| andrewla wrote:
| 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).
| marschot wrote:
| 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).
| andrewla wrote:
| 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).
| tromp wrote:
| > 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
| nh23423fefe wrote:
| f = 0:1:zipWith (+) f (tail f)
| lapinot wrote:
| This article _is about_ the cute generating function trick. Not
| exactly sure why you 're showcasing the usual recursive
| fibonacci in haskell.
| svat wrote:
| 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?
| toth wrote:
| 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.
| crdrost wrote:
| 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 > ph^{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.
| a1369209993 wrote:
| > 1/999999999999999999999998999999999999999999999999
|
| For anyone who only has floating-point handy, try `1.0/9899`
| for a faster-to-break-down but still illustrative example.
| Coder1996 wrote:
| 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!
| brudgers wrote:
| 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.
| pbsd wrote:
| 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.
___________________________________________________________________
(page generated 2023-12-11 23:01 UTC)