JayT

08-31-2007, 03:27 AM

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:

http://www.neoprogrammics.com/gcd/index.php

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:

http://www.neoprogrammics.com/gcd/index.php