Thread: Modulo 12

Review the generated assembler, determine its inefficiencies, and code your own optimized inline assembler.

Originally Posted by EVOEx

I seriously doubt you can make anything faster than what is probably a single instruction to the CPU. Especially if you compile with full optimization, you're not going to get anything faster.

In fact, I think C++ is generally faster than assembly language, as the compiler can better understand a lot of optimization techniques that are practically impossible for humans to apply correctly: for instance mixing up certain instructions so that memory read/writes are further apart - but how many instructions should be in between to be able to be as fast as possible? I have no idea on that. In fact, I think it even depends on the number of clock cycles it takes for the instructions between the memory accessing.

I know that, and you know that, but the OP needs to figure this out.

Some very useful links for this:
http://www.hackersdelight.org/divcMore.pdf
Bit Tricks, Part I: Exact Division

No the problem is that you've misinterpreted the code. There is not supposed to be any floats whatsoever in the program, just a few precalculated integer constants.
Admittedly, it is totally unclear what inverse(7) means in that code (it's just some other integer constant).
I should have time to try it out myself later.

Okay, I worked out what inverse(7) is for this example. It is 2454267027 which comes from:

Code:

ceil((((1<<32) % 7)<<32) / 7)

613566756 is

Code:

floor((1<<32) / 7)

Try the following code:

Code:

#include <iostream>
#include <cmath>

int main()
{
	double total = 0;
	for (unsigned int i = 0; i < 100000000; ++i) {
		if (i * 2454267027 <= 613566756)
			total += i;
	}
	std::cout << total << std::endl;
}

That should give the same answer and be faster than the i%7 version. Note that a great deal of the time will probably be spent on the total += i; line because that requires an int to double conversion. If you really want to see how much quicker it is, you'll need to change i and total to unsigned int in both versions.

Note that for this hack for i%7, it only works up to 858993461 (0x33333335)
It can be tested basically like this:

Code:

for (unsigned int i=0; i<=858993461; ++i) {
    bool t1 = (i % 7) == 0;
    bool t2 = i * 2454267027 <= 613566756;
    assert(t1 == t2);
}

Appliying this technique to the original mod 12 problem. The following is one solution to if (n % 12 == 0):

Code:

if (!(n & 3) && n * 1431655766 <= 1431655765)

The extra !(n & 3) test is because this technique only works on odd numbers, so it's actually doing a test for n%3 in that multiplication, not n%12
Note that it works only up to 2147483647 (0x7FFFFFFF), and it's up to you to test the performance difference.

I just realised that you actually need the result of the modulus rather than just testing it against zero, so I still recommend going through both of the above articles, and working it out from that.

Originally Posted by EVOEx

@iMalc:
The results still differ for me

Impossible! My units tests prove conclusively that they give the same answers all the way up the the limits I stated:

Code:

TESTMETHOD(TestMod7)()
{
	for (unsigned int i=0; i<0x33333336; ++i) {
		bool t1 = (i % 7) == 0;
		bool t2 = i * 2454267027U <= 613566756U;
		ASSERT(t1 == t2);
	}
}

TESTMETHOD(TestMod12)()
{
	for (unsigned int i=0; i<0x80000000; ++i) {
		bool t1 = (i % 12) == 0;
		bool t2 = !(i & 3) && i * 1431655766U <= 1431655765U;
		ASSERT(t1 == t2);
	}
}

I've also checked, that the U makes no difference, and there's no undefined behaviour here either, since unsigned overflow behaviour is defined.
Works on VS2008 and MinGW 5.1.6.
If the above fails on your compiler then I'd be inclined to start digging into assembly and figuring out what is wrong with the compiler, though perhaps you simply copied it down wrong.