Calculating the divisor of a number N is an easy task. For example the divisors of the number 2048 can be easily calculated by the following source code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
#include <type_traits> #include <iostream> #include <list> #include <cmath> template<typename T> std::list<T> list_of_divisors(T number) { static_assert(std::is_integral<T>::value, "T must be an integral type"); std::list<T> result; if(number < 1) return result; int sq = (int)std::floor(std::sqrt(number)) + 1; for(int i = sq; i > 0; --i) { if(number % i == 0) { result.push_front(i); if(i != number / i) { result.push_back(number / i); } } } return result; } int main(int argc, char** argv) { int N = 2048; std::list<int> result = list_of_divisors(N); for(int a : result) std::cout << a << " "; std::cout << std::endl; return 0; } |

The result is:

1 2 4 8 16 32 64 128 256 512 1024 2048

It was calculated on runtime. But does it have to be calculated on runtime? If the number N (like a compile time constant) is known beforehand there is no need for that. We need a solution purely determined on compile time.

But stop! It’s all right to ask the question:

Is there a case for a compile time constant where we also need the divisors – but runtime is a no go?

I think most of the time a runtime solution is fine. But now my case:

I have a predefined constant called `SAMPLING_COUNT`

, which is pretty much is the accuracy of a spectrum. To divide the spectrum into equal sized intervals based on the quality factor `Q`

(determined on runtime) I have to use the divisors of `SAMPLING_COUNT`

.

Now still; does it have to be on compile time? I have to admit, no, it would be completely fine to calculate it on runtime. But when I have the possibility to calculate it on compile time, I will just do it. Maybe you can find a good reason?

The following solution is capable of calculating the divisors of small numbers and returning them in a sorted constant array. It uses C++11 features and was tested on:

1 2 |
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.4) clang version 3.8.0-2ubuntu4 (tags/RELEASE_380/final) |

Remember to add the switch `--std=c++11`

as a parameter for GCC and `-std=c++11`

for clang++.

Before we dig into the divisor class we need a constexpr variant of std::sqrt. The C++14 already has one; but due to the fact that nearly all of my own projects have the C++11 baseline and C++14 support is incomplete for MSVC, I wrote my own std::sqrt integer variant:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// sqrt using binary search method template<typename T> class t_sqrt { static_assert(std::is_integral<T>::value, "T must be an integral type"); static constexpr T _helper(T v, T low, T high) { return (low == high ? low : ((v / (low + high + 1) < (low + high + 1) / 4) ? _helper(v, low, (low + high + 1)/2 - 1) : _helper(v, (low + high + 1)/2, high)) ); } public: static constexpr T value(T v) { return v > 0 ? _helper(v, 0, v / 2 + 1) : (T)0; } t_sqrt() = delete; t_sqrt(const t_sqrt&) = delete; t_sqrt(t_sqrt&&) = delete; }; |

It is not that fancy as std::sqrt, as it has to be called this way:

int v = t_sqrt<int>::value(4); // == 2

An easy task for the reader would be to change the interface to the well known std::sqrt one, without exposing the internal _helper function to the public.

Now with our `t_sqrt`

function we are able to build the divisor (builder) class:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
template <int N> class Divisor { static_assert(N >= 1, "N must be at least 1"); // First initialization public: static constexpr auto number = N; static constexpr auto sqrt_number = t_sqrt<int>::value(number) + 1; // Stuff comes here [....] // Utils public: Divisor() = delete; Divisor(const Divisor&) = delete; Divisor(Divisor&&) = delete; }; |

First of it would be nice to know how long the produced array will be. We will calculate it with a recursive function:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// [...] private: static constexpr int calc_length(int i) { return ((i == 0) ? 0 : calc_length(i-1) + ((number % i == 0) ? ((number / i == i) ? 1 : 2) : 0 ) ); } public: static constexpr auto length = calc_length(sqrt_number); // [...] |

The recursive function is pretty straightforward, as it calculates the divisors and only increases the total count when a divisor or divisor pair was found. A faster variant, but only after calculating the array, would be to use the line:

sizeof(Divisor<N>::values)/sizeof(int)

I do not like this style but you are free to use what ever variant you want.

To construct the array we need an array building template specialization. It is nearly the same as a recursive function with an explicit end:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// [...] private: // Recursive body // M is like i in our loop, it decreases from sqrt_number to 0 // Rest is the array we build template<int M, int... Rest> struct Impl { // std::coditional resembles an ? expression: // 'cond ? T1 : T2' -> std::conditional<cond, T1, T2> typedef typename std::conditional<(number % M) == 0, typename std::conditional<M == (number / M), Impl<M - 1, M, Rest...>, // Equal pair found Impl<M - 1, M, Rest..., number / M> // Two distinct elements found >::type, Impl<M - 1, Rest...>// Not a divisor >::type T; static constexpr auto& values = T::values; }; // Recursive end template<int... Rest> struct Impl<0, Rest...> { // We transform the template list to a constant array static constexpr int values[] = {Rest...}; }; public: static constexpr auto&& values = Impl<sqrt_number>::values; // [...] |

To be fair, we are pretty much done. But to use the array in actual runtime code and to make sure the array is also in the binary of the program, we need to add this line:

1 2 3 |
template<int N> template<int... Rest> constexpr int Divisor<N>::Impl<0, Rest...>::values[]; |

This is all you have to do. It is easy to use the class in runtime code:

1 2 3 4 5 6 7 8 9 10 |
int main(int argc, char** argv) { constexpr int N = 2048; typedef Divisor<N> OurDivisor; for(int i = 0; i < OurDivisor::length; ++i) std::cout << OurDivisor::values[i] << " "; std::cout << std::endl; return 0; } |

The above program produces the same line as the runtime implementation:

1 2 4 8 16 32 64 128 256 512 1024 2048

This is all. If you found some mistakes or something which is completely wrong, please comment. I’m happy to improve and open for constructive criticism. I would also be happy if someone could test the code for MSVC.

### Note:

You can construct many other algorithms with the style presented above. Like an integer sequence (see StackOverflow, as it has a lot of examples for that).

I think it would be also possible to construct a general class for a general function `f`

. But that would look ugly and would make this little example much more complicated.

A good starting point is also the Boost MPL library, as it has much more complicated examples and is not bounded to C++11 (correct me if I’m wrong).

With C++14 everything got really easy. Just read about the features. You will understand why :)

I recommend to look a the following StackOverflow questions as it also helped me to construct the divisor class:

- c++11: Create 0 to N constexpr array in c++
- The great answer from Kal was my starting point, but was only for standard integer sequences.

- Constructing const array out of constexpr

### Source

The archive divisor.zip contains the both variants/examples. The one with the _ct postfix is the compile time variant.

To see this class in production I suggest to look at the source code of my raytracer PearRay.