Home › C++ Templates: Euclid's Algorithm

Reply to comment

C++ Templates: Euclid's Algorithm

Mon, 2008-03-24 21:57 — jason

A while back I was going though the first chapters of Knuth's The Art of Computer Programming and came across Euclid's algorithm for finding the greatest common denominator. I decided to implement the algorithm as a C++ template. Here's the complete example.

#include <iostream>
 
using namespace std;
 
template <int M, int N>
struct Euclids
{
  enum { value = Euclids<N, M%N>::value };
};
 
template <int N>
struct Euclids<N, 0>
{
  enum { value = N };
};
 
int main(int, char *[])
{
  cout << "GCD: 5,4: " << Euclids<5,4>::value << endl;
  cout << "GCD: 10, 5: " << Euclids<10, 5>::value << endl;
  cout << "GCD: 18, 8: " << Euclids<18, 8>::value << endl;
  cout << "GCD: 894744, 2312: " << Euclids<894744, 2312>::value << endl;
  cout << "GCD: 100, 10000: " << Euclids<100, 10000>::value << endl;
  cout << "GCD: 40, 50: " << Euclids<40,50>::value << endl;
}

Reply

The content of this field is kept private and will not be shown publicly.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd> <blockquote>
  • Lines and paragraphs break automatically.
  • You may post PHP code. You should include <?php ?> tags.
  • Web page addresses and e-mail addresses turn into links automatically.
  • You can enable syntax highlighting of source code with the following tags: <code>, <blockcode>, <cpp>. The supported tag styles are: <foo>, [foo]. PHP source code can also be enclosed in <?php ... ?> or <% ... %>.
  • Images can be added to this post.

More information about formatting options

CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
3 + 14 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.