Long number base conversion

[Eric Sosman]

[...]
If you know you want to convert the result to decimal (and perhaps
that you don't want to do much else with it), one thing you can do is
handle the trailing zeroes specially. As you're plowing along building
up 1 * 2 * 3 * ... you can remove all the 2's and 5's from each new
factor and count how many you've removed. Then at the end you'll have

You mean that in 11! * 12, the 12 becomes 6, and I add one to the number
of two's?

Almost. The 12 becomes 3 and you add *two* to the number of twos.

What about *25 which becomes *5, do I apply the rule again to get *1?

Yes. And when you get to *300 you accumulate two twos and two
fives and wind up with *3.

(I've just tried this, and unless I made a mistake (which is quite
likely), I found it difficult to measure the difference on 100000!, and
that's without doing the adjustments at the end.)

I neglected to say so, but I assumed you'd do the "casting out"
of twos and fives in ordinary integer arithmetic, before moving into
the big-number realm. Also, an operation to multiply a big-number by
an ordinary integer (rather than by a big-number whose value happens
to be "small") would probably be worth while.

 

[BartC]

On 11/27/2010 3:44 PM, BartC wrote:

[Calculating 1000000!]

I neglected to say so, but I assumed you'd do the "casting out"
of twos and fives in ordinary integer arithmetic, before moving into
the big-number realm. Also, an operation to multiply a big-number by
an ordinary integer (rather than by a big-number whose value happens
to be "small") would probably be worth while.

Actually there was a bug in my multiply routine which meant extra words of
zeros were being accumulated at the most significant end. So it could not
benefit from smaller multipliers.

Fixed that made things faster anyway (the calculation now takes 20 minutes,
using the simplest algorithms).

Casting out twos and fives would reduce the main calculation time by around
10% (I can't do the final adjustment because I don't have shift or power
routines yet; actually I don't yet have subtract or divide...).

Also, an operation to multiply a big-number by
an ordinary integer (rather than by a big-number whose value happens
to be "small") would probably be worth while.

About 5% according to a brief test (although still with a few overheads
associated with a multi-word multiplier).

 

[Mark Wooding]

Also, an operation to multiply a big-number by an ordinary integer
(rather than by a big-number whose value happens to be "small") would
probably be worth while.

No; that turns out not to be the right answer. The problem is that
multiplying bignum*fixnum is inherently O(k) in the length of the
bignum -- and this is all you're doing.

Instead, try to maximize the number of small multiplications you do.
Start with a stack, and maintain the invariant that items lower on the
stack are longer (in words). To push a new item:

* If the stack is empty, or the new item is shorter than the top item,
just go ahead and push.

* Otherwise, pop the top item and try again, pushing the product of
your original new item and the old top item.

To compute n!, start with an empty stack, push each number 2, 3, ..., n
using the above algorithm, and finally compute the product of the items
remaining in the stack.

If the result is going to be k bits (k is bounded below by a multiple of
n (log n - 1)) then the naive algorithm above does O(k^2) work (it's
essentially triangular). The stack trick always multiplies numbers of
the same sizes (until the endgame). This has two benefits: it reduces
the number of large multiplications you have to do (only one of the
largest size, two of half that size, and so on). It also lets you get
the benefit of cleverer multiplication algorithms.

Here's Karatsuba's trick. Suppose you have two numbers, (x B + y) and
(w B + z) and you want their product (here, B is some power of the base
you're working in, probably some convenient power of 2, chosen so that
x, y, w and z are all roughly the same size). Well, that's

x w B^2 + (x z + w y) B + y z

Now notice that (x + y)(w + z) - x w - y z = x z + w y: you can compute
the product using only three multiplications of numbers half the size
(and some addition and shifting). Messing with the carries is annoying,
so for smallish numbers (a few hundred bits or so) this isn't
worthwhile, but for large factorials it's a big win.

-- [mdw]