#1. Fibonacci Numbers, Quickly
(Back to course page.)
Link to slides · Link to recording
Prompts for discussion:
Zeckendorf showed that each non-negative integer has a unique representation as a sum of Fibonacci numbers in which no two consecutive Fibonacci numbers occur. This observation leads to a numeral system. A natural question for a numeral system is how can we perform arithmetic operations on numbers in such a system, and how fast can we do it.
In particular:
Can you add and subtract \(n\)-digit numbers in the Zeckendorf system in \(O(n)\) time, as fast as in the binary system?
Can you multiply \(n\)-digit numbers in the Zeckendorf system in \(O(n \log n)\) time, as fast as in the binary system?