How to write a small graceful gcd function?

L

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/cs201/NOTES/chap04/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;
}

lovecreatesbeauty
 
N

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
 
J

Julian V. Noble

lovecreatesbeauty said:
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/cs201/NOTES/chap04/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;
}

lovecreatesbeauty

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

Keith Thompson

Julian V. Noble said:
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);
}
}
 
L

lovecreatesbeauty

Keith said:
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;
}

lovecreatesbeauty
 
K

Keith Thompson

lovecreatesbeauty said:
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.
 
L

lovecreatesbeauty

Keith said:
lovecreatesbeauty said:
Keith said:
[...]
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
$

lovecreatesbeauty
 
D

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

Tom St Denis

lovecreatesbeauty said:
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
 
D

Dann Corbit

Tom St Denis said:
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.
 
T

Tom St Denis

Dann said:
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
 
B

Ben Pfaff

Dann Corbit said:
Tom St Denis said:
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.
 
D

Dann Corbit

Tom St Denis said:
Dann said:
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=129746337890625;
unsigned long long med=8649755859375*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;
}
 
D

Dann Corbit

Ben Pfaff said:
Dann Corbit said:
Tom St Denis said:
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[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int
putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof
p-1;putchar(p\
);}return 0;}
 
T

Tom St Denis

Dann said:
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
 
D

Dann Corbit

Dann Corbit said:
Tom St Denis said:
Dann said:
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; }

Better use:
while (b && !(b & 1)) { b >>= 1; }

Or there will be problems.
 
D

Dann Corbit

/*
Now that I actually understand how it works, I like the subtraction trick a
lot better. In this instance, (lots of small repeated factors) it takes the
same number of iterations as the modulo version
*/
unsigned long long modulos = 0;
unsigned long long subtractions = 0;
unsigned long long gcdm(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;
modulos++;
while (b && !(b & 1)) { b >>= 1; }
}
return a << k;
}
unsigned long long gcds(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 && !(b & 1)) { b >>= 1; }
}
return a << k;
}
unsigned long long big=129746337890625;
unsigned long long med=8649755859375*7;

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

Tom St Denis

Tom said:
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]

Of course a=0 will kill this too. So the fix would be

unsigned gcd(unsigned a, unsigned b)
{
unsigned k, t;
if (!a) return b;
if (!b) return a;

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 ;
while (b && !(b & 1)) { b >>= 1; }
}
return a<<k;
}

That iterates a max of log_2(max(a,b)) times. It's fully linear time.
Whereas the division way is quadratic [unless you get into interpolated
divisions...]

Tom
 
D

Dann Corbit

Tom St Denis said:
Tom said:
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]

Of course a=0 will kill this too. So the fix would be

unsigned gcd(unsigned a, unsigned b)
{
unsigned k, t;
if (!a) return b;
if (!b) return a;

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 ;
while (b && !(b & 1)) { b >>= 1; }
}
return a<<k;
}

That iterates a max of log_2(max(a,b)) times. It's fully linear time.
Whereas the division way is quadratic [unless you get into interpolated
divisions...]

How can the division way be quadratic? It takes out repeated factors in
every iteration. The above example takes 2 modulus cycles.

gcdm 129746337890625 and 60548291015625 = 8649755859375
.. Number of modulos was 2
gcds 129746337890625 and 60548291015625 = 8649755859375
.. Number of subtractions was 2

C:\tmp>factor 60548291015625
first trying brute force division by small primes
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 7

C:\tmp>factor 129746337890625
first trying brute force division by small primes
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 3
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
PRIME FACTOR 5
 
B

Ben Pfaff

Dann Corbit said:
/*
Now that I actually understand how it works, I like the subtraction trick a
lot better. In this instance, (lots of small repeated factors) it takes the
same number of iterations as the modulo version
*/

Are we talking about the same binary GCD algorithm that's in
Knuth? There's a wikipedia page about it:
http://en.wikipedia.org/wiki/Binary_GCD_algorithm

(Every algorithm is in Knuth if you look hard enough.)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top