# Efficient Algorithms for Zeckendorf Arithmetic

• Published in 2012
In the collections
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.

### BibTeX entry

@article{Ahlbach2012,
abstract = {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.},
author = {Ahlbach, Connor and Usatine, Jeremy and Pippenger, Nicholas},
month = {jul},
title = {Efficient Algorithms for Zeckendorf Arithmetic},
url = {http://arxiv.org/abs/1207.4497 http://arxiv.org/pdf/1207.4497v1},
year = 2012,
archivePrefix = {arXiv},
eprint = {1207.4497},
primaryClass = {cs.DS},
urldate = {2015-02-16},
collections = {Easily explained,Fun maths facts,Integerology}
}