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;
}

---

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

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.

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.

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.

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

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.