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