A variable RADIX-2 r algorithm for single constant multiplication

In previous work, a fully predictable sub-linear runtime heuristic for the multiplication by a constant based on Radix-2 r arithmetic using a fixed radix was developed, called RADIX-2 r . In this paper, we introduce a new constant multiplication algorithm based also on Radix-2 r arithmetic but considering a variable radix. The new version is named RADIX-2 r -VAR. Using a variable radix allows to optimize the average number of additions in the constant multiplication since a larger search space is explored. The new RADIX-2 r -VAR recoding requires an average of 4.4% and 2.2% less additions than RADIX-2 r for 24 and 32 bits, respectively. The RADIX-2 r -VAR algorithm is combined with RADIX-2 r for more improvements of the average number of additions. An overall saving of 6.7% and 5.5% is obtained over RADIX-2 r for 24 and 32 bits, respectively.