How to write a small graceful gcd function?

[lovecreatesbeauty]

My small function works, but I have some questions. And I want to
listen to you on How it is implemented?

1. The function does not check if parameter x is larger or smaller than
parameter y.

2. Is it better to use unsigned int or unsigned long as the type of
parameters x and y? This change may remove the if statement.

More comments are still welcome.

/*The Greatest Common Divisor, GCD for short, of two positive integers
can be computed with Euclid's division algorithm. Let the given numbers
be a and b, a >= b. Euclid's division algorithm has the following
steps:
1. Compute the remainder c of dividing a by b.
2. If the remainder c is zero, b is the greatest common divisor.
3. If c is not zero, replace a with b and b with the remainder c. Go
back to step (1).

http://www.cs.mtu.edu/~shene/COURSES...hap04/gcd.html */

/*computes the GCD (Greatest Common Divisor) of positive integers x and
y with Euclid's algorithm. return the GCD, or -1 for failure. - jhl,
Jul 2006*/

int gcd(int x, int y){
if (x 0 && y 0){
while (x % y){
y = x + y;
x = y - x;
y = (y - x) % x;
}
} else {
y = -1; /*input invalid*/
}
return y;
}

lovecreatesbeau ty

[Nabsha]

Hi,

/*The Greatest Common Divisor, GCD for short, of two positive integers
can be computed with Euclid's division algorithm. Let the given numbers
be a and b, a >= b. Euclid's division algorithm has the following
steps:
1. Compute the remainder c of dividing a by b.
2. If the remainder c is zero, b is the greatest common divisor.
3. If c is not zero, replace a with b and b with the remainder c. Go
back to step (1).

int gcd (unsigned int a, unsigned int b)
{
unsigned int c;

if ( !a && !b )
return -1;

if (a b)
{
c = a;
a = b;
b = c;
}
while( (c=a%b) 0 )
{
a = b;
b = c;
}
return b;
}

Similar code in fortran is also available on the link u gave but I
could not understand why you have done this:

y = x + y;
x = y - x;
y = (y - x) % x;

Regards,

Nabeel Shaheen

lovecreatesbeau ty wrote:

My small function works, but I have some questions. And I want to
listen to you on How it is implemented?

1. The function does not check if parameter x is larger or smaller than
parameter y.

2. Is it better to use unsigned int or unsigned long as the type of
parameters x and y? This change may remove the if statement.

More comments are still welcome.

/*The Greatest Common Divisor, GCD for short, of two positive integers
can be computed with Euclid's division algorithm. Let the given numbers
be a and b, a >= b. Euclid's division algorithm has the following
steps:
1. Compute the remainder c of dividing a by b.
2. If the remainder c is zero, b is the greatest common divisor.
3. If c is not zero, replace a with b and b with the remainder c. Go
back to step (1).

http://www.cs.mtu.edu/~shene/COURSES...hap04/gcd.html */

/*computes the GCD (Greatest Common Divisor) of positive integers x and
y with Euclid's algorithm. return the GCD, or -1 for failure. - jhl,
Jul 2006*/

int gcd(int x, int y){
if (x 0 && y 0){
while (x % y){
y = x + y;
x = y - x;
y = (y - x) % x;
}
} else {
y = -1; /*input invalid*/
}
return y;
}

lovecreatesbeau ty

[Julian V. Noble]

lovecreatesbeau ty wrote:

My small function works, but I have some questions. And I want to
listen to you on How it is implemented?

1. The function does not check if parameter x is larger or smaller than
parameter y.

2. Is it better to use unsigned int or unsigned long as the type of
parameters x and y? This change may remove the if statement.

More comments are still welcome.

/*The Greatest Common Divisor, GCD for short, of two positive integers
can be computed with Euclid's division algorithm. Let the given numbers
be a and b, a >= b. Euclid's division algorithm has the following
steps:
1. Compute the remainder c of dividing a by b.
2. If the remainder c is zero, b is the greatest common divisor.
3. If c is not zero, replace a with b and b with the remainder c. Go
back to step (1).

http://www.cs.mtu.edu/~shene/COURSES...hap04/gcd.html */

