Highest Common Factor

[Frederick Gotham]

Anyone want to give me a hand to write efficient algorithms for Highest
Common Factor and Lowest Common Multiple? This is what I have so far...

Caveat: I haven't gone over the following code in detail, so there might be
a subtle bug lurking somewhere.

unsigned HCF(unsigned const a, unsigned const b)
{
unsigned bigger,smaller;

register unsigned hcf;

if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;

if ( !(bigger%smaller) ) return smaller;

hcf = smaller-1;

while (a%hcf || b%hcf) --hcf;

return hcf;
}

Any ideas to make it more efficient?

Here's what I've got for Lowest Common Multiple:

unsigned LCM(unsigned const a,unsigned const b)
{
unsigned bigger,smaller,max;

register unsigned lcm;

if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;

if ( !(bigger%smaller) ) return bigger;

max = (unsigned)-1 - bigger;

if (bigger > max) return 0;

lcm = bigger<<1;

while(lcm%a || lcm%b)
{
if (lcm > max) return 0;
lcm += bigger;
}

return lcm;
}

Any ideas to make it more efficient?

 

[nachch]

Anyone want to give me a hand to write efficient algorithms for Highest
Common Factor and Lowest Common Multiple? This is what I have so far...

Caveat: I haven't gone over the following code in detail, so there might be
a subtle bug lurking somewhere.

unsigned HCF(unsigned const a, unsigned const b)
{
unsigned bigger,smaller;

register unsigned hcf;

if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;

if ( !(bigger%smaller) ) return smaller;

hcf = smaller-1;

while (a%hcf || b%hcf) --hcf;

return hcf;

}Any ideas to make it more efficient?

Here's what I've got for Lowest Common Multiple:

unsigned LCM(unsigned const a,unsigned const b)
{
unsigned bigger,smaller,max;

register unsigned lcm;

if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;

if ( !(bigger%smaller) ) return bigger;

max = (unsigned)-1 - bigger;

if (bigger > max) return 0;

lcm = bigger<<1;

while(lcm%a || lcm%b)
{
if (lcm > max) return 0;
lcm += bigger;
}

return lcm;

}Any ideas to make it more efficient?

