Efficient Algorithms for Zeckendorf Arithmetic
Connor Ahlbach, Jeremy Usatine, Christiane Frougny, Nicholas J. Pippenger · The Fibonacci Quarterly · 2013
We study the problem of addition and subtraction using the Zeckendorf representation of integers. We show that both operations can be performed in linear time; in fact they can be performed by combinational logic networks with linear size and logarithmic depth. The implications of these results for multiplication, division and square-root extraction are also discussed.