Реализации алгоритмов/Бинарный алгоритм вычисления НОД: различия между версиями

Javascript
(Реализации на Pascal, Perl, Scala перенесены из ../Алгоритм Евклида.)
(Javascript)
GCD:= GCD(b, abs(a - b));
end;
</source>
 
== Javascript ==
 
<source lang="javascript">
function GCD(m,n){ // НОД двух чисел
var factor = 1;
while(true){
//НОД(0, n) = n; НОД(m, 0) = m; НОД(m, m) = m;
if(m==n)
if(m==0) throw 'GCD(0,0)'
else return factor*m;
if(m==0) return factor*n;
if(n==0) return factor*m;
//НОД(1, n) = 1; НОД(m, 1) = 1;
if(m==1 || n==1) return factor;
//Если m, n чётные, то НОД(m, n) = 2*НОД(m/2, n/2);
if(!(m&1) && !(n&1)){
factor<<=1;
m>>=1;
n>>=1;
}
//Если m чётное, n нечётное, то НОД(m, n) = НОД(m/2, n);
else if(!(m&1)) m>>=1;
//Если n чётное, m нечётное, то НОД(m, n) = НОД(m, n/2);
else if(!(n&1)) n>>=1;
//Если m, n нечётные и n > m, то НОД(m, n) = НОД((n-m)/2, m);
else if(n>m) n = (n-m)>>1;
//Если m, n нечётные и n < m, то НОД(m, n) = НОД((m-n)/2, n);
else m = (m-n)>>1;
}
}
</source>
 
5

правок