Compile-Time Array Construction of Divisors (C++11)

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:

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:

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:

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:

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

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:

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:

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

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:

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.


Pear3DEngine – and now?

Pear3DEngine is a modern and modular 3D development framework that lets you create professional games, simulations and more. You are free to develop your program in C++, XML or LUA and publish it as open source software or selling it as a commercial program. The rendering engine uses internally OpenGL or DirectX optionally. The planned editor supports software development on Linux, Windows and maybe MacOS X. DirectX 9 and Windows XP are not supported and support is not planned in the future. One goal of the Pear3DEngine Framework is to use the latest and most promising algorithms and techniques from the 3D and IT scene.

This is the description of the engine that you can find on SourceForge. But why a new engine? Are there not enough in the world?

Of course, the engine is open source. But is this a right to exist? Continue reading