A word of warning.

[ciphergoth]

You can't make multiplying together a big heap of bignums big-O faster by reordering the order in which you do the multiplies, unless you use a big-O-fast multiply. The cost of multiplying together a_1 ... a_n will be roughly

O(\sum_{i < j} log(a_i)log(a_j))

no matter what you try.

Suppose we want to find abc, and we do it by calculating (ab)c. Finding ab using naive multiplication will take time proportional to log(a)log(b), and then finding (ab)c will take log(ab)log(c). Total time

log(a) log(b) + log(ab)log(c) = log(a)log(b) + (log(a) + log(b))log(c)
= log(a) log(b) + log(a)log(c) + log(b)log(c)

Clearly, this is the same time as you'd get if you found it by calculating a(bc) or (ac)b.

To prove the general case by induction: partition the sequence A into two non-empty subsequences, X = x_0 .. x_m and Y = y_0 ... y_n, such that the final multiply we do is (\Pi X) (\Pi Y). The cost of finding (\Pi X) is \sum_{i < j} log(x_i)log(x_j) and similarly for (\Pi Y). Then the cost of the final multiply is log(\Pi X)log(\Pi Y) = (\sum log(x_i))(\sum log(y_j)) = \sum log(x_i) log(y_j) . In other words, the total cost of finding \Pi A by this method is the sum of the pairwise products of the logs of the numbers inside X and Y, plus the sum of the pairwise products of the logs of the numbers across X and Y - ie, the sum of the pairwise products of the logs of all numbers in A.

This is probably a well known result in bignum math, but I only worked this out after about two hard days trying such a strategy while labouring under a fatal misconception...

Update However, it turns out that gmp uses big-O-faster multiplication once numbers get to above 30 limbs or so (ie about 1000 bits). So it is worth trying to arrange for the numbers you multiply to be about the same size as each other - just not nearly as much worth it as I thought...

Comments

[soleklypse.livejournal.com]

Reminds me of when I learned the hard way why the CYK algorithm was so brilliant (namely by trying and failing to come up with something better or even as good on my own). I'm so proud to say that I've actually written a program that runs in exponential time without meaning to.

[deliberateblank.livejournal.com]

I once wrote a program which was *supposed* to take exponential time, but ended up taking a few hours rather than 15 seconds on the sample data set because I'd abstracted too much: the bottom level was a function which did a single multi-dimensional array store, in the days when compilers didn't inline (386-25).

(OTOH since I'd written it top-down, inlining wouldn't have helped anyway.)

[ex-meta.livejournal.com]

I'd just like to point out that you can do stuff like

Σ_{i < j} log(a_i)log(a_j)

on the web these days.

[ciphergoth.livejournal.com]

Cool! And without using MathML too...

[valkyriekaren.livejournal.com]

I clicked because I thought 'bignum' sounded rude. I'm very disappointed now :(

[pavlos.livejournal.com]

I also think it sounds rude.

Well, yes, obviously...

[pavlos.livejournal.com]

Just kidding. I woudn't say your result is obvious but if you asked me to take an intuitive guess I would probably guess the order does not matter. You still have to multiply each digit with each other. Looking at the sequence:

log(a₁) * log(a₂) +
(log(a₁) + log(a₂)) * log(a₃) +
... +
(log(a₁) + log(a₂) + ... + log(a_n-1)) * log(a_n)

I don't readily see something that suggests permuting the a_i terms would change the sum.

What I'm trying to say is by what line of thought did you guess that permuting the numbers might help? Your thought might apply in some other context.

Re: Well, yes, obviously...

[ciphergoth.livejournal.com]

I used log(ab) (ie log(a) + log(b)) as my estimate of the cost. That led me to believe that calculating (ab)(cd) would be much faster than calculating ((ab)c)d.

Consider the classic dynamic programming example of reordering matrix multiplication for potentially enormous speedups (eg http://www.ics.uci.edu/~dan/class/161/notes/6/Dynamic.html) - that's where a strategy like this works.