igcd,igcdcntl

igcd(i1,i2)

:: 整数の GCD (最大公約数)

igcdcntl([i])

:: 整数 GCDのアルゴリズム選択

return

整数

i1,i2,i

整数

• igcd は i1 と i2 の GCD を求める.
• 引数が整数でない場合は, エラーまたは無意味な結果を返す.
• 多項式の場合は, gcd, gcdz を用いる.
• 整数 GCD にはさまざまな方法があり, igcdcntl で設定できる.

  0

  Euclid 互除法 (default)

  1

  binary GCD

  2

  bmod GCD

  3

  accelerated integer GCD

  2, 3 は [Weber] による. おおむね 3 が高速だが, 例外もある.

[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)

参照

section gcd, gcdz.

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