  We introduce stamp chains. A stamp chain is a finite integer sequence 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.
