BigNum -- BigFrac

From: Programmer Dude (Chris_at_Sonnack.com)
Date: 12/23/03 

Date: Tue, 23 Dec 2003 11:13:06 -0600

Okay, I'm convinced! I started playing around with BigFracs last
night, and (probably, re-)discovered some fascinating things.

First, checking, do I understand the "basic" or "usual" way this
is done: BigInts as numerator and denominator and a number of
required operations: BigIntAdd(), BigIntMultiply() & gcd(). Also
the internal BigInt storage is binary.

I get the impression from something someone said here that the
stored ratios are normalized--using gcd()--to their lowest
possible values. Presumably, this is to reduce the math that
is required for processing.

Thus, IIU, there might an example like this:

user input:

    print 2.5 + 3.14159

initial conversion to BigFracs:

    25/10 + 314159/100000

after gcd:

    5/2 + 314159/100000

do the add:

    (5*100000 + 314159*2) / 2*100000
    (500000 + 628318) / 200000
     1128318 / 200000

after gcd:

    564159/100000

Eventual output in this case is easy with a denominator of 100000,
but--with the design so far (keep reading!)--you can't count on it
being so. Thus the output routine likely involves a BigIntDivide()
operation (I need to review the output code Arthur posted though--
might be a better way?).

All this is fine and not tough to implement, but it does seem this
design requires *three* BigIntMultiply()s and a BigIntAdd(). Even
multiplying appears to require two BigIntMultiply()s. (Or is there
a slicker way to do it?)

What I stumbled on last night appears to remove the need for the
gcd() and the multiply function for add and subtract and removes
one multiply from multiply. (And I'm sure I've just stumbled on
an existing wheel--no great claims of invention here.)

The idea is to keep the denominator as a power of ten, and it's
even possible to remove the BigInt-ness from it if one is willing
to restrict the range to, say, 64 bits worth of powers of ten.

The interesting thing is this "formula":

    A/10^ae + B/10^be = (A*10^be-j + B*10^ae-j) / 10^k

Where: j=min(ae,be) and: k=max(ae,be)

What ends up happening is that one of the powers of ten (the lesser)
drops to zero which reduces one side of the addition to identity--
hence no multiply required there. There is also no multiply in the
denominator. The final multiply is *always* a power of ten multiply,
and this can be implemented as a series of left shifts and adds
(surely much faster than an actual multiply!).

So, no gcd(), no multiply.

Returning to the example (ten powers in {}):

    print 2.5 + 3.14159

initial conversion to BigFracs:

    25/{1} + 314159/{5}

do the add:

    j=1; k=5

    (25*{5-1} + 314159*{1-1}) / {5}
    (25*{4} + 314159*{0}) / {5}
    (250000 + 314159) / {5}
    564159 / {5}

With the denominator ALWAYS a power of ten, output is always trival.

Multiplication still requires multiplying numerators, but the
"denominators" can just be added.

    2.5 * 3.14159

    25/{1} * 314159/{5}
    25 * 314159/{6}
    7853975 /{6}

Division needs work, since inverting the ratio messes up the system.
Still thinking about that one.

But.... thoughts, anyone? It almost seems to combine the goodness
of FP with the goodness of ratios.... 

-- 
|_ CJSonnack <Chris@Sonnack.com> _____________| How's my programming? |
|_ http://www.Sonnack.com/ ___________________| Call: 1-800-DEV-NULL  |
|_____________________________________________|_______________________|

Relevant Pages

  • Re: BigNum -- BigFrac
    ... BigInts as numerator and denominator and a number of ... Well actually its main purpose is to ensure uniqueness of fractions, ... numerator and denominator values. ... > multiplying appears to require two BigIntMultiplys. ...
    (comp.programming)
  • Re: Can I have fries and a calculator with that?
    ... We can rationalize the denominator of 1/b, ... > After multiplying, but before reducing, the denominator will be ... > The numerator will be an integer-linear combination of 15 ... The above method of rationalizing denominators is actually ...
    (sci.math)
  • Re: limits help
    ... using taylor expansion, to expanding the denominator in the fraction ... wikipedia on the series expansion of y = coth x and multiplying it by ...
    (sci.math)
  • Re: Dividing complex numbers
    ... You divide two complex numbers by taking the conjugate of the ... denominator and multiplying the dividend and denominator by it. ...
    (sci.math)
Loading