3.1. Addition

Serial numbers may be incremented by the addition of a positive integer n, where n is taken from the range of integers [0 .. (2^(SERIAL_BITS - 1) - 1)]. For a sequence number s, the result of such an addition, s', is defined as

s' = (s + n) modulo (2 ^ SERIAL_BITS) where the addition and modulus operations here act upon values that are non-negative values of unbounded size in the usual ways of integer arithmetic.

Addition of a value outside the range [0 .. (2^(SERIAL_BITS - 1) - 1)] is undefined.

3.2. Comparison

Any two serial numbers, s1 and s2, may be compared. The definition of the result of this comparison is as follows.

For the purposes of this definition, consider two integers, i1 and i2, from the unbounded set of non-negative integers, such that i1 and s1 have the same numeric value, as do i2 and s2. Arithmetic and comparisons applied to i1 and i2 use ordinary unbounded integer arithmetic.

Then, s1 is said to be equal to s2 if and only if i1 is equal to i2, in all other cases, s1 is not equal to s2.

s1 is said to be less than s2 if, and only if, s1 is not equal to s2, and

(i1 < i2 and i2 - i1 < 2^(SERIAL_BITS - 1)) or (i1 > i2 and i1 - i2 > 2^(SERIAL_BITS - 1))

s1 is said to be greater than s2 if, and only if, s1 is not equal to s2, and

(i1 < i2 and i2 - i1 > 2^(SERIAL_BITS - 1)) or (i1 > i2 and i1 - i2 < 2^(SERIAL_BITS - 1))

Note that there are some pairs of values s1 and s2 for which s1 is not equal to s2, but for which s1 is neither greater than, nor less than, s2. An attempt to use these ordering operators on such pairs of values produces an undefined result.

The reason for this is that those pairs of values are such that any simple definition that were to define s1 to be less than s2 where (s1, s2) is such a pair, would also usually cause s2 to be less than s1, when the pair is (s2, s1). This would mean that the particular order selected for a test could cause the result to differ, leading to unpredictable implementations.

While it would be possible to define the test in such a way that the inequality would not have this surprising property, while being defined for all pairs of values, such a definition would be unnecessarily burdensome to implement, and difficult to understand, and would still allow cases where

s1 < s2 and (s1 + 1) > (s2 + 1)

which is just as non-intuitive.

Thus the problem case is left undefined, implementations are free to return either result, or to flag an error, and users must take care not to depend on any particular outcome. Usually this will mean avoiding allowing those particular pairs of numbers to co-exist.

The relationships greater than or equal to, and less than or equal to, follow in the natural way from the above definitions.

4. Corollaries

These definitions give rise to some results of note.

4.1. Corollary 1

For any sequence number s and any integer n such that addition of n to s is well defined, (s + n) >= s. Further (s + n) == s only when n == 0, in all other defined cases, (s + n) > s.

4.2. Corollary 2

If s' is the result of adding the non-zero integer n to the sequence number s, and m is another integer from the range defined as able to be added to a sequence number, and s" is the result of adding m to s', then it is undefined whether s" is greater than, or less than s, though it is known that s" is not equal to s.

4.3. Corollary 3

If s" from the previous corollary is further incremented, then there is no longer any known relationship between the result and s.

4.4. Corollary 4

If in corollary 2 the value (n + m) is such that addition of the sum to sequence number s would produce a defined result, then corollary 1 applies, and s" is known to be greater than s.