Geodesic
Addition chains meet postage stamps: reducing the number of multiplications
Journal of integer sequences, Tome 17 (2014) no. 3.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: We introduce stamp chains. A stamp chain is a finite set of integers that is both an addition chain and an additive 2-basis, i.e., a solution to the postage stamp problem. We provide a simple method for converting known postage stamp solutions of length $k$ into stamp chains of length $k + 1$. Using stamp chains, we construct an algorithm that computes $u(x_{i})$ for $i = 1, \dots , n$ in less than $n - 1$ multiplications, if $u$ is a function that can be computed at zero cost, and if there exists another zero-cost function $v$ such that $v(a, b) = u(ab)$. This can substantially reduce the computational cost of repeated multiplication, as illustrated by application examples related to matrix multiplication and data clustering using subset convolution. In addition, we report the extremal postage stamp solutions of length $k = 24$.
Classification : 11B13
Keywords: additive basis, addition chain, matrix multiplication, subset convolution 
@article{JIS_2014__17_3_a5,
     author = {Kohonen, Jukka and Corander, Jukka},
     title = {Addition chains meet postage stamps: reducing the number of multiplications},
     journal = {Journal of integer sequences},
     publisher = {mathdoc},
     volume = {17},
     number = {3},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JIS_2014__17_3_a5/}
}
TY  - JOUR
AU  - Kohonen, Jukka
AU  - Corander, Jukka
TI  - Addition chains meet postage stamps: reducing the number of multiplications
JO  - Journal of integer sequences
PY  - 2014
VL  - 17
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JIS_2014__17_3_a5/
LA  - en
ID  - JIS_2014__17_3_a5
ER  - 
%0 Journal Article
%A Kohonen, Jukka
%A Corander, Jukka
%T Addition chains meet postage stamps: reducing the number of multiplications
%J Journal of integer sequences
%D 2014
%V 17
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JIS_2014__17_3_a5/
%G en
%F JIS_2014__17_3_a5
Kohonen, Jukka; Corander, Jukka. Addition chains meet postage stamps: reducing the number of multiplications. Journal of integer sequences, Tome 17 (2014) no. 3. http://geodesic.mathdoc.fr/item/JIS_2014__17_3_a5/