/*computes the GCD (Greatest Common Divisor) of positive integers x and
y with Euclid's algorithm. return the GCD, or -1 for failure. - jhl,
Jul 2006*/

int gcd(int x, int y){
if (x 0 && y 0){
while (x % y){
y = x + y;
x = y - x;
y = (y - x) % x;
}
} else {
y = -1; /*input invalid*/
}
return y;
}

lovecreatesbeau ty

int gcd( int m, int n ) // recursive
{
if(n==0) { return m; }
else
{ int answer = gcd(n,m%n);
return answer; }
}


--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia

[Keith Thompson]

"Julian V. Noble" <jv*@virginia.e duwrites:
[...]

int gcd( int m, int n ) // recursive
{
if(n==0) { return m; }
else
{ int answer = gcd(n,m%n);
return answer; }
}

The temporary is unnecessary, and the formatting is just odd. Here's
how I'd write it:

int gcd(int m, int n)
{
if (n == 0) {
return m;
}
else {
return gcd(n, m % n);
}
}

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[lovecreatesbeauty]

Keith Thompson wrote:

"Julian V. Noble" <jv*@virginia.e duwrites:
[...]

int gcd( int m, int n ) // recursive
{
if(n==0) { return m; }
else
{ int answer = gcd(n,m%n);
return answer; }
}

The temporary is unnecessary, and the formatting is just odd. Here's
how I'd write it:

int gcd(int m, int n)
{
if (n == 0) {
return m;
}
else {
return gcd(n, m % n);
}
}

Thanks.

The function accepts zeros and negative integers as their arguments.
How are users without much mathematical knowledge like me supposed to
provide correct input to use it?

If compare an integer with zero value, will the following changes be
better?

1.

/*...*/ /*some necessary check*/

if (!n) {
return m;
} else {
return gcd(n, m % n);
}

2.

/*...*/ /*some necessary check*/

if (n) {
return gcd(n, m % n);
} else {
return m;
}

lovecreatesbeau ty

[Keith Thompson]

"lovecreatesbea uty" <lo************ ***@gmail.comwr ites:

Keith Thompson wrote:

>"Julian V. Noble" <jv*@virginia.e duwrites:
[...]

int gcd( int m, int n ) // recursive
{
if(n==0) { return m; }
else
{ int answer = gcd(n,m%n);
return answer; }
}

The temporary is unnecessary, and the formatting is just odd. Here's
how I'd write it:

int gcd(int m, int n)
{
if (n == 0) {
return m;
}
else {
return gcd(n, m % n);
}
}

Thanks.

The function accepts zeros and negative integers as their arguments.
How are users without much mathematical knowledge like me supposed to
provide correct input to use it?

The obvious solution to that is to change the arguments and result
from int to unsigned.

Different mathematical functions have different domains and ranges
(values that make sense for arguments and results). C, unlike some
other languages, doesn't let you declare a type with a specified range
of values -- but in this case, unsigned happens to be just what you
want.

If compare an integer with zero value, will the following changes be
better?

1.

/*...*/ /*some necessary check*/

if (!n) {
return m;
} else {
return gcd(n, m % n);
}

2.

/*...*/ /*some necessary check*/

if (n) {
return gcd(n, m % n);
} else {
return m;
}

In my opinion, not at all. Using "if (n)" or "if (!n)" makes sense if
n is a condition, something that can be logically true or false.
Here, n is a numeric value; comparing it to 0 isn't checking whether
it's true or false, it's just comparing it to 0.

It means exactly the same thing to the compiler, of course, but
clarity for the human reader is just as important.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <* <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[lovecreatesbeauty]

Keith Thompson wrote:

"lovecreatesbea uty" <lo************ ***@gmail.comwr ites:

Keith Thompson wrote:

