Efficient Algorithms for Zeckendorf Arithmetic

Autor:	Ahlbach, Connor, Usatine, Jeremy, Pippenger, Nicholas
Rok vydání:	2012
Předmět:	Computer Science - Data Structures and Algorithms Mathematics - Combinatorics
Druh dokumentu:	Working Paper
Popis:	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: i+6 pp
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1207.4497 Zobrazit plný text záznamu View this record from Arxiv