An answer to this question on Stack Overflow.

Question

This may have been asked already, but I was unable to find it on this forum. I had a general question about integer arithmetic in c++ when doing arithmetic on large integers.

unsigned int value = 500000;
value = (value * value) % 99;

The correct value to the above code would be 25, however when this is implemented in C++ I get a value of 90.

I looked at the disassembly and that gave me a slight idea as to why it may be coming back with an erroneous value, the disassembly is as follows

unsigned int value = 500000;
    00D760B5  mov         dword ptr [value],7A120h  
    value = ((value * value) % 99);
    00D760BC  mov         eax,dword ptr [value]  
    00D760BF  imul        eax,dword ptr [value]  
    00D760C3  xor         edx,edx  
    00D760C5  mov         ecx,63h  
    00D760CA  div         eax,ecx  
    00D760CC  mov         dword ptr [value],edx

It appears to be placing it into a 32 bit register, and that is why the result is coming back erroneous.

Nevertheless, my question is how can I mimic the language to give me the correct answer? I'm sure there's an easy and straightforward way to do it but I'm drawing a blank.

Answer

You should consider using a larger integer type, such as unsigned long or unsigned long long. On my machine both of these give you eight bytes of working space, which allows for a maximum value of 18,446,744,073,709,551,615. This is comfortably large enough to fit 500000^2=250,000,000,000.

But, in my opinion, that's a poor solution. You should, instead, use better mathematics. The follow modular identity should let you do what you want:

(ab) mod n = [(a mod n)(b mod n)] mod n.

In you case, you'd write:

unsigned int value = 500000;
value = ((value%99)*(value%99))%99;