# 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$$.
##### MSC:
 11B39 Fibonacci and Lucas numbers and polynomials and generalizations 11B75 Other combinatorial number theory 11Y16 Number-theoretic algorithms; complexity