4 ms·

Love this! Remember a thread from years ago on 1/999999999999999999999998999999999999999999999999 giving the Fibonacci numbers (https://news.ycombinator.com/ite

by svat 3y ago

Love this! Remember a thread from years ago on 1/999999999999999999999998999999999999999999999999 giving the Fibonacci numbers (https://news.ycombinator.com/item?id=9815839 https://news.ycombinator.com/item?id=9815839 — was even linked from https://kottke.org/15/07/fibonacci-sequence-hidden-in-ordinary-division-problem 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 3y ago
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 3y ago
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.
a1369209993 3y ago
> 1/999999999999999999999998999999999999999999999999 For anyone who only has floating-point handy, try `1.0/9899` for a faster-to-break-down but still illustrative example.

by svat 3y ago

toth 3y ago

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 3y ago

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.

a1369209993 3y ago

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