Content deleted Content added
a source would clearly be needed to support your contention. →gcd(0,0) |
→Implementations: added pseudocode |
||
Line 106:
:I think you did the right thing. I just restored the C and ARM implementations after [[User:Arvindn]] blanked them, for these reasons: IMHO, C isn't important for showing bitwise operations; it should be obvious that you'd use bitwise ops where appropriate. But the C implementation is easier to read than the English algorithm at the moment, so it needs to stay at least until there's an appropriate substitute ([[pseudocode]]? Knuth-style algorithm description?). IMHO, the ARM implementation is really enlightening, because it shows the real size and speed benefit of the algorithm in a way that no higher-level language's compiler even approaches. (In particular, it totally stomps the C implementation.) Without ''some'' hand-optimized assembly implementation, the advantage of binary GCD over Euclid is not obvious, IMHO. --[[User:Quuxplusone|Quuxplusone]] 21:18, 1 January 2007 (UTC)
The following pseudocode describes the algoritm probably best:
<source lang="text">
Input: Positive integers u and v
Output: gcd(u,v)
Note: division and multiplication by 2 can in many languages most efficiently be done by bitshifting.
START
s:=1
while even(u) and even(v) do
u:=u/2;v:=v/2;s:=s*2;
while even(u) do u:=u/2
while even(v) do v:=v/2
while u<>v do
begin
if u>v then
begin
u:=u-v
while even(u) do u:=u/2
end
else
begin
v:=v-u
while even(v) do v:=v/2
end
end
return(u*s)
END
</source>
[[User:Hkleinnl|Hkleinnl]] ([[User talk:Hkleinnl|talk]]) 20:07, 12 August 2010 (UTC)
== Implementation in assembly ==
| |||