Interesting Esoterica

Efficient Algorithms for Zeckendorf Arithmetic

Article by Ahlbach, Connor and Usatine, Jeremy and Pippenger, Nicholas
  • Published in 2012
  • Added on
In the collection
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.

Links


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}
}