# User talk:NevilleDNZ/GeSHi sandbox

This task requires the finding of the greatest common divisor of two integers.

```with Ada.Text_Io; use Ada.Text_Io;

procedure Gcd_Test is
function Gcd (A, B : Integer) return Integer is
begin
if A = 0 then
return B;
end if;
if B = 0 then
return A;
end if;
if A > B then
return Gcd(B, A mod B);
else
return Gcd(A, B mod A);
end if;
end Gcd;

begin
Put_Line("GCD of 100, 5 is" & Integer'Image(Gcd(100, 5)));
Put_Line("GCD of 5, 100 is" & Integer'Image(Gcd(5, 100)));
Put_Line("GCD of 7, 23 is" & Integer'Image(Gcd(7, 23)));
end Gcd_Test;
```

```GCD of 100, 5 is 5
GCD of 5, 100 is 5
GCD of 7, 23 is 1
```

## ALGOL 68

<algol-68>

```PROC gcd = (INT a, b) INT: (
IF a = 0 THEN
b
ELIF b = 0 THEN
a
ELIF a > b  THEN
gcd(b, a MOD b)
ELSE
gcd(a, b MOD a)
FI
);

main : (
INT a = 33, b = 77;
printf((\$x"The gcd of"g" and "g" is "gl\$,a,b,gcd(a,b)));
INT c = 49865, d = 69811;
printf((\$x"The gcd of"g" and "g" is "gl\$,c,d,gcd(c,d)))
)
```

</algol-68> The output is:

```The gcd of        +33 and         +77 is         +11
The gcd of     +49865 and      +69811 is       +9973
```

## C

### Iterative Euclid algorithm

<c>

```int
gcd_iter(int u, int v) {
int t;
while (v) {
t = u;
u = v;
v = t % v;
}
return u < 0 ? -u : u; /* abs(u) */
}
```

</c>

### Recursive Euclid algorithm

<c>

```int
gcd(int u, int v) {
if (v)
return gcd(v, u % v);
else
return u < 0 ? -u : u; /* abs(u) */
}
```

</c>

### Iterative binary algorithm

<c> int gcd_bin(int u, int v) {

``` int t, k;
```
``` u = u < 0 ? -u : u; /* abs(u) */
v = v < 0 ? -v : v;
if (u < v) {
t = u;
u = v;
v = t;
}
if (v == 0)
return u;
```
``` k = 1;
while (u & 1 == 0 && v & 1 == 0) { /* u, v - even */
u >>= 1; v >>= 1;
k <<= 1;
}
```
``` t = (u & 1) ? -v : u;
while (t) {
while (t & 1 == 0)
t >>= 1;
```
```   if (t > 0)
u = t;
else
v = -t;
```
```   t = u - v;
}
return u * k;
```

} </c>

### Notes on performance

`gcd_iter(40902, 24140)` takes us about 2.87 usec

`gcd_bin(40902, 24140)` takes us about 2.47 usec

`gcd(40902, 24140)` takes us about 2.86 usec

## Forth

<forth>

```: gcd ( a b -- n )
begin dup while tuck mod repeat drop ;
```

</forth>

## Fortran

### Iterative Euclid algorithm

<fortran>

```      subroutine gcd_iter(value, u, v)
Cf2py integer intent(out) :: value
integer value, u, v, t
intrinsic abs, mod
C
do while( v.NE.0 )
t = u
u = v
v = mod(t, v)
enddo
value = abs(u)
end subroutine gcd_iter
```

</fortran>

### Iterative binary algorithm

<fortran>

```      subroutine gcd_bin(value, u, v)
Cf2py integer intent(out) :: value
integer value, u, v, k, t, abs, mod
intrinsic abs, mod
u = abs(u)
v = abs(v)
if( u.lt.v ) then
t = u
u = v
v = t
endif
if( v.eq.0 ) then
value = u
return
endif
k = 1
do while( (mod(u, 2).eq.0).and.(mod(v, 2).eq.0) )
u = u / 2
v = v / 2
k = k * 2
enddo
if( (mod(u, 2).eq.0) ) then
t = u
else
t = -v
endif
do while( t.ne.0 )
do while( (mod(t, 2).eq.0) )
t = t / 2
enddo
if( t.gt.0 ) then
u = t
else
v = -t
endif
t = u - v
enddo
value = u * k
end subroutine gcd_bin
```

</fortran>

### Notes on performance

`gcd_iter(40902, 24140)` takes us about 2.8 usec

`gcd_bin(40902, 24140)` takes us about 2.5 usec

