Compute the product a * b² * c³ ... efficiently

Question

What is the most efficient way to compute the product

a¹ b² c³ d⁴ e⁵ ...

assuming that squaring costs about half as much as multiplication? The number of operands is less than 100.

Is there a simple algorithm also for the case that the multiplication time is proportional to the square of operand length (as with java.math.BigInteger)?

---

The first (and only) answer is perfect w.r.t. the number of operations.

Funnily enough, when applied to sizable BigIntegers, this part doesn't matter at all. Even computing abbcccddddeeeee without any optimizations takes about the same time.

Most of the time gets spent in the final multiplication (BigInteger implements none of the smarter algorithms like Karatsuba, Toom–Cook, or FFT, so the time is quadratic). What's important is assuring that the intermediate multiplicands are about the same size, i.e., given numbers p, q, r, s of about the same size, computing (pq) (rs) is usually faster than ((pq) r) s. The speed ratio seems to be about 1:2 for some dozens of operands.

Update

In Java 8, there are both Karatsuba and Toom–Cook multiplications in BigInteger.

Answer 1

I absolutely don't know if this is the optimal approach (although I think it is asymptotically optimal), but you can do it all in O(N) multiplications. You group the arguments of a * b^2 * c^3 like this: c * (c*b) * (c*b*a). In pseudocode:

result = 1
accum = 1
for i in 0 .. arguments:
  accum = accum * arg[n-i]
  result = result * accum

I think it is asymptotically optimal, because you have to use N-1 multiplications just to multiply N input arguments.