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$
2
  • $\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$ Commented May 12, 2016 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$ Commented May 12, 2016 at 22:06

1 Answer 1

Reset to default
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)$

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$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.