PHP | gmp_gcdext() function
The gmp_gcdext() is an inbuilt function in PHP which calculates the GCD ( Greatest Common Divisor ) and multipliers of a given equation such that a * x + b * y = GCD(a, b), where GCD is the greatest common divisor.
This function is used to solve linear Diophantine equation in two variables .
Syntax:
array gmp_gcdext ( GMP $a, GMP $b )
Parameters: The gmp_gcdext() function accepts two parameters as listed above and described below:
- $a: This parameter can be a GMP resource in PHP 5.5 and earlier, a GMP object in PHP 5.6, or we are also allowed to pass a numeric string provided that it is possible to convert that string to a number.
- $b: This parameter can be a GMP resource in PHP 5.5 and earlier, a GMP object in PHP 5.6, or we are also allowed to pass a numeric string provided that it is possible to convert that string to a number.
Return Values: This function will return an array of GMP numbers (GNU Multiple Precision: For large numbers) that is the multipliers (x and y of a given equation ) and the gcd.
Examples:
Input: a = 12 , b = 21 equation = 12 * x + 21 * y = 3 Output: Input: a = 5 , b = 10 equation = 5 * x + 10 * y = 5 Output: x = 1 , y = 0 , GCD(12,21) = 5
Below program illustrate the gmp_gcdext() function:
<?php // PHP code to solve a Diophantine equation // Solve the equation a*x + b*y = g // where a =, b =, g = gcd(5, 6) = 1 $a = gmp_init(5); $b = gmp_init(6); // calculates gcd of two gmp numbers $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 generated\n" ; ?> |
Output:
Solution: 5 * -1 + 6 * 1 = 1
Reference : http://php.net/manual/en/function.gmp-gcdext.php
Contact Us