<j>

```x+.y
```

</j>

## Java

### Iterative

<java>

```public static long gcd(long a, long b){
long factor= 0;
factor= Math.max(a, b);
for(long loop= factor;loop > 1;loop--){
if(a % loop == 0 && b % loop == 0){
return loop;
}
}
return 1;
}
```

</java>

### Recursive

<java>

```public static long gcd(long a, long b){
if(a == 0) return b;
if(b == 0) return a;
if(a > b) return gcd(b, a % b);
return gcd(a, b % a);
}
```

</java>

## OCaml

<OCaml>

```let rec gcd a b =
if      a = 0 then b
else if b = 0 then a
else if a > b then gcd b (a mod b)
else               gcd a (b mod a)
```

</OCaml>

## Perl

### Iterative Euclid algorithm

<perl>

```sub gcd_iter(\$\$) {
(\$u, \$v) = @_;
while (\$v) {
\$t = \$u;
\$u = \$v;
\$v = \$t % \$v;
}
return abs(\$u);
}
```

</perl>

### Recursive Euclid algorithm

<perl>

```sub gcd(\$\$) {
(\$u, \$v) = @_;
if (\$v) {
return gcd(\$v, \$u % \$v);
} else {
return abs(\$u);
}
}
```

</perl>

### Iterative binary algorithm

<perl>

```sub gcd_bin(\$\$) {
(\$u, \$v) = @_;
\$u = abs(\$u);
\$v = abs(\$v);
if (\$u < \$v) {
\$t = \$u;
\$u = \$v;
\$v = \$t;
}
if (\$v == 0) {
return \$u;
}
\$k = 1;
while (\$u & 1 == 0 && \$v & 1 == 0) {
\$u >>= 1;
\$v >>= 1;
\$k <<= 1;
}
\$t = (\$u & 1) ? -\$v : \$u;
while (\$t) {
while (\$t & 1 == 0) {
\$t >>= 1;
}
if (\$t > 0) {
\$u = \$t;
} else {
\$v = -\$t;
}
\$t = \$u - \$v;
}
return \$u * \$k;
}
```

</perl>

### Notes on performance

<perl>

```use Benchmark qw(cmpthese);

\$u = 40902;
\$v = 24140;
(-5, {
'gcd' => sub { gcd(\$u, \$v); },
'gcd_iter' => sub { gcd_iter(\$u, \$v); },
'gcd_bin' => sub { gcd_bin(\$u, \$v); },
});
```

</perl> Output on 'Intel(R) Pentium(R) 4 CPU 1.50GHz' / Linux / Perl 5.8.8:

```             Rate  gcd_bin gcd_iter      gcd
gcd_bin  321639/s       --     -12%     -20%
gcd_iter 366890/s      14%       --      -9%
gcd      401149/s      25%       9%       --
```

## Python

### Iterative Euclid algorithm

<python>

```def gcd_iter(u, v):
while v:
u, v = v, u % v
return abs(u)
```

</python>

### Recursive Euclid algorithm

Interpreter: Python 2.5 <python>

```def gcd(u, v):
return gcd(v, u % v) if v else abs(u)
```

</python>

### Tests

```>>> gcd(0,0)
0
>>> gcd(0, 10) == gcd(10, 0) == gcd(-10, 0) == gcd(0, -10) == 10
True
>>> gcd(9, 6) == gcd(6, 9) == gcd(-6, 9) == gcd(9, -6) == gcd(6, -9) == gcd(-9, 6) == 3
True
>>> gcd(8, 45) == gcd(45, 8) == gcd(-45, 8) == gcd(8, -45) == gcd(-8, 45) == gcd(45, -8) == 1
True
>>> gcd(40902, 24140) # check Knuth :)
34
```

### Iterative binary algorithm

See The Art of Computer Programming by Knuth (Vol.2)> <python>

```def gcd_bin(u, v):
u, v = abs(u), abs(v) # u >= 0, v >= 0
if u < v:
u, v = v, u # u >= v >= 0
if v == 0:
return u

# u >= v > 0
k = 1
while u & 1 == 0 and v & 1 == 0: # u, v - even
u >>= 1; v >>= 1
k <<= 1

t = -v if u & 1 else u
while t:
while t & 1 == 0:
t >>= 1
if t > 0:
u = t
else:
v = -t
t = u - v
return u * k
```

</python>

### Notes on performance

`gcd(40902, 24140)` takes us about 17 usec

`gcd_iter(40902, 24140)` takes us about 11 usec

`gcd_bin(40902, 24140)` takes us about 41 usec