Efficient algorithms for Zeckendorf arithmetic

MaRDI QIDQ2868803zbMATH OpenFDO

Authors Connor Ahlbach, Jeremy Usatine, Christiane Frougny, Nicholas Pippenger

Publication date 19 December 2013

Published in The Fibonacci Quarterly (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.4497, http://fq.math.ca/Abstracts/51-3/ahlbach.pdf

Mathematics Subject Classification ID

Other number representations (11A67) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

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.

Recommendations

• Zeckendorf arithmetic for Lucas numbers
• Efficient algorithm for multiplication of numbers in Zeckendorf representation
• scientific article; zbMATH DE number 775622
• scientific article; zbMATH DE number 4134046
• scientific article; zbMATH DE number 2124021

Cited in

(15)

• A Macsyma implementation of Zeilberger's fast algorithm
• Ostrowski numeration systems, addition, and finite automata
• On the complexity of Fibonacci coding
• The arithmetic of recursively run-length compressed natural numbers
• scientific article; zbMATH DE number 4132091 (Why is no real title available?)
• Decision algorithms for Fibonacci-automatic words. I: Basic results.
• scientific article; zbMATH DE number 1222520 (Why is no real title available?)
• scientific article; zbMATH DE number 2096522 (Why is no real title available?)
• scientific article; zbMATH DE number 2124021 (Why is no real title available?)
• scientific article; zbMATH DE number 775622 (Why is no real title available?)
• Zeckendorf arithmetic for Lucas numbers
• Fast LCF-Style Proof Reconstruction for Z3
• A Fibonacci analogue of the two’s complement numeration system
• Efficient algorithm for multiplication of numbers in Zeckendorf representation
• Canonical Zeckendorf normalization and sharp iteration depth of the Berstel adder

This page was built for publication: Efficient algorithms for Zeckendorf arithmetic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2868803)