Hacker News Reader

Comment by svat | Hacker News Reader

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?

View on HN

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.

> 1/999999999999999999999998999999999999999999999999

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

Reply on news.ycombinator.com