LIPIcs.FUN.2021.16.pdf
- Filesize: 333 kB
- 9 pages
Document
Efficient Algorithm for Multiplication of Numbers in Zeckendorf Representation
Author
-
Part of:
Volume:
10th International Conference on Fun with Algorithms (FUN 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-09-16
Cite AsGet 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
https://doi.org/10.4230/LIPIcs.FUN.2021.16
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.
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)
0PDF Downloads
References
-
Connor Ahlbach, Jeremy Usatine, Christiane Frougny, and Nicholas Pippenger. Efficient algorithms for Zeckendorf arithmetic. The Fibonacci Quarterly, 51(3):249-255, 2013.
-
Alberto Apostolico and Aviezri S. Fraenkel. Robust transmission of unbounded strings using Fibonacci representations. IEEE Transactions on Information Theory, 33(2):238-245, 1987.
-
George Bergman. A number system with an irrational base. Mathematics Magazine, 31(2):98-110, 1957.
-
Peter Fenwick. Zeckendorf integer arithmetic. Fibonacci Quarterly, 41:405-413, 2003.
-
H.T. Freitag and G.M. Phillips. Elements of Zeckendorf Arithmetic, pages 129-132. Springer Netherlands, Dordrecht, 1998.
-
Verner E. Hoggatt, Jr. Fibonacci and Lucas Numbers. Houghton Mifflin Company, 1969.
-
Donald E. Knuth. The Art of Computer Programming, volume 1. Addison-Wesley, 1968.
-
Donald E. Knuth. Fibonacci multiplication. Applied Mathematics Letters, 1(2):III-VI, 1988.
-
Arnold Schönhage and Volker Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7:281-292, 1971.
-
Garry J. Tee. Russian peasant multiplication and Egyptian division in Zeckendorf arithmetic. Australian Mathematical Society Gazette, 30(5):267-276, 2003.
-
Edouard Zeckendorf. A generalized Fibonacci numeration. The Fibonacci Quarterly, 10(4):365-372, 1972.
-
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.