OpenEuphoria

1. Reducing fractions

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

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.

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

global function reduced_fractions (sequence s)
   -- in: list of fractions to be reduced,
   --     of the form {{3,8}, {2,4}, {2,6}}
   bigint div

   for numerator = 1 to length(s) do
      for denominator = 1 to length(s) do
         div = gcd2(s[numerator][1], s[denominator][2])
         if div > 1 then
            s[numerator]  [1] /= div
            s[denominator][2] /= div
         end if
      end for
   end for
   return s
end function

? reduced_fractions({{3,8}, {2,4}, {2,6}})

Regards,
   Juergen

-- 
Have you read a good program lately?

3. Re: Reducing fractions

• Posted by "Juergen Luethje" <j.lue at gmx.de> May 23, 2005
• 408 views
• Last edited May 24, 2005

Matt Lewis wrote:

<snip>

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

I see. Should have thought of that myself ...

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

I recognized that Ricardo's "genfunc.e" library contains PrimeFactors(),
a basic function for factorization. I'll play with it a little.

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

This seems to be a bit over my head, so I'll probably have to wait
until someone provides an Eu library for it. 
Well, currently I don't need it for a real application.

Thanks,
   Juergen

5. Re: Reducing fractions

• Posted by "Juergen Luethje" <j.lue at gmx.de> May 24, 2005
• 380 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