igcd,igcdcntl

igcd(i1,i2)

:: The integer greatest common divisor of i1 and i2.

igcdcntl([i])

:: Selects an algorithm for integer GCD.

return

integer

i1,i2,i

integer

• Function igcd() returns the integer greatest common divisor of the given two integers.
• An error will result if the argument is not an integer; the result is not valid even if one is returned.
• Use gcd(), gcdz() for polynomial GCD.
• Various method of integer GCD computation are implemented and they can be selected by igcdcntl.

  0

  Euclid algorithm (default)

  1

  binary GCD

  2

  bmod GCD

  3

  accelerated integer GCD

  2, 3 are due to [Weber]. In most cases 3 is the fastest, but there are exceptions.

[0] A=lrandom(10^4)$
[1] B=lrandom(10^4)$
[2] C=lrandom(10^4)$
[3] D=A*C$
[4] E=A*B$
[5] cputime(1)$
[6] igcd(D,E)$
0.6sec + gc : 1.93sec(2.531sec)
[7] igcdcntl(1)$
[8] igcd(D,E)$  
0.27sec(0.2635sec)
[9] igcdcntl(2)$
[10] igcd(D,E)$  
0.19sec(0.1928sec)
[11] igcdcntl(3)$
[12] igcd(D,E)$  
0.08sec(0.08023sec)

References

section gcd, gcdz.

Go to the first, previous, next, last section, table of contents.