For hcf (AKA gcd, greatest common divisor), read about Euclid's
algorithm (http://en.wikipedia.org/wiki/Euclidean_algorithm).

 

[bert]

Anyone want to give me a hand to write efficient algorithms for Highest
Common Factor and Lowest Common Multiple? This is what I have so far...

Caveat: I haven't gone over the following code in detail, so there might be
a subtle bug lurking somewhere.

I haven't got access to a C compiler anymore, but I used
Knuth's binary algorithm when I needed this function.

unsigned HCF (unsigned a, unsigned b)
{
int za, zb, zr;

if (a == 0 || b == 0)
return a + b;

za = zb = 0;
while ((a & 1) == 0)
{
a >>= 1; ++za;
}
while ((b & 1) == 0)
{
b >>= 1; ++zb;
}
zr = za > zb ? zb : za;

/* odd HCF of two odd numbers (Knuth) */
while (a != b)
{
if (a > b)
{
a -= b;
do
a >>= 1;
while ((a & 1) == 0);
}
else
{
b -= a;
do
b >>= 1;
while ((b & 1) == 0);
}
} /* end Knuth */

while (zr)
{
a <<= 1; --zr;
}

return a;
}
--

 

[gw7rib]

For hcf (AKA gcd, greatest common divisor), read about Euclid's
algorithm (http://en.wikipedia.org/wiki/Euclidean_algorithm).

Indeed, Euclid's algorithm seems the best way to go, unless you want to
try factorising the numbers. Note that you can modify the algorithm
slightly whereby instead of calculating a%b (which will be in the range
0 to b-1 inclusive) you allow negative numbers to give a result in the
range -b/2 to b/2. This guarentees that b is halving in magnitude each
time so places a log bound on the running time.

For lcm, note that hcf * lcm = product of the two numbers, so you can
re-use the hcf routine.

Hope this helps.
Paul.

 

[Julian V. Noble]

Anyone want to give me a hand to write efficient algorithms for Highest
Common Factor and Lowest Common Multiple? This is what I have so far...

Caveat: I haven't gone over the following code in detail, so there might be
a subtle bug lurking somewhere.

unsigned HCF(unsigned const a, unsigned const b)
{
unsigned bigger,smaller;

register unsigned hcf;

if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;

if ( !(bigger%smaller) ) return smaller;

hcf = smaller-1;

while (a%hcf || b%hcf) --hcf;

return hcf;
}

Any ideas to make it more efficient?

Here's what I've got for Lowest Common Multiple:

unsigned LCM(unsigned const a,unsigned const b)
{
unsigned bigger,smaller,max;

register unsigned lcm;

if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;

if ( !(bigger%smaller) ) return bigger;

max = (unsigned)-1 - bigger;

if (bigger > max) return 0;

lcm = bigger<<1;

while(lcm%a || lcm%b)
{
if (lcm > max) return 0;
lcm += bigger;
}

return lcm;
}

Any ideas to make it more efficient?

Several gcd programs in C can be found at

http://galileo.phys.virginia.edu/classes/551.jvn.fall01/Cprogs.htm

Look at item #4.

 

[Afghan Hound]

Anyone want to give me a hand to write efficient algorithms for Highest
Common Factor and Lowest Common Multiple? This is what I have so far...

Caveat: I haven't gone over the following code in detail, so there might be
a subtle bug lurking somewhere.

unsigned HCF(unsigned const a, unsigned const b)
{
unsigned bigger,smaller;

register unsigned hcf;

if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;

if ( !(bigger%smaller) ) return smaller;

hcf = smaller-1;

while (a%hcf || b%hcf) --hcf;

return hcf;
}

Any ideas to make it more efficient?

You may find this one useful:

long gcd(long a, long b)
{
long c;

if (b==0)
return a; /*so that gcd(5,0) should work*/

/*****Euclidean algorithm*****/
while ((c=a%b))
{
a = b;
b = c;
}

return b;
}

 

[Elijah Cardon]

Anyone want to give me a hand to write efficient algorithms for Highest
Common Factor and Lowest Common Multiple? This is what I have so far...

Caveat: I haven't gone over the following code in detail, so there might
be
a subtle bug lurking somewhere.

unsigned HCF(unsigned const a, unsigned const b)
{
unsigned bigger,smaller;

register unsigned hcf;

if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;

if ( !(bigger%smaller) ) return smaller;

hcf = smaller-1;

while (a%hcf || b%hcf) --hcf;

return hcf;
}

Any ideas to make it more efficient?

Here's what I've got for Lowest Common Multiple:

unsigned LCM(unsigned const a,unsigned const b)
{
unsigned bigger,smaller,max;

register unsigned lcm;

if (a>b) bigger=a,smaller=b;
else bigger=b,smaller=a;

if ( !(bigger%smaller) ) return bigger;

max = (unsigned)-1 - bigger;

if (bigger > max) return 0;

lcm = bigger<<1;

while(lcm%a || lcm%b)
{
if (lcm > max) return 0;
lcm += bigger;
}

return lcm;
}

Any ideas to make it more efficient?

I doubt it. OTOH, if Dr. Knuth looked at this, he wouldn't get it. On the
first hand, this source executes so lightning fast that to argue about its
speed would be to argue about the comparative speed of light in various
media.

My question is, using an appropriate caller, how large a number can this
work for? EC

 

[mensanator]

I doubt it. OTOH, if Dr. Knuth looked at this, he wouldn't get it. On the
first hand, this source executes so lightning fast that to argue about its
speed would be to argue about the comparative speed of light in various
media.

Really?

Doesn't the execution time of

while (a%hcf || b%hcf) --hcf;

double every time the smaller operand increases by 1 bit?

My question is, using an appropriate caller, how large a number can this
work for? EC

Can it do (assuming appropriate data types)

a: 2**177149-1 b: 2**19685-1 ?

 

[Spiros Bousbouras]

Anyone want to give me a hand to write efficient algorithms for Highest
Common Factor and Lowest Common Multiple? This is what I have so far...

Caveat: I haven't gone over the following code in detail, so there might be
a subtle bug lurking somewhere.

unsigned HCF(unsigned const a, unsigned const b)
<SNIP>

Any ideas to make it more efficient?

Here's what I've got for Lowest Common Multiple:

unsigned LCM(unsigned const a,unsigned const b)
<SNIP>

Any ideas to make it more efficient?

If you want to calculate both HCF (usually called
greatest common divisor) and LCM for the same
pair of numbers a,b then you can use the formula
LCM(a,b) = (a*b)/HCF(a,b) This should be faster than
calling both of your functions.

 

[Guest]

If you want to calculate both HCF (usually called
greatest common divisor) and LCM for the same
pair of numbers a,b then you can use the formula
LCM(a,b) = (a*b)/HCF(a,b) This should be faster than
calling both of your functions.

It's better to use LCM(a,b) = a*(b/HCF(a,b)). This avoids one potential
for overflow, and there can't be a rounding error since the result of
HCF() by definition is a factor of b.

 

[Elijah Cardon]

Really?

Doesn't the execution time of

while (a%hcf || b%hcf) --hcf;

double every time the smaller operand increases by 1 bit?

Ask Dr. Knuth and he'll tell you it's time for lunch.

Can it do (assuming appropriate data types)

a: 2**177149-1 b: 2**19685-1 ?

I wish my life consisted of choosing the lesser of these evils. The second
looks like a distractor to me. What would callers look like? EC