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
    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.2012-10-13
  • 0
    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.2012-10-13
  • 0
    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.2012-10-13
  • 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
    A procedure is fine. Sorry, got caught up in stuff.2012-10-27
  • 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