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,smalle r=b;
else bigger=b,smalle r=a;

if ( !(bigger%smalle r) ) 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,smalle r=b;
else bigger=b,smalle r=a;

if ( !(bigger%smalle r) ) 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?

--

Frederick Gotham

[nachch@gmail.com]

Re: Highest Common Factor

On Oct 23, 11:01 pm, Frederick Gotham <fgotha...@SPAM .comwrote:

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,smalle r=b;
else bigger=b,smalle r=a;
>
if ( !(bigger%smalle r) ) 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,smalle r=b;
else bigger=b,smalle r=a;
>
if ( !(bigger%smalle r) ) 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).
--
Nachch

[bert]

Re: Highest Common Factor

Frederick Gotham wrote:

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@aol.com]

Re: Highest Common Factor

nachch@gmail.co m wrote:

On Oct 23, 11:01 pm, Frederick Gotham <fgotha...@SPAM .comwrote:

Anyone want to give me a hand to write efficient algorithms for Highest
Common Factor and Lowest Common Multiple?

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]

Re: Highest Common Factor

Frederick Gotham wrote:

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,smalle r=b;
else bigger=b,smalle r=a;
>
if ( !(bigger%smalle r) ) 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,smalle r=b;
else bigger=b,smalle r=a;
>
if ( !(bigger%smalle r) ) 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.

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

[Afghan Hound]

Re: Highest Common Factor

Frederick Gotham wrote:

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,smalle r=b;
else bigger=b,smalle r=a;
>
if ( !(bigger%smalle r) ) 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]

Re: Highest Common Factor


"Frederick Gotham" <fgothamNO@SPAM .comwrote in message
news:j4a%g.1514 7$j7.332700@new s.indigo.ie...

>
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,smalle r=b;
else bigger=b,smalle r=a;
>
if ( !(bigger%smalle r) ) 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,smalle r=b;
else bigger=b,smalle r=a;
>
if ( !(bigger%smalle r) ) 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@aol.com]

Re: Highest Common Factor


Elijah Cardon wrote:

"Frederick Gotham" <fgothamNO@SPAM .comwrote in message
news:j4a%g.1514 7$j7.332700@new s.indigo.ie...

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,smalle r=b;
else bigger=b,smalle r=a;

if ( !(bigger%smalle r) ) 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,smalle r=b;
else bigger=b,smalle r=a;

if ( !(bigger%smalle r) ) 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.

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]

Re: Highest Common Factor

Frederick Gotham wrote:

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.

[Harald van Dijk]

Re: Highest Common Factor

Spiros Bousbouras wrote:

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]

Re: Highest Common Factor


<mensanator@aol .comwrote in message
news:1161711341 .519952.224390@ b28g2000cwb.goo glegroups.com.. .

>
Elijah Cardon wrote:

>"Frederick Gotham" <fgothamNO@SPAM .comwrote in message
>news:j4a%g.151 47$j7.332700@ne ws.indigo.ie...

>
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,smalle r=b;
else bigger=b,smalle r=a;
>
if ( !(bigger%smalle r) ) 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,smalle r=b;
else bigger=b,smalle r=a;
>
if ( !(bigger%smalle r) ) 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.

>
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.

>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 ?

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