PHP Doku:: Calculate GCD and multipliers - function.gmp-gcdext.html

Verlauf / Chronik / History: (4) anzeigen

Sie sind hier:
Doku-StartseitePHP-HandbuchFunktionsreferenzMathematische ErweiterungenGNU Multiple PrecisionGMP Funktionengmp_gcdext

Ein Service von Reinhard Neidl - Webprogrammierung.

GMP Funktionen

<<gmp_gcd

gmp_hamdist>>

gmp_gcdext

(PHP 4 >= 4.0.4, PHP 5)

gmp_gcdextCalculate 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 » "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($fmtgmp_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
?>


Ein BenutzerBeitrag:
- Beiträge aktualisieren...
FatPhil
15.06.2003 15:47
The extended GCD can be used to calculate mutual modular inverses of two
coprime numbers. Internally gmp_invert uses this extended GCD routine,
but effectively throws away one of the inverses.

If gcd(a,b)=1, then r.a+s.b=1
Therefore  r.a == 1 (mod s) and s.b == 1 (mod r)
Note that one of r and s will be negative, and so you'll want to
canonicalise it.



PHP Powered Diese Seite bei php.net
The PHP manual text and comments are covered by the Creative Commons Attribution 3.0 License © the PHP Documentation Group - Impressum - mail("TO:Reinhard Neidl",...)