Greater Common Divisor (GCD), the Euclidean way

GDC using the Euclidean algorithm and different programming languages (as a means of a very simple coding kata):

Python (http://ideone.com/jqCLR):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def gcd(num,den):
rem = abs(num%den)
print "num: %d, den: %d, rem: %d"%(num,den,rem)
if (rem == 0):
     return den
else:
     return gcd(den,rem)


# Result should be 11 for all of the following  
print gcd(110,33)
print gcd(-110,33)
print gcd(33,-110)
print gcd(33,110)

C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <stdlib.h>

// Function prototype
int gcd(int a,int b);

int main()
{
printf("GCD(%d,%d) = %d\n",110,33,gcd(110,33));
printf("GCD(%d,%d) = %d\n",110,-33,gcd(110,-33));
printf("GCD(%d,%d) = %d\n",33,110,gcd(33,110));
printf("GCD(%d,%d) = %d\n",33,-110,gcd(33,-110));
exit(0);
}

int gcd(int a, int b)
{
int rem = abs(a%b);
if(rem == 0)
{
       return b;
}
else
{
       return gcd(b,rem);
}
}
 

C++


 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstdlib>
using namespace std;

class GDC
{
public:
  int calculateGDC(int a, int b);
};

int main()
{
  GDC * calculator = new GDC();
  int a = 110;
  int b = 33;
  cout << "GDC(" << a << "," << b << ") = " << calculator->calculateGDC(a,b) << endl;
  cout << "GDC(" << a << "," << -b << ") = " << calculator->calculateGDC(a,-b) << endl;
  cout << "GDC(" << -a << "," << b << ") = " << calculator->calculateGDC(-a,b) << endl;
  cout << "GDC(" << -a << "," << b << ") = " << calculator->calculateGDC(-a,b) << endl;
  delete calculator;
  exit(0);
}



int GDC::calculateGDC(int a, int b)
{
  int rem = abs(a%b);
  if (rem == 0)
  {
          return b;
  }
  else
  {
          return this->calculateGDC(b,rem);
  }
}
Java (http://ideone.com/nFqLf)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.math.*;
public class Main
{
    public static void main(String args[])
    {
            int a = 110;
            int b = 33;
            Main calc = new Main();
            System.out.println("GDC("+a+","+b+") = "+ calc.calculateGDC(a,b));
            System.out.println("GDC("+a+","+-b+") = "+ calc.calculateGDC(a,-b));
            System.out.println("GDC("+-a+","+b+") = "+ calc.calculateGDC(-a,b));
            System.out.println("GDC("+-a+","+-b+") = "+ calc.calculateGDC(-a,-b));
    }

    int calculateGDC(int a, int b){
            int rem = Math.abs(a%b);
            if (rem == 0)
            {
                    return b;
            }
            else
            {
                    return this.calculateGDC(b,rem);
            }
    }
}

Ruby (http://ideone.com/Q8HPg)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def mcd(a,b)
 rem = (a%b).abs
 if rem == 0 then
   return b
 else
   return mcd(b,rem)
 end
end

puts mcd(110,44)
puts mcd(110,33)
puts mcd(110,-33)
puts mcd(33,-110)