Efficient Algorithms for Zeckendorf Arithmetic

• Published in 2012
• Added on 2015-02-16

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

• http://arxiv.org/abs/1207.4497
• http://arxiv.org/pdf/1207.4497v1

Other information

BibTeX entry

@article{Ahlbach2012,
	key = {Ahlbach2012},
	type = {article},
	title = {Efficient Algorithms for Zeckendorf Arithmetic},
	author = {Ahlbach, Connor and Usatine, Jeremy and Pippenger, Nicholas},
	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.},
	comment = {},
	date_added = {2015-02-16},
	date_published = {2012-07-01},
	urls = {http://arxiv.org/abs/1207.4497,http://arxiv.org/pdf/1207.4497v1},
	collections = {Easily explained,Fun maths facts,Integerology},
	month = {jul},
	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}
}