OpenEuphoria

Re: Reducing fractions

• Posted by Matt Lewis <matthewwalkerlewis at gmail.com> May 23, 2005
• 393 views

Juergen Luethje wrote:
> 
> Hi all,
> 
> I'm looking for a special way to reduce several fractions.
> 
> Say I want to multiply e.g. the fractions 3/8, 2/4 and 2/6.
> Of course I could do:
>    numerator   = 3*2*2
>    denominator = 8*4*6
> 
> and then calculate the GCD and reduce the fraction. But in order to
> avoid overflow for big numbers, the routine should reduce the fractions
> *before* it multiplies their numerators and denominators.
> 
> Below you'll find my function 'reduced_fractions()', which looks at
> all pairs of numerators and denominators, and tries to reduce them
> (e.g. {3,8} means the fraction 3/8).
> It works fine, but can take a considerable amount of time. So I wonder
> whether the function actually has to look at all the pairs, or whether
> there is a faster way to achieve the same result.

As a first step optimization, you could ignore when the number is less
than the square root of whatever your precision limit is.  Assuming you're
using doubles, then you can go up to 51 or 52 bits, which give you up to
2,251,799,813,685,250 or 4,503,599,627,370,500 as your max integers before
you start losing precision.  That means that you can safely ignore numbers
up to either 47,453,132 or 67,108,864 (check the spec for a 64-bit floating
point number--you'll get 1 additional digit over whatever the mantissa size
is).

Of course, you may well find that one large factoriztion takes longer
than a few small factorizations, so you may have to be more clever in
deciding when factoring is worth it.  Beyond that, you'll probably need
to investigate faster factoring methods.  Algoritms you could investigate
include:

Quadratic Sieve
General Number Field Sieve
Lenstra Elliptic Curve Factorization

Google will give you lots of results for these, but implementing them
seems far from simple (and will likely include needing a good matrix
library).

Matt Lewis