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.