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