Function.gmp-gcdext

Aus PHP-Wiki

gmp_gcdext — Calculate GCD and multipliers

Beschreibung

array gmp_gcdext ( resource $a , resource $b )

Calculates g, s, and t, such that a*s + b*t = g = gcd(a,b), where gcd is the greatest common divisor. Returns an array with respective elements g, s and t. This function can be used to solve linear Diophantine equations in two variables. These are equations that allow only integer solutions and have the form: a*x + b*y = c. For more information, go to the [[http://mathworld.wolfram.com/DiophantineEquation.html|» "Diophantine Equation" page at MathWorld]]

Parameter-Liste

a

• Dies kann entweder eine resource für einen GMP Wert sein oder ein numerischer String wenn es möglich ist diesen in einen GMP Wert umzuwandeln.

b

• Dies kann entweder eine resource für einen GMP Wert sein oder ein numerischer String wenn es möglich ist diesen in einen GMP Wert umzuwandeln.

Rückgabewerte

An array of GMP numbers.

Beispiele

Beispiel #1 Solving a linear Diophantine equation

<?php
// Solve the equation a*s + b*t = g
// where a = 12, b = 21, g = gcd(12, 21) = 3
$a = gmp_init(12);
$b = gmp_init(21);
$g = gmp_gcd($a, $b);
$r = gmp_gcdext($a, $b);
 
$check_gcd = (gmp_strval($g) == gmp_strval($r['g']));
$eq_res = gmp_add(gmp_mul($a, $r['s']), gmp_mul($b, $r['t']));
$check_res = (gmp_strval($g) == gmp_strval($eq_res));
 
if ($check_gcd && $check_res) {
    $fmt = "Solution: %d*%d + %d*%d = %d\n";
    printf($fmt, gmp_strval($a), gmp_strval($r['s']), gmp_strval($b),
    gmp_strval($r['t']), gmp_strval($r['g']));
} else {
    echo "Error while solving the equation\n";
}
 
// output: Solution: 12*2 + 21*-1 = 3
?>