OpenEuphoria

Reducing fractions

• Posted by "Christian Cuvier" <christian.cuvier at agriculture.gouv.fr> May 24, 2005
• 398 views

> Date: Mon, 23 May 2005 16:48:18 +0200
> From: "Juergen Luethje" <j.lue at gmx.de>
> Subject: Reducing fractions
> 
> 
> 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.
> 
> }}}
<eucode>
> global type bigint (object x)
>    -- This type can hold bigger integers than Euphoria's built-in
>    -- integer type (> 1073741823).
>    -- It is technically an atom, but mathematically an integer.
>    if atom(x) then
>       return x = floor(x)
>    end if
>    return 0
> end type
> 
> global function gcd2 (bigint p, bigint q)
>    -- return the greatest common divisor of p and q (Euclidean Algorithm)
>    -- in : p, q: integers
>    -- out:       nonnegative integer (>= 0)
>    bigint r
> 
>    while q do
>       r = remainder(p, q)
>       p = q
>       q = r
>    end while
> 
>    -- return abs(p)
>    if p < 0 then
>       p = -p
>    end if
>    return p
> end function

[snip]

You can optimize the gcd2 function in several ways:

function gcd2_notest(bigint p,bigint q)
     -- return the greatest common divisor of p and q (Euclidean Algorithm)
     -- in : p, q: integers, p>q>0
     -- out:       nonnegative integer (> 0)
--internally used by gcd2, same algo as above but faster
--as most tests are made only at the time they may fail, ie with raw args
bigint r
while q>1 do  --this shaves an iteration off
   r=remainder(p,q)
   if r=0 then return q end if   --q divides p
   p=q
   q=r   --nonzero
end while
return 1  --p and q were relatively prime
end function

global function gcd2(bigint p,bigint q) return the greatest common divisor of p and q (Euclidean Algorithm)

in : p, q: integers, p>q>0 out: nonnegative integer (>= 0)

actually normalizes (p,q) and returns gcd2_notest's result returns 0 if p or q is 0 if not (p and q) then return 0 end if if p<0 then p=-p end if if q<0 then q=-q end if if p<q then p-=q q+=p p=q-p end if swap arguments return gcd2_notest(p,q) end function

And don't forget to switch type checking off. I didn't try defining r as a local var instead, so as not to create and destroy it a zillion times on the stack. Depends on whether Eu relies on the stack to store private vars.

HTH CChris }}}

Not Categorized, Please Help