"built-in" c++ command for gcd?

there is no standard implementation of those ...

but there is one in boost ... which is almost as good ...

www.boost.org

Ok thanks. Like I said though my purpose for not using the one contained in boost is (well I implied) that we can only use standard libraries that come with a c++ compiler because the code must be run on another machine. I just find it kind of interesting that c++ has so many features but standard libraries do not implement what I would think is a simple function.

Check this:


Or just read the wiki pages:
http://en.wikipedia.org/wiki/Binary_GCD_algorithm

Common Lisp includes gcd in it's language standard...

A shorter gcd:
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

A good optimizing compiler will create the same code.

Thats why I have written "a good optimizing compiler".

VC++ 8.0 does it, GCC 3.4 too

Quote:

Original post by Anonymous Poster In fact, there are a number of subtle issues that make it hard to optimise in c/c++.

There are. Modern compilers don't tend to have trouble with tail-call-optimizing functions like this which have no aliasing, though.

Thank you for your replies everyone. Some of you went well beyond what I was asking but it gave me ideas on how to improve on the time of the existing Euclid's method implementation that I had in my head. On that note, however, if I wanted to calculate the lcm of two numbers, would there be any computationally quicker method than simply dividing a*b by gcd(a, b)? The calculation of a*b might be an unnecessary task if a and b differ by maybe 1 or 2 factors out of many.