0
$\begingroup$

I have a "clock" - a 32-bit unsigned number - that wraps around from $4,294,967,295$ ($2^{32}-1$) back to $0$.
At point 'A' in time, I stamp the clock into a variable - call it $x$.
Later, at point 'B' in time, I stamp the clock again into another variable - call it $y$.
I want to convince myself that as long as the clock hasn't been wrapped around more than once between the two points 'A' and 'B', the result of the subtraction $(y - x)$ will always give the correct result - regardless of which is bigger (the correct result being how many 'ticks' the clock has counted from 'A' to 'B').

I know that when dealing with unsigned numbers in a binary system (with two's complement arithmetic), it holds that $z = 2^N -z'\hspace{10pt}\forall z=0,1,...,2^N-1$, where $z'$ is the "negative" (i.e. the two's) complement of $z$. I feel like it's relevant, but still can't prove the above to myself...
Can someone help proving it?


Example where $N=4$:

$\begin{array}{ccccccc}0& 1& 2& 3& 4& 5& 6& 7\\ 0000& 0001& 0010& 0011& 0100& 0101& 0110& 0111\end{array}$

$\begin{array}{ccccccc}8& 9& 10& 11& 12& 13& 14& 15\\ 1000& 1001& 1010& 1011& 1100& 1101& 1110& 1111\end{array}$

$2 - 11 = -9$ which is equivalent to $7$, having only $4$ digits, and is exactly the number of ticks passed from $11$ to $2$, when considering clock wrap around.

$\endgroup$
  • $\begingroup$ You probably want $y-x$ rather than $x-y$, since $x$ is stored earlier. Anyway, you'll always get a result that is "correct modulo $2^{32}$". But you only get the correct result if there were fewer than $2^{32}$ ticks between $A$ and $B$. If at time $A$, the clock was at $10$, say, and time $B$ is $2^{32} + 10$ ticks later, the clock wrapped only once, but you get the wrong result ($10$ instead of $2^{32} + 10$). $\endgroup$ – Daniel Fischer May 12 '16 at 21:07
  • $\begingroup$ Yes, you're right. I meant y - x... Regarding the rest - I can understand the intuition, just wondered if this can be proved mathematically... $\endgroup$ – so.very.tired May 12 '16 at 22:06
0
$\begingroup$

Let $0\leq x,y\leq2^{N}-1$, s.t. $x<y$.
To show that I get the "correct result", means to show that: $(x-y)\mod2^N = 2^N-(y-x)$
(I guess that what I was having difficulty defining...).
Now if I apply $\mod 2^N$ on RHS:
$(2^N-(y-x))\mod 2^N$
$(2^N+(x-y))\mod 2^N=$
$(2^N\mod 2^N+(x-y)\mod 2^N)\mod 2^N= $
$(0 + (x-y)\mod 2^N)\mod 2^N=$
$(x-y)\mod 2^N$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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