OpenEuphoria

Re: Reducing fractions

• Posted by "Juergen Luethje" <j.lue at gmx.de> May 24, 2005
• 379 views

Christian Cuvier wrote:

>> From: "Juergen Luethje"

<snip>

>> }}}
<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:
>
> }}}
<eucode>
> 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.



Thank you for looking into this issue.
I made several tests with big integers, and your gcd2() function was
always significantly slower than mine (Windows 98, exw.exe 2.5).

> 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.

I don't think that calculating the Greatest Common Divisor itself is the
time critical part of the whole program
<http://www.listfilter.com/EUforum/m12539.html> anyway, since the
Euclidean Algorithm is rather fast ( O(log(n)) ). For deteils see
e.g. <http://mathworld.wolfram.com/EuclideanAlgorithm.html>.

I believe most effective would be any attempt to reduce the number of
iterations in the function reduced_fractions() ( currently O(n^2) ).

Regards,
   Juergen