Bitwise Int32_Add Proof-Of-Concept

Author Topic: Bitwise Int32_Add Proof-Of-Concept  (Read 1908 times)

I just realized that there's not technically anything stopping us from using Torque's full range of Int32 values other than the math operators being horrible. Bitwise operators still work fine for large (integral) values.


function Int32_Add(%inA, %inB)
{
   //%sign = -214748364;   //I have no idea how to do signed bitwise math
   //%signA = %inA & %sign;
   //%signB = %inB & %sign;
   %bit = 1;   //Start with the first bit
   for(%i=0;%i<31;%i++)   //This should be unrolled (for loops are inefficient) but I'm lazy
   {
      %bitA = %inA & %bit;   //Does the first value have this bit?
      %bitB = %inB & %bit;   //Does the second?
      %val = (%bitA != 0) + (%bitB != 0) + %carry;   //Get the full-add value
      %carry = (%val & 2) != 0;   //The carry bit
      if(%val & 1)   //If the value's lowest-order bit is true,
         %out |= %bit;   //add the bit to the output.
      %bit <<= 1;   //Shift the current bit up one.
   }
   $Int32::CarryFlag = %carry;   //For anyone who gives a stuff
   return %out;   //Return the value
}



This is just a proof of concept and shouldn't be used for actual projects. If anyone better at bitwise math than I wants to help out, please do.

Especially for the signed math, which I am absolutely stumped on how to do using bitwise operations. :/

Quote
(Read 57 times)
57 people aren't nerdy enough to understand this

Could someone do a performance test on this compared to regular torque integers?

Could someone do a performance test on this compared to regular torque integers?

Generating 100k pairs of random numbers (via getRandom(0, 999999)) took 9.82 µs per pair.
Adding 100k pairs of numbers (via A + B) took 5.93 µs per operation.
Adding 100k pairs of numbers (via Int32_Add(A, B)) took 43.37 µs per operation.

So the default addition operator is seven times faster, but only operates on up to six decimal places of precision, while this one can operate on only positive integers but can do so across the whole Int32 range.

So the default addition operator is seven times faster, but only operates on up to six decimal places of precision, while this one can operate on only positive integers but can do so across the whole Int32 range.
Alright, thank you very much.

Simple proof that all Torque integers are signed 32-bit ints, and the only thing preventing us from normally using the full range are the operators:

==>echo(0xFFFFFFF);
268435455
==>echo(0xEFFFFFFF);
-268435457
==>echo(1 << 30);
1073741824
==>echo((1 << 30) - 1);
1.07374e+009

Simple proof that all Torque integers are signed 32-bit ints, and the only thing preventing us from normally using the full range are the operators:
-snip-
Or you can just do echo(23489689579069057845734768923 47604903598345907247602390568 2390682390768350589232306831);
and observe that the result has 9 digits instead of the usual 6

If the operators are the only problem, I think it would be quite easy for the game to support 32-bit ints, would it not?

Or you can just do echo(23489689579069057845734768923 47604903598345907247602390568 2390682390768350589232306831);
and observe that the result has 9 digits instead of the usual 6

Wouldn't that be parsed as a string and include all the digits? Eh, maybe not.

Wouldn't that be parsed as a string and include all the digits? Eh, maybe not.
I actually looked into it and it correctly retains a whole bunch of the least significant binary digits, so yeah. Using this fact I'm going to hopefully be able to speed up a lot of my math code by quite a bit.

Also, I'm pretty sure this works too, instead all of the loops and stuff that you're doing:

return (%num1 + %num2) | 0;

EDIT: just checked, doing (any number) | 0 gives the full int32 version of it. This is actually a pretty big deal.

EDIT2: I did a speed check on 10,000,000 iterations of adding two 9-digit numbers. Just plain adding them together takes 142ns each, while using (a+b)|0 gives 134ns each.

Interesting.
« Last Edit: December 13, 2013, 01:30:25 PM by Ipquarx »

why doesn't badspot just code in some big num library ._.

why doesn't badspot just code in some big num library ._.

==>echo((999999 * 16) | 0);
15999984


there you go
it loses precision very quickly though, for example when using fractions

999999 * 16.54 = (999999 * 16) - 1

what specifically is happening there, port?

(number times a number) logical OR zero

what? how does that make it work properly?

It's probably just an oddity in TorqueScript where the bitwise OR causes the number (which is just a string) to be displayed in regular notation rather than scientific. Normally, the engine must multiply everything correctly behind the scenes, it's just that when it comes time to display the number, it converts it into scientific notation.

what specifically is happening there, port?

(number times a number) logical OR zero

what? how does that make it work properly?
It's not logical OR, it's bitwise OR.
It seems when addition/subtraction/multiplication is used on integers, by default it uses int32 arithmetic, and using the bitwise operator just converts the string to it's proper form.
On fractions or anything involving division it switches to floating point arithmetic which quickly looses precision. (This can be easily verified by dividing 200003 by two and seeing the result has no .5)
« Last Edit: December 14, 2013, 04:09:49 PM by Ipquarx »