The Euclidean algorithm finds the greatest common divisor by replacing a pair with the smaller number and the remainder.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | <?php declare(strict_types=1); // Euclidean GCD in PHP // // PURPOSE // The Euclidean algorithm finds the greatest common divisor by replacing a pair with the // smaller number and the remainder. Common divisors are preserved by this replacement. // // METHOD // Repeatedly compute a modulo b, move b into a, and put the remainder into b. Stop when b is // zero; the last nonzero value divides both original inputs. // // COMPLEXITY // O(log(min(a,b))) arithmetic steps for positive inputs, O(1) auxiliary space. // // CONTRACT // a and b are nonnegative integers. Defines gcd(0,0) as 0. Avoid negative values because // remainder conventions vary by language. // Public APIs infer array lengths except in C, which accepts pointer/length pairs. Vertex // counts and matrix dimensions remain explicit. Arrays must contain signed 32-bit integers. // Sorted order, correct tree topology, and caller-owned data-structure invariants are // preconditions; checking them on every query would change query complexity. // Scalar and shape checks are included. Value-range checks are included where needed to // prevent invalid indexing or nontermination. Allocation sizes are capped at 4,000,000 // workspace entries. Arithmetic outside Python raises an error on 32-bit overflow; Python // uses arbitrary precision. Native allocation failures propagate. In-place outputs may be // partly updated after arithmetic failure. These are single-threaded, in-memory // implementations. // // LANGUAGE DETAILS // PHP 8.1+ on a 64-bit runtime: packed arrays, strict scalar types, read-only inputs by // value using copy-on-write, references only for outputs, and checked 32-bit arithmetic. // Invalid input and overflow throw exceptions. PHP arrays have higher overhead than native // packed buffers in C/Java. // // EXAMPLE // Expected return: 6. // Run: php example.php // Tests for this exact source artifact run before publication. The accompanying source // archive includes unit cases, runtime results, and source hashes. function alg_require(bool $valid): void { if (!$valid) throw new InvalidArgumentException("invalid algorithm input"); } function alg_checked(int|float $v): int { if ($v < -2147483648 || $v > 2147483647 || floor($v) != $v) throw new OverflowException("32-bit result overflow"); return (int)$v; } function alg_add(int $a,int $b): int { return alg_checked($a+$b); } function alg_sub(int $a,int $b): int { return alg_checked($a-$b); } function alg_mul(int $a,int $b): int { return alg_checked($a*$b); } function alg_size(int $n): int { alg_require($n>=0 && $n<=4000000); return $n; } function gcd(int $a, int $b): int { alg_require((($a >= 0) && ($b >= 0))); $remainder = 0; while (($b != 0)) { $remainder = ($a % $b); $a = $b; $b = $remainder; } return $a; } $a = 48; $b = 18; $result = gcd($a, $b); echo $result, PHP_EOL; |