2つの自然数、a、bの最大公約数(g.c.d.)を求める方法としては、
a、bをそれぞれ素因数分解して、共通の因子を取り出す、
という方法があるが、a、bが小さい数ならともかく、ひじょうに大きい数、
例えば100桁以上になると、素因数分解自体が困難となる。
100桁と云わないまでも、例えば、851と437の最大公約数といった場合、
それぞれの素因数を暗算で見つけられる人は少ないと思う。
素因数分解を行わず、一般の数に適用可能なアルゴリズムとして、ユークリッドの互除法がある。
例.851と437の最大公約数を求める。
最大公約数をdとする。もちろん、1かもしれない。
851を437で割ってみる。
851=1・437+414
この時点で、851と437の最大公約数はわからない。
しかし、公約数である以上、=の両方の値を割り切るはずである。
すなわち、
左辺:851
右辺:437と414
を割り切るはずである。つまり、
(851, 437)=(437, 414)
である。
(ここで、何をやろうとしているのかピンとくるかもしれないが、とにかくこのまま進める。)
次に、437と414について、437を414で割ってみる。
437=1・414+23
上と同じ理由で、
(437, 414)=(414, 23)
となる。
次に、414と23について、414を23で割ってみる。
414=18・23
割り切れた。
すなわち、414と23の最大公約数は23である。
これまでの等式を逆に辿っていくと、
23=(414, 23)=(437, 414)=(851, 437)
となり、851と437の最大公約数は23となる。
実際に割ってみると、
851=37・23
437=19・23
であるから、たしかに23は851と437の最大公約数である。
このように、
2数を割って余りを取っていき、余りが0になった時、
その時の割り切った数が最大公約数である。
というアルゴリズムをユークリッドの互除法と呼ぶ。
このアルゴリズムのポイントは、
ある数を素因数分解するのは一般に困難であるが、
2つの数の割り算を行うのは簡単である。
という点にある。
ちなみに、ユークリッドというと幾何学というイメージが強いが、
『原論』では1巻まるごと、整数論を扱っている巻があり、
その中で、このユークリッドの互除法の他に、
等について、触れている。
プログラムは以下のとおり。
fnGcd(A,B) local D if A<B then swap (A,B) D=A@B while (D<>0) A=B:B=D:D=A@B wend return(B)
UBASICでは、gcd(n)という組み込み関数となっている。
これを利用して、
等が可能となる。これについて特にプログラムは示さない。
与えられた数a、b、cについて、ax+by=cをみたす整数x、yを求める。
a、bの最大公約数をdをしたとき、d|cなら解が存在する。
アルゴリズムは以下のとおり。
(1) S=a, T=bとする (2) S=Q・T+U(余り) ・U=0 なら、T=gcd(a,b) ・U≠0 なら、 S=T, T=Uとして、(2) へ
(1) Sa=1, Ta=0 Sb=0, Tb=1 とする(初期値) (2) Ua=Sa−Q*Ta Ub=Sb−Q*Tb Sa=Ta, Sb=Tb Ta=Ua, Tb=Ub (3) gcd(a, b)=T(下のプログラムではS)が求まったとき、 x=Sa×c/T y=Sb×c/T が解。 gcd(a, b) が c を割り切らないときは、解なし
10 input "A, B, C=";A,B,C 20 S=A:Sa=1:Sb=0 30 T=B:Ta=0:Tb=1 40 while T<>0 50 Q=S\T 60 U=S-Q*T:Ua=Sa-Q*Ta:Ub=Sb-Q*Tb 70 S=T:Sa=Ta:Sb=Tb 80 T=U:Ta=Ua:Tb=Ub 90 wend 100 G=S 110 if C@G<>0 then print "解なし。":end 120 Sa*=C\G:Sb*=C\G 130 print "一般解は x=";Sa;"+";B\G;"t , y=";Sb;"-";A\G;"t" 140 end
(a, m)=1 のとき、ab≡1 (mod m) となる、bが存在する。bを求める。
前の式、ax+by=cにおいて、
b → m
c → 1
とおいたときのx が解となる。
x だけ求めればよいので、前のプログラムで、
Ub=Sb−Q*Tb
の部分は不要。よって、Sb、Tbも不要。
10 input "A, M =";A,M 20 B=fnModinv(A,M) 30 if B=0 then print "解なし。":end 40 print B 50 end 60 ' 70 fnModinv(A,M) 80 local Ta,U,Ua,Q 90 Sa=1:Ta=0 100 while M<>0 110 Q=A\M:U=A-Q*M:Ua=Sa-Q*Ta 120 A=M:Sa=Ta 130 M=U:Ta=Ua 140 wend 150 if A<>1 then return(0) 160 return(Sa)
UBASICでは、modinv(a,m)という組み込み関数になっている。
2数、a、bについて、まず、2で割れるだけ割っておき、それをcに格納する。
2で割る操作は、a、bを2進数で表した場合、右にシフトしていけばよい(これは、2の割算よりも速い)。
そうすると、(1)両方とも奇数、(2)片方が奇数、片方は偶数、の状態になるはずである。
ここで、後者の場合、偶数が両者の共通因子になることはありえないので、
両者奇数になるまで、2で割る。
大きい方から小さい方を引く。奇数と奇数の差なので、必ず偶数となる。
かつ偶数の共通因子はないから、この答えを奇数になるまで、2で割る。
この答えと、小さい方について、同じ処理を繰り返す。
(互除法では、ここで割算を行った)。
上記処理を行っていくと、どこかで、a−b=0となる。
この0となったときのa、bの値が、奇数の最大共通素因数となる。
この値と、c(2のべきの最大共通素因数)を掛け合わせたものが、求める最大公約数となる。
割算ではなく、引算にしているため、ループの回数は互除法に比べて多くなる。
しかし、右へのシフト及び引算等は、割算に比べて圧倒的に速いため、
全体としての処理時間は、かなり短縮される。
特に、大きい数の最大公約数を求めるときは、効果が大きい。
前 | この章の目次 | 次 |
---|