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.

Supinator

Looks like reasonable interview question... Basic solution (not optimal) would be to simply compute powers of each member individually (log2(Power) of multiplications) and multiply results... – Bremser

There's an O(N log(N)^2) algorithm to do this (where N is the size of the final number). But you'll need to go beyond java.math.BigInteger to achieve it. – Dim

What is the type of operands? int? – Myxomycete

@Adam: Actually, the operands are BigIntegers, but currently I don't know how big. – Supinator

BigInteger implements none of the smarter algorithms like Karatsuba, Toom–Cook, or FFT, so the time is quadratic what implementation of java.math.BigInteger does this refer/apply to? – Capsize

@Capsize Updated.... it wasn't there in some ancient times (I don't know the history). – Supinator

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.

Megrims

Looks like this will run in about O(N^2) time. Which does appear to be good enough for the OP. +1 That said, it's not asymptotically optimal since it can be done in O(N log(N)^2) albeit using very difficult to implement algorithms. – Dim

With his current pseudocode in place, it runs in O(n) time. His code caches previous multiplications, thus doing only 2*n multiplications. All if n is the number of input arguments. – Empanel

@Sebastian Multiplication on BigInteger is not constant time. – Dim

Ahh that makes sense. Didn't realize that it was a restriction. – Empanel

Yeah, it gets a lot of people. For java's BigInteger, it can be as slow as O(N^2) to the operand sizes. – Dim

@Mysticial: Sure, you're right with the multiplication time, but it sort of misses my question. This solution runs in a linear number of multiplications, the other problem is that each multiplication takes quadratic time. You can't say the time is O(n**2) (using BigInteger or better using some crazy algorithm) as there are two inputs: the size of a number and the number of terms. – Supinator

@Supinator Oh ok. It wasn't clear from the question whether you were after run-time or # of multiplications. I assumed the former because that's what people usually care about. Sorry about that. The complexities that I've given in the comments here and on the question are simplified as there are indeed two inputs. But regardless of how the inputs are skewed, the best known algorithm is going to be within a logarithmic factor of O(N log(N)^2). If you only had two terms or a small fixed number of terms, it would actually be just O(N log(N)). – Dim

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.)

Capsize