Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Rest assured, it makes sense in context. Assume positive values only.

How do I calculate (((i * j) modulo 2^64) / k) modulo 2^64 and get the same result as ( (i * j) / k ) modulo 2^64?

share|improve this question
    
Please reveal the context this makes sense in. Do you mean you want conditions on $i$, $j$, and $k$ that will guarantee this? $k=\pm 1$ or $ij < 2^{64}$ ought to do it. –  Henning Makholm Oct 13 '12 at 20:37
    
They are congruent mod $2^{64}$. So it suffices to normalize them, i.e. pick some canonical system of residue representatives (e.g. least positive residues), then normalize the result so that it lies in that range. –  Bill Dubuque Oct 13 '12 at 20:42
    
Sorry; I need to decompose the first equation into a series of equations which, when a set of i, j and k numbers are run through them, give the same final result as the second equation. –  Narf the Mouse Oct 13 '12 at 20:50
    
What do you mean by "decomposing" an expression into another when there are values where the two expression give different results? –  Henning Makholm Oct 13 '12 at 20:58
add comment

1 Answer 1

Note that $ij=u+k2^{64}$ where $0<=u<2^{64}$ You want to divide $ij$ or $u$ by $k$ mod $2^{64}$ so choose some $k'$ inverse to $k$, i.e. $kk'=1$ mod $2^{64}$.

Now it seems you want the calculation $uk'$ to give the same result as $ijk'$ mod $2^{64}$. This will of course happen automatically, in that the same results mod $2^{64}$ will occur for each. But if it happens that $k>0$ the two numbers, $uk'$ and $ijk'$, will be different, obviously. I think you can't do what you want, without having some kind of access to the value of $k$ (the number of times $2^{64}$ has to be added to $u$ to obtain $ij$).

Put simply: you can't just use the numbers $i,j,k$ and some chosen constants mod $2^{64}$ to do what you want. You'll need to use also an intermediate variable computed from the two numbers $i,j$. So you won't have a formula, just a procedure.

share|improve this answer
    
A procedure is fine. Sorry, got caught up in stuff. –  Narf the Mouse Oct 27 '12 at 3:03
    
@NarftheMouse Are you still wondering how to set up such a procedure, or have you already figured one out (since Oct 14 was a while ago)? –  coffeemath Jul 4 '13 at 15:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.