 uint NonRecursiveGCD(uint a, uint b)
 {
 if (a < b)
 {
 a += b;
 b = a  b;
 a = b;
 }

 if (b == 0) return a;

 while ( a % b != 0 )
 {
 a += b;
 b = a  b;
 a = b;
 b %= a;
 }
 return b;
 }
* This source code was highlighted with Source Code Highlighter.
Lines 38 ensure that "a" is bigger than "b" and exchange them otherwise using a well known trick for exchanging variables without additional memory.
Line 10 takes care for case GCD(a,0), and returns "a" as the GCD.
The "while" loop in lines 1218 actually implements the Euclid's algorithm by finding remainder of "a" and "b", then puts "b" into "a" and the remainder into "b".
Lines 1416 use again the "swap" trick for exchanging variables without additional memory usage.
Line 19 returns the last remainder, which is also the GCD to the caller.
Any comments and suggestions are welcome.
No comments:
Post a comment