A few days ago I wrote about Fibonacci numbers and certificates. As I pointed out in the article, there’s no need to certify Fibonacci numbers, but the point of the post was to illustrate the idea of a solution certificate in a simple context. Practical uses of certificates are more complicated.
This time I want to use Fibonacci numbers to illustrate space tradeoffs. The post on Fibonacci certificates imagined providing someone a pair (F, r) where F is a large Fibonacci number, and r is a certificate proving that F is indeed a Fibonacci number. The goal was to minimize the computational effort to verify F. All the recipient needed to do was compute
| 5F² − r² |.
The number F is a Fibonacci number if and only if this number equals 4. The problem with this scenario is that F and r are both large numbers. They require transmitting and storing a lot of bits.
A much more space-efficient approach would be to transmit the index of the Fibonacci number and have the user compute the number. The example in the certificate post was (12586269025, 28143753123). Since 12586269025 is the 50th Fibonacci number, I could communicate it to someone by simply transmitting the number 50. That saves space, but it puts more computational burden on the recipient.
Fibonacci numbers grow exponentially with index size, and so the size of the nth Fibonacci number in bits is proportional to n. But the number of bits in n is proportional to log n. When n is large, the difference is dramatic.
How many bits are in the 1,000,000th Fibonacci number? The nth Fibonacci number is φn/√5 rounded to the nearest integer, so the number of bits in the millionth Fibonacci number would be
log2 (φ1000000/√5) = 1000000 log2 φ − 0.5 log2 5
which is roughly 700,000. By contrast, one million is a 20 bit number. So transmitting “1000000” is far more efficient than transmitting the millionth Fibonacci number.
What does it take to compute the nth Fibonacci number? For small n, it’s fast and easy to compute the Fibonacci numbers up to n sequentially using the definition of the sequence. For large enough n, it would be faster to compute φn/√5. However, the former requires (extended) integer arithmetic, and the latter requires (extended) floating point arithmetic. It’s not clear where the crossover point would be where floating point would be more efficient. That’s the topic of the next post.