WolframAlpha

A new computational knowledge base is up and running. It calculates whatever you want, including your mortgage return, distance between cities and much more.

Try it: http://www.wolframalpha.com

In order to add WolframAlpha to search providers of your IE click here and follow instructions on "Create Your Own" section

Non-recursive implementation of Euclidean algorithm Greatest Common Divisor (C#)

We're familiar with Euclid's algorithm for finding greatest common divisor since from school, and implemented it for sure on basic programming classes. The below method does actually the same, but eliminates recursion (which is a bad thing) and does not uses any additional variables (which is a good thing). The function may look non-readable due to some tricks, but I hope the explanation below makes it clearer.

1. uint NonRecursiveGCD(uint a, uint b)
2. {
3.   if (a < b)
4.   {
5.     a += b;
6.     b = a - b;
7.     a -= b;
8.   }
9.       
10.   if (b == 0) return a;
11.  
12.   while ( a % b != 0 )
13.   {
14.     a += b;
15.     b = a - b;
16.     a -= b;
17.     b %= a;
18.   }
19.   return b;
20. }

* This source code was highlighted with Source Code Highlighter.

Lines 3-8 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 12-18 actually implements the Euclid's algorithm by finding remainder of "a" and "b", then puts "b" into "a" and the remainder into "b".

Lines 14-16 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.