Anonymous user
Greatest common divisor: Difference between revisions
→{{header|Euphoria}}: Euphoria examples added
(→{{header|C}}/{{header|C++}}: removed bogus benchmark: gcd_bin is very inefficient in general) |
(→{{header|Euphoria}}: Euphoria examples added) |
||
Line 490:
gcd(A,B) when A > B -> gcd(B, A rem B);
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#}}==
| |||