Document Open Access Logo

Efficient Algorithm for Multiplication of Numbers in Zeckendorf Representation

Author Tomasz Idziaszek

PDF

File

Thumbnail PDF
PDF
LIPIcs.FUN.2021.16.pdf
  • Filesize: 333 kB
  • 9 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • Fibonacci numbers
  • Zeckendorf representation
  • multiplication algorithm
  • Fast Fourier Transform
  • golden ratio numeral system
  • Lucas numbers

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

In the Zeckendorf representation an integer is expressed as a sum of Fibonacci numbers in which no two are consecutive. We show O(n log n) algorithm for multiplication of two n-digit numbers in Zeckendorf representation.
For this purpose we investigate a relationship between the numeral system using Zeckendorf representations and the golden ratio numeral system. We also show O(n) algorithms for converting numbers between these systems.

Cite As Get BibTex

Tomasz Idziaszek. Efficient Algorithm for Multiplication of Numbers in Zeckendorf Representation. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 16:1-16:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FUN.2021.16

Author Details

Tomasz Idziaszek
  • Independent Researcher, Poland

References

  1. Connor Ahlbach, Jeremy Usatine, Christiane Frougny, and Nicholas Pippenger. Efficient algorithms for Zeckendorf arithmetic. The Fibonacci Quarterly, 51(3):249-255, 2013. Google Scholar
  2. Alberto Apostolico and Aviezri S. Fraenkel. Robust transmission of unbounded strings using Fibonacci representations. IEEE Transactions on Information Theory, 33(2):238-245, 1987. Google Scholar
  3. George Bergman. A number system with an irrational base. Mathematics Magazine, 31(2):98-110, 1957. Google Scholar
  4. Peter Fenwick. Zeckendorf integer arithmetic. Fibonacci Quarterly, 41:405-413, 2003. Google Scholar
  5. H.T. Freitag and G.M. Phillips. Elements of Zeckendorf Arithmetic, pages 129-132. Springer Netherlands, Dordrecht, 1998. Google Scholar
  6. Verner E. Hoggatt, Jr. Fibonacci and Lucas Numbers. Houghton Mifflin Company, 1969. Google Scholar
  7. Donald E. Knuth. The Art of Computer Programming, volume 1. Addison-Wesley, 1968. Google Scholar
  8. Donald E. Knuth. Fibonacci multiplication. Applied Mathematics Letters, 1(2):III-VI, 1988. Google Scholar
  9. Arnold Schönhage and Volker Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7:281-292, 1971. Google Scholar
  10. Garry J. Tee. Russian peasant multiplication and Egyptian division in Zeckendorf arithmetic. Australian Mathematical Society Gazette, 30(5):267-276, 2003. Google Scholar
  11. Edouard Zeckendorf. A generalized Fibonacci numeration. The Fibonacci Quarterly, 10(4):365-372, 1972. Google Scholar
  12. Edouard Zeckendorf. Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. Roy. Sci. Liège, 41:179-182, 1972. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact