Re: BigNum -- BigFrac
From: Paul Hsieh (qed_at_pobox.com)
Date: 12/25/03
- Next message: Edward G. Nilges: "Re: Letter to US Sen. Byron Dorgan re unpaid overtime"
- Previous message: Bill Godfrey: "Re: To Richard Heathfield: enough's enough"
- In reply to: Programmer Dude: "BigNum -- BigFrac"
- Next in thread: Programmer Dude: "Re: BigNum -- BigFrac"
- Reply: Programmer Dude: "Re: BigNum -- BigFrac"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: 25 Dec 2003 13:50:04 -0800
Programmer Dude <Chris@Sonnack.com> wrote:
> 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.
Yes, but you might as well throw BigIntSubtract() in there.
> I get the impression from something someone said here that the
> stored ratios are normalized--using gcd()--to their lowest
> possible values.
Yes ... but you should also have a kind of implicit rule that
fractions always have positive denominators.
> [...] Presumably, this is to reduce the math that is required for processing.
Well actually its main purpose is to ensure uniqueness of fractions,
based solely on unique numerator, denominators. To check if two
post-normalized fractions are equal you only need to compare the
numerator and denominator values. Without normalization, you would
have to do the cross multiply or something slow like that. It also
keeps the sizes of the numbers under some kind of control even after
numerous operations.
> Thus, IIU, there might an example like this:
>
> user input:
>
> print 2.5 + 3.14159
>
> initial conversion to BigFracs:
>
> 25/10 + 314159/100000
Well certainly you could have a mode which converted from finite
decimal to fractions, so this is fine.
> 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.
That is correct. The numerator in general will not necessarily be a
power of 10.
> [...] Thus the output routine likely involves a BigIntDivide()
> operation
Yes ... its fairly straight forward. Just try writing your own
putInt32(int) function for starters (without sprintf or strtol or
something like that.) The algorithm is almost exactly the same.
> [...] (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?)
There is no slicker way that I am aware of.
> 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.
No. You do this and you will lose the divide operation altogether.
This kind of defeats the main benefit of using a fractional
representation for exact computation.
> 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)
(Notice your use of an *exponent* ...)
> 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!).
Yes but then this is no different from the exponent, mantissa based
formats proposed earlier. You are forced to lose accuracy on divides,
or just give up on divides.
> So, no gcd(), no multiply.
Yes but if you perform no gcd at all, then you will lose your
uniqueness property, and thus will also be stuck in situations where
10/100 and 1/10 will show up as results in your library, and not
realize that they are the same number without some computation.
> [...] With the denominator ALWAYS a power of ten, output is always trival.
Of course, but output formatting is not usually so important in terms
of performance as to warrant an internal format suited just for its
needs.
> Division needs work, since inverting the ratio messes up the system.
> Still thinking about that one.
It needs more than "work" -- it needs to be thrown out, or else you
will be stuck with approximations. Thus losing the whole
uncompromising accuracy that you were looking for in the first place.
> But.... thoughts, anyone? It almost seems to combine the goodness
> of FP with the goodness of ratios....
No, you don't carry forward the exactness and good divide properties
of a pure fractional system forward. This is just a floating point
system at best.
-- Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/
- Next message: Edward G. Nilges: "Re: Letter to US Sen. Byron Dorgan re unpaid overtime"
- Previous message: Bill Godfrey: "Re: To Richard Heathfield: enough's enough"
- In reply to: Programmer Dude: "BigNum -- BigFrac"
- Next in thread: Programmer Dude: "Re: BigNum -- BigFrac"
- Reply: Programmer Dude: "Re: BigNum -- BigFrac"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
