#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?

Source