Re: BigNum -- BigFrac

From: Paul Hsieh (qed_at_pobox.com)
Date: 12/31/03 

Date: 30 Dec 2003 19:37:15 -0800

Programmer Dude <Chris@Sonnack.com> wrote:
> Richard Heathfield wrote:
> >> ...and 2^(2^16) took over five hours (big number: 19789 digits)!
> >
> > Not quite sure what you're doing wrong there. My lib calculated
> > 2^(2^16) in 0.000 seconds (well, presumably just a /touch/ more
> > than that), and took 119.22 seconds to convert from base 256 to
> > base 10.
>
> Hmmm. I didn't realize I was *that* far from ideal.

Depends on what you mean by ideal. I ressurected an old bigInt
library I was playing with and managed to compute it (well actually I
computed 1 << 65536) in immeasurable time and convert it from base
4294967296 to base 10 in about 0.9 seconds. Of course I cheated and
used a divide-and-conquer mechanism rather than the more obvious
iterative algorithm (its interesting because I can't actually reduce
the number of divides -- but I can reduce the size of the numbers
being divided.)

> > So, er - how come it takes five hours?
>
> Very bad implementation? What do your power and multiply function
> look like (algorithmically)?

For multiply, a good method is to use a column digit by column digit
multiplier. It requires one carry digit register for the upper word
of the multiply, then an additional carry digit register for the
ripple carry of those digit pairs. The advantage of doing it this way
versus the classical public school method is that you don't have to
allocate space for a temporary row.

Power is done by successively squaring and taking those that
corresponds to bits in the exponent as part of the product. For
example:

    x ^ 13 = x ^ (8 + 4 + 1)
           = x^1 * x^4 * x^8
           = (x) * ((x^2)^2) * (((x^2)^2)^2)

You should notice the trivial values of x. For a binary base, that's
0, 1, 2, and any other power of 2. One way or another they can be
computed with some mathematical shortcut or other. If you have a
"lowest bit set on" function and bidirectional shifting, then you can
speed it up by pulling out the power of twos before computing the
result then shifting them back in after multiplying the number by the
exponent. 

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Relevant Pages

  • Re: Extracting Digits from a Number
    ... three digit numbers. ... The multiplier is 41 and the starting shift is 12. ... The idea is that division by a power of 2 is cheaper than a generic ...
    (comp.lang.c)
  • Re: power measure
    ... Power though, continues to be dissipated ... > voltage, during that period the instantaneous wattage of the device is ... but the circuit design ideas can be ... The basic multiplier circuit has been designed for you. ...
    (sci.electronics.misc)
  • Re: Turns ratio change
    ... I've changed my primary turns from 19 T to 15 T and changed secondary ... voltage- It's a 10 stage cockroft-walton multiplier. ... One thing I have done before is increase secondary tuning ... Post some more details on the power supply. ...
    (sci.electronics.design)
  • Re: BigNum -- BigFrac
    ... clear that you are performing digit by digit extraction -- getting it ... > For every set bit in the multiplier, ... > out to accumulator length to accomodate the shifts. ... Paul Hsieh ...
    (comp.programming)
  • Re: Decimal carry-save adder using reversed biquinary notation
    ... one could design a decimal arithmetic unit that operates at a ... Another fast approach for a long decimal multiplier would be to generate all 8 possible multiples of the first input value by a single digit value. ... While doing this each digit of the second input latches the relevant intermediate result, before a set of adders merge all these values. ...
    (comp.arch.arithmetic)