Greatest common divisor: Difference between revisions

===Modules===

All three modules will take large integers as input, e.g.

<tt>gcd("68095260063025322303723429387", "51306142182612010300800963053")</tt>. Other possibilities are Math::Cephes euclid, Math::GMPz gcd and gcd_ui.

<lang perl># Fastest, takes multiple inputs

use Math::Prime::Util "gcd";

$gcd = gcd(49865, 69811);

# In CORE. Slowest, takes multiple inputs, result is a Math::BigInt unless converted

use Math::BigInt;

$gcd = Math::BigInt::bgcd(49865, 69811)->numify;

# Result is a Math::Pari object unless converted

use Math::Pari "gcd";

$gcd = gcd(49865, 69811)->pari2iv

</lang>

use Math::BigInt;

use Math::Pari;

use Math::Prime::Util;

'gcd_rec' => sub { gcd($u, $v); },

'gcd_bigint' => sub { Math::BigInt::bgcd($u,$v)->numify(); },

'gcd_pari' => sub { Math::Pari::gcd($u,$v)->pari2iv(); },

'gcd_mpu' => sub { Math::Prime::Util::gcd($u,$v); },

Output on 'Intel i3930k 4.2GHz' / Linux / Perl 5.20:

Rate gcd_bigint gcd_bin gcd_rec gcd_iter gcd_pari gcd_mpu

gcd_bigint 39939/s -- -83% -94% -95% -98% -99%

gcd_bin 234790/s 488% -- -62% -70% -88% -97%

gcd_rec 614750/s 1439% 162% -- -23% -68% -91%

gcd_iter 793422/s 1887% 238% 29% -- -58% -89%

gcd_pari 1896544/s 4649% 708% 209% 139% -- -73%

gcd_mpu 7114798/s 17714% 2930% 1057% 797% 275% --