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]

Re: How to write a small graceful gcd function?

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]

Re: How to write a small graceful gcd function?

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]

Re: How to write a small graceful gcd function?

"Julian V. Noble" <jvn@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) kst-u@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]

Re: How to write a small graceful gcd function?


Keith Thompson wrote:

"Julian V. Noble" <jvn@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]

Re: How to write a small graceful gcd function?

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

Keith Thompson wrote:

>"Julian V. Noble" <jvn@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) kst-u@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]

Re: How to write a small graceful gcd function?

Keith Thompson wrote:

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

Keith Thompson wrote:

"Julian V. Noble" <jvn@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]

Re: How to write a small graceful gcd function?

/*
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]

Re: How to write a small graceful gcd function?


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

[Dann Corbit]

Re: How to write a small graceful gcd function?

"Tom St Denis" <tomstdenis@gma il.comwrote in message
news:1153160856 .384561.248110@ i42g2000cwa.goo glegroups.com.. .

>
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;
}
>
:-)

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.

[Tom St Denis]

Re: How to write a small graceful gcd function?

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

[Ben Pfaff]

Re: How to write a small graceful gcd function?

"Dann Corbit" <dcorbit@connx. comwrites:

"Tom St Denis" <tomstdenis@gma il.comwrote in message
news:1153160856 .384561.248110@ i42g2000cwa.goo glegroups.com.. .

>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;
>}

[...]

Of course, it assumes 2's complement machines, but that is pretty much a
forgone conclusion now-days.

Does it need that assumption? To me it looks like all the
arithmetic is done with unsigned ints, which behave the same way
regardless of how negative integers are represented.
--
int main(void){char p[]="ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwC IxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+= strchr(p,*q++)-p;if(i>=(int)si zeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Dann Corbit]

Re: How to write a small graceful gcd function?

"Tom St Denis" <tomstdenis@gma il.comwrote in message
news:1153161567 .419653.68640@7 5g2000cwc.googl egroups.com...

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
>

/* Let me know how long this takes on your system: */

unsigned long long subtractions = 0;
unsigned long long gcd(unsigned long long a, unsigned long long b)
{
unsigned long long 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;
subtractions++;
while (!(b & 1)) { b >>= 1; }
}
return a << k;
}

unsigned long long big=12974633789 0625;
unsigned long long med=86497558593 75*7;

#include <stdio.h>
int main(void)
{
unsigned long long answer = gcd(big, med);
printf("gcd %llu and %llu = %llu\n. Number of subtractions was %llu\n",
big, med, answer, subtractions);
return 0;
}

[Dann Corbit]

Re: How to write a small graceful gcd function?

"Ben Pfaff" <blp@cs.stanfor d.eduwrote in message
news:87fyh02hr8 .fsf@benpfaff.o rg...

"Dann Corbit" <dcorbit@connx. comwrites:
>

>"Tom St Denis" <tomstdenis@gma il.comwrote in message
>news:115316085 6.384561.248110 @i42g2000cwa.go oglegroups.com. ..

>>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;
>>}

>
[...]
>

>Of course, it assumes 2's complement machines, but that is pretty much a
>forgone conclusion now-days.

>
Does it need that assumption? To me it looks like all the
arithmetic is done with unsigned ints, which behave the same way
regardless of how negative integers are represented.

Right, I was thinking of negative numbers, which this does not have to deal
with.

--
int main(void){char
p[]="ABCDEFGHIJKLM NOPQRSTUVWXYZab cdefghijklmnopq rstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwC IxNJC";int i=sizeof p/2;char *strchr();int
putchar(\
);while(*q){i+= strchr(p,*q++)-p;if(i>=(int)si zeof p)i-=sizeof
p-1;putchar(p[i]\
);}return 0;}

[Tom St Denis]

Re: How to write a small graceful gcd function?

Dann Corbit wrote:

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

Note the added &&'s.

The bug you think you noted was because the internal loop wasn't
stopping. With the fixes you get

gcd 129746337890625 and 60548291015625 = 8649755859375
.. Number of subtractions was 4

Which is what gp gives me. [Note: I *did* say it was from memory and
off the top of my head]

Tom