"Julian V. Noble" <jv*@virginia.e duwrites:
[...]
int gcd( int m, int n ) // recursive
{
if(n==0) { return m; }
else
{ int answer = gcd(n,m%n);
return answer; }
}

The temporary is unnecessary, and the formatting is just odd. Here's
how I'd write it:

int gcd(int m, int n)
{
if (n == 0) {
return m;
}
else {
return gcd(n, m % n);
}
}

Thanks.

The function accepts zeros and negative integers as their arguments.
How are users without much mathematical knowledge like me supposed to
provide correct input to use it?

The obvious solution to that is to change the arguments and result
from int to unsigned.

Different mathematical functions have different domains and ranges
(values that make sense for arguments and results). C, unlike some
other languages, doesn't let you declare a type with a specified range
of values -- but in this case, unsigned happens to be just what you
want.

The recursive way becomes the worst one and can not be improved to add
more parameter validation to it. If the function accepts input from
other automatic software systems, then someone should still keep an eye
on it, because the result may be wrong without warning.

int gcd(int x, int y){
if (x 0 && y 0){
while (x % y){
y = x + y;
x = y - x;
y = (y - x) % x;
}
} else {
y = -1; /*input invalid*/
}
return y;
}

int gcd3(int m, int n){
if (n == 0){
return m;
} else {
return gcd3(n, m % n);
}
}

$ ./a.out
gcd(8, 8): 8
gcd3(8, 8): 8
$ ./a.out
gcd(0, 8): -1
gcd3(0, 8): 8
$ ./a.out
gcd(8, 0): -1
gcd3(8, 0): 8
$

lovecreatesbeau ty

[Dann Corbit]

/*
The small and graceful versions are not as robust as those that
use a bit more code and also perform some sanity checks.
IMO-YMMV.
*/
/*
recursive variants:
*/
/* Recursive, using Knuth's subtraction trick: */
int gcd(int a, int b)
{
return a == b ? a : a b ? gcd(b, a - b) : gcd(b, b - a);
}
/* Recursive via simplest definition: */
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
/* Slight variant of one directly above: */
int gcd(int a, int b)
{
if (!b)
return a;
return gcd(b, a % b);
}

/*
Iterative variants:
*/
/* Iterative version with Knuth's subtraction method: */
int gcd(int a, int b)
{
while (a) {
if (a < b) {
int t = a;
a = b;
b = t;
}
a = a - b;
}
return b;
}
/* Iterative via fundamental definition: */
int gcd(int a, int b)
{
while (b) {
int t = b;
b = a % b;
a = t;
}
return a;
}
/* Not quite as safe as version directly above this one: */
int gcd(int a, int b)
{
do {
int r = a % b;
a = b;
b = r;
} while (b);
return a;
}
/* Sanity checks tossed in (a good idea): */
int gcd(int a, int b)
{
int t;
if (a < b)
t = a;
else
t = b;
while (a % t || b % t)
t = t - 1;
return t;
}

