0
$\begingroup$

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?

  • 0
    What do you mean by "decomposing" an expression into another when there are values where the two expression _give different results_?2012-10-13

1 Answers 1

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.

  • 0
    @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)?2013-07-04