Help: overflow with (a*b) mod c
Okay, I am using MIPS 32... but it doesnt really matter since i just want to deal with this issue in a more abstract level (relevant to probably every assembly lang, although i am no expert).
Anyways: the problem - compute r=(a*b) mod c
input restrictions: 0<=a,b,c<2^31 and c is non-zero
for any of you not familiar with mod, u=v mod w means u is the non-negative remainder you get when you divide v by w.
that means r<c and the output fits in a 32-bit register.
The problem is with overflow. a*b can be as many as 64-bits (the case i am interested in). computing a mod c and b mod c may not help at all since they can still be over 32-bits. note that if we want to compute u=v mod w, and v is 32-bits, it only takes 2 instructions (divide, get result). but in this case... the best algorithm i've implemented takes around 800 instructions. is there a fast and savvy way to do this efficiently?
technical details, when multiply in MIPS, the result is stored in two registers, HI and Lo, and Hi contains the higher order 32-bits and Lo contains lower order 32-bits of the product. thats probalby all u need to know about mips.
Re: Help: overflow with (a*b) mod c
Quote:
Originally Posted by bugzpodder
Okay, I am using MIPS 32... but it doesnt really matter since i just want to deal with this issue in a more abstract level (relevant to probably every assembly lang, although i am no expert).
Anyways: the problem - compute r=(a*b) mod c
input restrictions: 0<=a,b,c<2^31 and c is non-zero
for any of you not familiar with mod, u=v mod w means u is the non-negative remainder you get when you divide v by w.
that means r<c and the output fits in a 32-bit register.
The problem is with overflow. a*b can be as many as 64-bits (the case i am interested in). computing a mod c and b mod c may not help at all since they can still be over 32-bits. note that if we want to compute u=v mod w, and v is 32-bits, it only takes 2 instructions (divide, get result). but in this case... the best algorithm i've implemented takes around 800 instructions. is there a fast and savvy way to do this efficiently?
technical details, when multiply in MIPS, the result is stored in two registers, HI and Lo, and Hi contains the higher order 32-bits and Lo contains lower order 32-bits of the product. thats probalby all u need to know about mips.
I think I've got the jist of what you're saying. Basically you're trying to do math that has numbers larger then the registers you have correct? You only have a couple of options off the top of my head, thats either backdown on the size of the numbers you're working with to get them inside the register or do the math with strings. It's a lot of work doing it the string way but you won't have the restrictions on you're number size.
Re: Help: overflow with (a*b) mod c
I reverse engineered some code almost exactly like this.
The original code was:
enc = (pos2+pos1)%74 + 48; //pos2, pos1, and enc can be of type int.
The actually assembly looks like this:
Code:
mov eax,DWORD PTR [ebp-12]
mov ecx,DWORD PTR [ebp-8]
add ecx,eax
mov eax,0xdd67c8a7
imul ecx
lea eax,[edx+ecx*1]
mov edx,eax
sar edx,0x6
mov eax,ecx
sar eax,0x1f
sub edx,eax
mov eax,edx
shl eax,0x3
add eax,edx
shl eax,0x2
add eax,edx
add eax,eax
sub ecx,eax
mov eax,ecx
add eax,0x30
mov DWORD PTR [ebp-16],eax
The magic happens with the imul ecx, which puts 32 bits of the high byte into edx and 32 bits of the low byte into eax.
Converting it back into C++ gives us:
enc = pos2+pos1-(((long long)pos2+pos1)*0xdd67c8a7>>38)*74+48;
Type "long long" gives us the needed 64 bits. But due to the insaine shifting... you actually can return a value that would fit in INT... not a Long Long! This is pretty much the magic behind the % and assembly.
I don't know if this is of any use... or leads you to any ideas. I know nothing of MIPS.
Re: Help: overflow with (a*b) mod c
Instead of computing (a*b) mod m, you can compute it like this, which will be slower, but will not overflow.
Psuedocode Example:
Code:
integer a = 43, b = 77;
integer m = 16;
integer result = 0;
integer i;
for(i = 0; i < b; i = i + 1)
begin
result = result + a;
result = result mod m;
end
// result is now the result of the statement (a*b) mod m
