Greatest common divisor: Difference between revisions
Content added Content deleted
(→{{header|C}}/{{header|C++}}: removed bogus benchmark: gcd_bin is very inefficient in general) |
(→{{header|Euphoria}}: Euphoria examples added) |
||
Line 490: | Line 490: | ||
gcd(A,B) when A > B -> gcd(B, A rem B); |
gcd(A,B) when A > B -> gcd(B, A rem B); |
||
gcd(A,B) -> gcd(A, B rem A).</lang> |
gcd(A,B) -> gcd(A, B rem A).</lang> |
||
=={{header|Euphoria}}== |
|||
{{trans|C/C++}} |
|||
===Iterative Euclid algorithm=== |
|||
<lang euphoria>function gcd_iter(integer u, integer v) |
|||
integer t |
|||
while v do |
|||
t = u |
|||
u = v |
|||
v = remainder(t, v) |
|||
end while |
|||
if u < 0 then |
|||
return -u |
|||
else |
|||
return u |
|||
end if |
|||
end function</lang> |
|||
===Recursive Euclid algorithm=== |
|||
<lang euphoria>function gcd(integer u, integer v) |
|||
if v then |
|||
return gcd(v, remainder(u, v)) |
|||
elsif u < 0 then |
|||
return -u |
|||
else |
|||
return u |
|||
end if |
|||
end function</lang> |
|||
===Iterative binary algorithm=== |
|||
<lang euphoria>function gcd_bin(integer u, integer v) |
|||
integer t, k |
|||
if u < 0 then -- abs(u) |
|||
u = -u |
|||
end if |
|||
if v < 0 then -- abs(v) |
|||
v = -v |
|||
end if |
|||
if u < v then |
|||
t = u |
|||
u = v |
|||
v = t |
|||
end if |
|||
if v = 0 then |
|||
return u |
|||
end if |
|||
k = 1 |
|||
while and_bits(u,1) = 0 and and_bits(v,1) = 0 do |
|||
u = floor(u/2) -- u >>= 1 |
|||
v = floor(v/2) -- v >>= 1 |
|||
k *= 2 -- k <<= 1 |
|||
end while |
|||
if and_bits(u,1) then |
|||
t = -v |
|||
else |
|||
t = u |
|||
end if |
|||
while t do |
|||
while and_bits(t, 1) = 0 do |
|||
t = floor(t/2) |
|||
end while |
|||
if t > 0 then |
|||
u = t |
|||
else |
|||
v = -t |
|||
end if |
|||
t = u - v |
|||
end while |
|||
return u * k |
|||
end function</lang> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |