monitor file activity
+ Reply to Thread
Results 1 to 3 of 3

Thread: Arbitrary Precision GCD (Greatest Common Divisor)

  1. #1
    Join Date
    Aug 2007
    Posts
    122

    Arbitrary Precision GCD (Greatest Common Divisor)

    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

    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]
    Last edited by JayT; 09-07-2007 at 02:03 PM.

  2. #2
    Join Date
    Jan 2005
    Posts
    623
    Thanks for the script. I need to start documenting my scripts like JayT. Check out his site too. Some really cool stuff there.
    [url=http://www.syntax******.info/tools/services.php]Speed Up Windows XP[/url]
    [url=http://www.syntax******.info/tools/ip.php]Get An Ip Address[/url]
    [url=http://www.syntax******.info/tools/base_converter.php]Base Converter[/url]
    --------------------------------
    [URL=http://www.boninroad.com/syntax******/]Old Site[/URL]
    [URL=http://www.syntax******.info]Comming Soon[/URL]

  3. #3
    Join Date
    Aug 2007
    Posts
    122
    Quote Originally Posted by SyntaX****** View Post
    Thanks for the script. I need to start documenting my scripts like JayT. Check out his site too. Some really cool stuff there.
    Thanx, Syntax

    Since some people, especially beginners, have a hard time understanding the code written by others, documenting is indeed a good idea.

    Glad you liked my site.

    Some of the pages are actually old science and math notes I made over the years and am now converting into interactive web pages.

    It has no specific organisation yet, but I'm working on it slowly.


+ Reply to Thread

Similar Threads

  1. 2^*024 Decimal Precision
    By SyntaXmasteR in forum Programming
    Replies: 11
    Last Post: 05-21-2008, 05:53 PM
  2. i'm a common victim of hackers
    By staci in forum Internet Privacy
    Replies: 1
    Last Post: 07-30-2005, 10:38 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts