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.

Answer 2

As mentioned in the Oct 26 '12 edit:
With multiplication time superlinear in the size of the operands, it would be of advantage to keep the size of the operands for long operations similar (especially if the only Toom-Cook available was toom-2 (Karatsuba)). If not going for a full optimisation, putting operands in a queue that allows popping them in order of increasing (significant) length looks a decent shot from the hip.
Then again, there are special cases: 0, powers of 2, multiplications where one factor is (otherwise) "trivial" ("long-by-single-digit multiplication", linear in sum of factor lengths).
And squaring is simpler/faster than general multiplication (question suggests assuming ½), which would suggest the following strategy:

• in a pre-processing step, count trailing zeroes weighted by exponent
  result 0 if encountering a 0
• remove trailing zeroes, discard resulting values of 1
  result 1 if no values left
• find and combine values occurring more than once
• set up a queue allowing extraction of the "shortest" number. For each pair (number, exponent), insert the factors exponentiation by squaring would multiply
• optional: combine "trivial factors" (see above) and re-insert
  Not sure how to go about this. Say factors of length 12 where trivial, and initial factors are of length 1, 2, …, 10, 11, 12, …, n. Optimally, you combine 1+10, 2+9, … for 7 trivial factors from 12. Combining shortest gives 3, 6, 9, 12 for 8 from 12
• extract the shortest pair of factors, multiply and re-insert
  once there is just one number, the result is that with the zeroes from the first step tacked on

(If factorisation was cheap, it would have to go on pretty early to get most from cheap squaring.)