##
**
Addition Chains Meet Postage Stamps: Reducing the Number of Multiplications
**

###
Jukka Kohonen and Jukka Corander

Department of Mathematics and Statistics

P. O. Box 68

FI-00014 University of Helsinki

Finland

**Abstract:**

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, ... , *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.

**
Full version: pdf,
dvi,
ps,
latex
**

(Concerned with sequences
A001212
A234941.)

Received October 24 2013;
revised version received February 3 2014.
Published in *Journal of Integer Sequences*, February 15 2014.

Return to
**Journal of Integer Sequences home page**