# Problem with modulo calculation

• 01-12-2009
manutdfan
Problem with modulo calculation
Right, am having a problem when using a modulo calculation in my program.

Trying to do the calculation below,

N = 1073741827
R = 4294967296

N' = (1/N) (mod R) = 1789569707

The code I was trying to use is below however it just gives 0 as the result, i'm guessing its something to do with the type but not sure what.
Code:

```typedef unsigned long long bigint; void method() { bigint N, R, invN; N = 1073741827; R = 4294967296; invN = (1/N) % R; }```
• 01-12-2009
Salem
> (1/N)
Integer arithmetic, anything other than 1 here will give you zero
• 01-12-2009
manutdfan
Quote:

Originally Posted by Salem
> (1/N)
Integer arithmetic, anything other than 1 here will give you zero

Yeh I guessed this was the problem, how would I go about anything other type of arithmetic to get the required result.
• 01-12-2009
Jaken Veina
Not to mention that the solution to that equation is N' = 1/N, not 1789569707...

N' = (1 / N) % R
N' = (1 / 1073741827) % R
N' = (0.00000000093132257201) % R
N' = (0.00000000093132257201) % 4294967296

0.00000000093132257201 / 4294967296 = 0 Remainder 0.00000000093132257201

So, N' = 0.00000000093132257201 = 1 / N

Somehow, I don't think that's the equation you want...However, for education's sake, a correct implementation of that equation would look something like this...

Code:

```void method(void) { double N, R, invN; N = 1073741827; R = 4294967296; invN = ((double)1/N) % R; }```
Although, there may be problems with precision. I'm not sure off-hand how well a double will be able to deal with such large (and small) numbers.
• 01-12-2009
tabstop
I take it you're looking for an inverse mod R? That is, 1073etc * 1789etc is equal to 1 mod 4294etc? That has nothing to do with %. (% is remainder; it does not do artihmetic mod whatever). You will have to actually compute it yourself, using an algorithm of some kind.
• 01-12-2009
manutdfan
Quote:

Originally Posted by tabstop
I take it you're looking for an inverse mod R? That is, 1073etc * 1789etc is equal to 1 mod 4294etc? That has nothing to do with %. (% is remainder; it does not do artihmetic mod whatever). You will have to actually compute it yourself, using an algorithm of some kind.

Yes sorry I was so unclear, that was what I wanted to do. In maple you can just type 1/N mod R and it gives the correct answer 1089etc however wasn't sure how to do this in C.

Does the extended euclidean algorithm do this? and do I enter N and R as the two variables for the function to take?

thanks for the help
• 01-12-2009
tabstop
The extended Euclidean algorithm does indeed do this. N and R are the only two variables you've got, so I suppose those are the two.