Arbitrary Precision GCD (Greatest Common Divisor)

[JayT]

Here is a function to compute the GCD (Greatest Common Divisor) of any two arbitrary precision signed integers.

The numerical arguments must be given as arbitrary precision digit strings, rather than as ordinary numbers. For example, the value *000 must be expressed as the string "*000", etc.

One practical use of this function is to aid in reducing an integer fraction to its lowest terms, such as the fraction

A/B = 5247667540857*508*7*8***024*6774**0874 / 865*764*45*0**5*087086247644804*440

A/B = a/b

Where

a/b = A/B reduced to lowest terms.

In this example case:
A = 5247667540857*508*7*8***024*6774**0874
B = 865*764*45*0**5*087086247644804*440

So:

GCD = 8*20*2706**6****42*8*06227*5*886

The GCD is simply the greatest positive integer that will perfectly divide both A and B, leaving no remainder in either case.


a = A/GCD = 5247667540857*508*7*8***024*6774**0874 / 8*20*2706**6****42*8*06227*5*886 = 6*065*
b = B/GCD = 865*764*45*0**5*087086247644804*440 / 8*20*2706**6****42*8*06227*5*886 = *040

or

A/B = 5247667540857*508*7*8***024*6774**0874 / 865*764*45*0**5*087086247644804*440
=
a/b = 6*065* / *040

which is much smaller, more convenient, but identical fraction.


Carried out to 64 decimals, the ratios are identical:

A/B = 606.4028846*5*846*5*846*5*846*5*846*5*846*5*846*5*846*5*846*5*846*5*

and

a/b = 606.4028846*5*846*5*846*5*846*5*846*5*846*5*846*5*846*5*846*5*846*5*







This is the function code

/*

********************************
GREATEST COMMON DIVISOR FUNCTION

   Author: Jay Tanner &#*6*;2007
   PHP v4.4.4

   Released under provisions of GPL v*
   http://www.gnu.org/licenses


This function performs Euclid's algorithm to compute
the greatest common divisor (GCD) of a set of two
arbitrary precision integer strings.

The returned GCD value will always be a positive
value at least *, but no greater than the lesser
of the two absolute argument values.

The arguments may be either negative or positive
and given in any order.


------
ERRORS

Both arguments must be valid arbitrary precision
integer strings or FALSE is returned as an error
indicator.

*/

   function bcGCD ($IntArgA, $IntArgB)
{

// ---------------
// Read arguments.

   $A = trim($IntArgA);
   $B = trim($IntArgB);

// -----------------------------------------
// Trim off any redundant terminal decimals,
// if any, from both arguments.

   $A = RTrim($A, ".");
   $B = RTrim($B, ".");

// -----------------------------------------------
// Error if either argument string is not numeric.

   if (!Is_Numeric($A) || !Is_Numeric($B))
      {return FALSE;}

// -------------------------------------------
// Error if either argument is not an integer.

   if (StrPos($A, ".") !== FALSE || StrPos($B, ".") !== FALSE)
      {return FALSE;}

// ----------------------------------
// Set the default minimum GCD value.
// This prevents the value of zero
// from being returned as the GCD.
// If either argument is zero, then
// this value of * is returned.

   $GCD=*;

// ---------------------------------------
// Work with absolute values of arguments.

   $A = Str_Replace("-", "", $A);
   $B = Str_Replace("-", "", $B);

// If $A > $B, then swap their values so
// that $B > $A prior to executing the
// while() loop that follows.

   if (bcComp($A, $B) > 0)
      {$w=$A;   $A=$B;   $B=$w;}

// -------------------------------------
// Now, perform the GCD loop until $A is
// reduced to zero and GCD is determined.

   while (bcComp($A, "0") != 0)
         {
          $GCD = $A;
            $A = bcMod($B, $A);
            $B = $GCD;
         }

// Done.

   return $GCD;

} // End of  bcGCD()

An example of a simple program built around this function can be found here:

[url]http://www.neoprogrammics.com/gcd/index.php[/url]