This content originally appeared on Level Up Coding - Medium and was authored by Dan McLeran
Introduction
One way to find the greatest common divisor of 2 numbers is Euclid’s algorithm. Khan Academy has a great description here. The basic algorithm is:
- Start with 2 non-zero numbers A and B, where A ≥ B.
- Using modulo, find the remainder, R.
- If R == 0, then we’re done and the answer is B.
- If R != 0, then repeat the algorithm assigning B -> A and R->B.
The recursive nature of this algorithm is perfect for C++ template metaprogramming. Using this technique, we can have the C++ compiler do this math for us. I’m not sure how useful this is in practice, but it gives one a quick tutorial on C++ templates and the power of using them to make calculations at compile-time.
Cloning The Repository
To inspect this code and try the program for yourself, you can clone the repo here: https://github.com/danmcleran/euclid.git
GCD Parent Struct
We start by defining the top-level struct which we want users to instantiate and use:
You’ll notice that we’re using the C++11 constexpr specifier. This ensures that all of our calculations are occurring at compile-time. There will be no runtime overhead for these calculations. We will prove this to ourselves later by inspecting the assembly language output.
The first 2 lines within the struct gcd:
Ensure that we select the greater of the 2 template parameters (M, N) as value 1. We then set value2 to be the value ≤ value1. This is a little helper to ensure that our lhs is ≥ our rhs before we call into our gcd implementation, which happens on the very next line:
This is the line which kicks off the recursive template instantiations to perform the GCD calculation.
GCD Implementation
To make this template more user-friendly, we provide the template specializations in a struct called:
This structure as well as its specializations are provided to struct gcd as a convenience. The parent struct handles calculating the division remainder as well as the recursive template instantiations.
Template Specializations
We have a partial template specialization to prevent division by 0:
If the recursive template instantiations try to instantiate a template where N == 0, this specialization will intervene and return the answer, GCD == M.
We have another partial template specialization which intercepts when M == 0:
When M == 0, the GCD result will be == 0.
One last explicit template specialization is need to halt the recursive template instantiations. We need a specialization for when both M and N are == 0:
With the above specializations, we can calculate Euclid’s GCD algorithm using C++ template metaprogramming.
Example Program
Now that we have our templates sorted out, we can use them to calculate the GCD using Euclid’s algorithm.
Building The Example
We’ll use g++ to build the example program:
g++ -o euclid -std=c++11 euclid.cpp
We specify C++ 11 to ensure constexpr behaves as expected.
Running The Example
When we run the example, we should see the following output:
GCD of 0, 0 = 0
GCD of 6, 4 = 2
GCD of 36, 24 = 12
GCD of 270, 192 = 6
GCD of 4, 6 = 2
GCD of 24, 36 = 12
GCD of 192, 270 = 6
You can see that we get the same results no matter the order of template arguments.
Inspecting The Assembly
To ensure we’re not incurring runtime overhead, we can generate the assembly output for inspection. On Linux we do this:
objdump -S --disassemble euclid > euclid.lst
You’ll see that the values are being loaded directly into registers during program execution:
...
9f5: be 02 00 00 00 mov $0x2,%esi
9fa: 48 89 c7 mov %rax,%rdi
9fd: e8 9e fd ff ff callq 7a0 <_ZNSolsEm@plt>
a02: 48 89 c2 mov %rax,%rdx
a05: 48 8b 05 c4 15 20 00 mov 0x2015c4(%rip),%rax
...
a2a: be 0c 00 00 00 mov $0xc,%esi
a2f: 48 89 c7 mov %rax,%rdi
a32: e8 69 fd ff ff callq 7a0 <_ZNSolsEm@plt>
a37: 48 89 c2 mov %rax,%rdx
...
Notice where we’re loading the values of 0x2 and 0xc directly into microprocessor registers:
...
9f5: be 02 00 00 00 mov $0x2,%esi
...
a2a: be 0c 00 00 00 mov $0xc,%esi
This is the result of our template metaprogramming.
Conclusion
C++ templates can do some pretty cool stuff via C++ template metaprogramming. While this may be something of a toy program, this demonstrates the mechanics that most template metaprograms use.
Euclid’s GCD Using C++ Templates was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Dan McLeran
Dan McLeran | Sciencx (2021-03-07T02:27:32+00:00) Euclid’s GCD Using C++ Templates. Retrieved from https://www.scien.cx/2021/03/07/euclids-gcd-using-c-templates/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.