Velocity Reviews > Long number base conversion

# Long number base conversion

Eric Sosman
Guest
Posts: n/a

 11-27-2010
On 11/27/2010 3:44 PM, BartC wrote:
>
>
> "Eric Sosman" <(E-Mail Removed)> wrote in message
> news:icr452\$boe\$(E-Mail Removed)-september.org...
>> [...]
>> 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.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

BartC
Guest
Posts: n/a

 11-28-2010
"Eric Sosman" <(E-Mail Removed)> wrote in message
news:ics2k2\$snk\$(E-Mail Removed)-september.org...
> On 11/27/2010 3:44 PM, BartC wrote:

[Calculating 1000000!]

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

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

--
Bartc

Mark Wooding
Guest
Posts: n/a

 11-28-2010
Eric Sosman <(E-Mail Removed)> writes:

> 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,

* 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]

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post jared.grubb@gmail.com C++ 4 09-12-2008 08:27 AM veryhotsausage C++ 1 07-04-2008 05:41 PM chen li Ruby 6 01-23-2007 07:45 PM Daniel Rudy C Programming 5 09-20-2005 02:37 AM George Marsaglia C Programming 1 07-08-2003 05:16 PM