StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POEfficient 128-bit addition using carry flag
text
Body
copied!<p>I'm using a 128 bit integer counter in the very inner loops of my C++ code. (Irrelevant background: The actual application is evaluating finite difference equations on a regular grid, which involves repetitively incrementing large integers, and even 64 bits isn't enough precision because small rounding accumulates enough to affect the answers.)</p> <p>I've represented the integer as two 64 bit unsigned longs. I now need to increment those values by a 128 bit constant. This isn't hard, but you have to manually catch the carry from the low word to the high word.</p> <p>I have working code something like this:</p> <pre><code>inline void increment128(unsigned long &hiWord, unsigned long &loWord) { const unsigned long hiAdd=0x0000062DE49B5241; const unsigned long loAdd=0x85DC198BCDD714BA; loWord += loAdd; if (loWord < loAdd) ++hiWord; // test_and_add_carry hiWord += hiAdd; } </code></pre> <p>This is tight and simple code. It works.</p> <p>Unfortunately this is about 20% of my runtime. The killer line is that loWord test. If I remove it, I obviously get the wrong answers but the runtime overhead drops from 20% to 4%! So that carry test is especially expensive!</p> <p>My question: Does C++ expose the hardware carry flags, even as an extension to GCC? It seems like the additions could be done without the test-and-add-carry line above if the actual compiled instructions used an add using last carry instruction for the hiWord addition. Is there a way to rewrite the test-and-add-carry line to get the compiler to use the intrinsic opcode?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload