2026-07-24T03:33:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12777 2024-03-06T10:49:09Z ddc:004 open_access

Efficient Algorithm for Multiplication of Numbers in Zeckendorf Representation Idziaszek, Tomasz Fibonacci numbers Zeckendorf representation multiplication algorithm Fast Fourier Transform golden ratio numeral system Lucas numbers 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tomasz Idziaszek 2020 Is Part Of LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2021.16 urn:nbn:de:0030-drops-127770 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.16 eng https://creativecommons.org/licenses/by/3.0/legalcode