zbMATH — the first resource for mathematics

Faster multiplication of medium large numbers via the Zeckendorf representation. (English) Zbl 0826.11011
The Fibonacci numbers of degree \(r\) are defined by \(F_0^{(r)} =0\), \(F_1^{(r)} =1\), \(F_j^{(r)}= 2^{j-2}\), \(j=2,3, \dots, r-1\), \(F_i^{(r)}= F_{i-1}^{(r)}+ F_{i-2}^{(r)}+ \cdots+ F_{i- r}^{(r)}\), \(i\geq r\). Each nonnegative integer \(N\) has the following unique Zeckendorf representation \(N= \alpha_2 F_2^{(r)}+ \alpha_3 F_3^{(r)}+ \cdots+ \alpha_j F_j^{(r)}\) where \(\alpha_i\in \{0, 1\}\) and no \(r\) consecutive \(\alpha\)’s are 1. This paper compares several algorithms for integer multiplication and shows that medium sized numbers can be multiplied on average more quickly using the Zeckendorf representation with \(r=4\).
11B39 Fibonacci and Lucas numbers and polynomials and generalizations
11B75 Other combinatorial number theory
11Y16 Number-theoretic algorithms; complexity