摘要：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.
关键词：Fibonacci numbers; Zeckendorf representation; multiplication algorithm; Fast Fourier Transform; golden ratio numeral system; Lucas numbers
