Calculating the Greatest Common Denominator (GCD) in PHP

This PHP code defines a function called gcd that calculates the greatest common denominator (GCD) of a list of integers by using a brute-force approach and later efficient and widely-used method called Euclidean Algorithm.

The code defines a function called gcd that takes any number of integers as input and returns their greatest common denominator. The function uses a simple approach: it starts by finding the smallest absolute value among the input numbers. Then, it iterates backward via a for loop from that smallest value to 2, checking if each number is a common divisor for all the input arguments. If a common divisor is found, the loop breaks, and the greatest common denominator is returned.

The example at the end demonstrates how to use the gcd function with three numbers (10, 20, and -35) and prints the result. In this case, it prints the greatest common denominator, which is 5.

/*
 ** Function gcd
 ** Input: any number of integers
 ** Output: integer
 ** Description: Returns the greatest common
 ** denominator from the input.
 */function gcd()
{
    // Find the smallest absolute value among the input numbers
    $start = 2147483647;
    foreach (func_get_args() as $arg) {
        if (abs($arg) < $start) {
            $start = abs($arg);
        }
    }

    // Loop from the smallest absolute value down to 2 to find the greatest common denominator
    for ($i = $start; $i > 1; $i--) {
        // Assume we will find a common divisor
        $isCommon = true;

        // Check each number in the input arguments
        foreach (func_get_args() as $arg) {
            // If the current number divided by $i has a remainder, it's not a common divisor
            if (($arg % $i) != 0) {
                $isCommon = false;
            }
        }

        // If $isCommon is still true, we found the greatest common denominator
        if ($isCommon) {
            break;
        }
    }

    // Return the greatest common denominator
    return $i;
}

// Example usage: prints the greatest common denominator of 10, 20, and -35
print(gcd(10, 20, -35) . "<br />\n");

Note that this is for demonstration purpose only as more efficient algorithms exist such as Euclidean algorithm for calculating the greatest common denominator, especially for larger numbers.

The Euclidean algorithm is a more efficient and widely-used method for calculating the greatest common divisor (GCD) of two numbers. It’s effective for larger numbers and is based on the fact that the GCD of two numbers is the same as the GCD of the smaller number and the remainder of the larger number divided by the smaller number.

function gcd($a, $b) {
    // Ensure both numbers are positive
    $a = abs($a);
    $b = abs($b);

    // Perform Euclidean algorithm
    while ($b != 0) {
        $temp = $b;
        $b = $a % $b;
        $a = $temp;
    }

    return $a;
}

// Example usage: prints the greatest common denominator of 10 and 20
print(gcd(10, 20) . "<br />\n");

This algorithm is more efficient than the brute-force approach we initially provided as it doesn’t involve iterating through all possible divisors. If you need to find the GCD of more than two numbers, you can repeatedly apply this algorithm to pairs of numbers.