commons-user mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ted Dunning <>
Subject Re: Math Fraction, reducing gcd() calls
Date Tue, 08 Apr 2014 22:14:33 GMT
On Tue, Apr 8, 2014 at 2:52 PM, paul womack <> wrote:

> Gilles wrote:
>> I think that calling "gcd" ensures that the result will not overflow for
>> the largest possible range of arguments.
>> It's part of the code logic.
>> Maybe you could write methods that implement the "naive" algorithms for
>> addition, subtraction, ...
>> Then test whether you always get correct results in your application.
> Agreed; when you have a "overview" you can bypass
> some of the at-each-stage precautions a general implementation
> is forced to do.
> My only other suggestion (which is less good) would be to use
> a small LRU cache on the gcd() operation, but the success
> of that would depend very much on the numeric properties
> of your data.

GCD's cost for integers < n is O(log n).  That means it is almost certainly
cheaper in terms of cycles required for gcd to do it once at the end.

The real cost, however, is that other operations may now operate on LOTs
more digits than necessary and thus may take more time.  For additions and
subtractions, this is not possible, but multiplications and more complex
operations can have this effect.

  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message