OpenEuphoria

Reducing fractions

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