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.


C#, Unity and DataLisp

Hello there!

After experimenting with Qt and finite elements I started to play around with C# two months ago due to the Unity Engine. Many of my games need some kind of configuration files and I love my DataLisp implementation (and it does his job well), so I decided to implement the DataLisp standard (v.1) in C#. To be honest, it was really easy and the code got much lighter, due to the help of the .NET/Mono framework. If you want to take a look. I have a C# Repository on GitHub.

More Information about DataLisp and his C++ and C# implementation can you find in his own project page.

See ya!


Sampling

Hi everybody!

Some updates about my current project. PearRay!

It’s yet another ray tracer with pure focus on spectral rendering and global illumination.
In the future I will post more information about the development process and the underlying principles and my own problems with it. Today some inside pics to the (broken) sampling procedure. Continue reading


GitHub transfer

Howdy,

after a long time of just student works, I transferred nearly all of my public repositories to GitHub.
You can find me here. All my public repositories are listed there as well :)

I hope I will be able to work on my hobby projects soon. It’s getting a bit boring only doing student tasks.

Regards,

Ömercan




University

It’s been a long time since I wrote my last post…….. Much has changed.

I’m now a student at the University of Heidelberg. I’m studying Computer Science and do not know how much time I can now spend now on my blog. I do not think that I either spent that much time here, but I do not want to abandon my blog. I will write some post from time to time about my studies and everything else on my mind.

Sorry for the long time of nothing. Hope I invest more time in :/

Regards

PearCoding




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