/*
With a few tricks and using a bigger type:
*/
/*************** *************** *************** **********/
/* This function uses the Euclidean Algorithm to */
/* calculate the greatest common divisor of two long */
/* double floating point numbers. */
/*************** *************** *************** **********/
/* Programmer: Danniel R. Corbit */
/* */
/* Copyright (C) 1992 by Danniel R. Corbit */
/* All rights reserved. */
/*************** *************** *************** **********/
/* Reference: "Factorizat ion and Primality Testing", */
/* by David M. Bressoud, */
/* Springer-Verlag 1989. */
/* pages 7-12. */
/*************** *************** *************** **********/
#include <math.h>
long double ldGcd(long double a, long double b)
{
int shiftcount = 0;
long double tmp;
int i;
/*************** *************** *************** *************** *******/
/* This zero testing stuff may seem odd, since zero is not likely. */
/* However, knowing that neither a nor b is zero will speed up */
/* later operations greatly by elimination of tests for zero. */
/*************** *************** *************** *************** *******/
if (a == 0.0e0L)
{
tmp = b;
}
else if (b == 0.0e0L)
{
tmp = a;
}
else /* Neither a NOR b is zero! */
{
/* Absolute values used. */
a = a 0.0e0L ? a : -a;
b = b 0.0e0L ? b : -b;

/*************** *************** *************** *************** **/
/* While all this fuss about numbers divisible by 2 may seem */
/* like quite a bother, half of the integers in the universe */
/* are evenly divisible by 2. Hence, on a random sample of */
/* input values, great benefit will be realized. The odds */
/* that at least one of a,b is even is 1 - (1/2)*(1/2) = .75 */
/* since the probability that both are odd is .25. */
/*************** *************** *************** *************** **/
/* If a & b are divisible by 2, gcd(a,b) = 2*gcd(a/2,b/2). */
/*************** *************** *************** *************** **/
while (fmodl(a,2.0e0L ) == 0.0e0L && fmodl(b,2.0e0L) == 0.0e0L)
{
a /= 2.0e0L;
b /= 2.0e0L;
shiftcount++;
}

/*************** *************** *************** *************** **/
/* If the a is divisible by 2 and b is not divisible by 2, */
/* then gcd(a,b) = gcd(a/2,b). */
/*************** *************** *************** *************** **/
while (fmodl(a,2.0e0L ) == 0.0e0L)
{
a /= 2.0e0L;
}

/*************** *************** *************** **********/
/* If b is divisible by 2 and a is not divisible by 2, */
/* then gcd(a,b) = gcd(a,b/2). */
/*************** *************** *************** **********/
while (fmodl(b,2.0e0L ) == 0.0e0L)
{
b /= 2.0e0L;
}

/*************** *************** *************** *************** **********/
/* Make sure the numbers are in the proper order (swap if necessary).
*/
/*************** *************** *************** *************** **********/
if (b a)
{
tmp = a;
a = b;
b = tmp;
}

/*************** *************** **********/
/* Euclid's famous gcd algorithm: */
/* Iterate until the remainder is <= 1. */
/*************** *************** **********/
while (b 1.0e0L)
{
tmp = b;
b = fmodl(a,b);
a = tmp;
}
if (b == 0.0e0L)
tmp = a;
else
tmp = b;

/*************** *************** *************** *************** ***********/
/* If we divided BOTH numbers by factors of 2, we must compensate now.
*/
/*************** *************** *************** *************** ***********/
if (shiftcount 0 && tmp 0.0e0L)
for (i = 0; i < shiftcount; i++)
tmp += tmp;
}
return (tmp);
}

[Tom St Denis]

lovecreatesbeau ty wrote:

My small function works, but I have some questions. And I want to
listen to you on How it is implemented?

Divisions are for chumps...

unsigned gcd(unsigned a, unsigned b)
{
unsigned k, t;

k = 0;
while (!(a & 1 || b & 1)) {
++k; a >>= 1; b >>= 1;
}
while (!(a & 1)) { a >>= 1; }
while (!(b & 1)) { b >>= 1; }

while (b) {
if (a b) { t = a; a = b; b = t; }
b = b - a;
while (!(b & 1)) { b >>= 1; }
}
return a << k;
}

:-)

[untested, from memory, from my book too...]

Tom

[Tom St Denis]

Dann Corbit wrote:

I guess that most of the time repeated subtraction will not be faster than
division with modern processors. I do like this implementation, though.
Of course, it assumes 2's complement machines, but that is pretty much a
forgone conclusion now-days.

if b a and b has k bits then you loop at most k times [hint: b - a is
always either even or zero]

So are 16, 32 or 64 subtractions/shifts faster than a small set of
divisions? Most likely yes, specially on things like an ARM. It
really depends on the numbers and the platform.

Also my code doesn't link in the division support [for processors that
lack a divider] so it's a bit more compact. It's also Kernel save
[using divisions in the Kernel last I heard was a no no].

Tom