## Deamortization – Part 1: Redundant Number Systems

In the positional number system of base b, the representation d_{n}d_{n-1}…d_{1}d_{0} denotes the number \sum_{i = 0}^{n} d_i b^i. For example, the binary (b = 2) number (1001)_2 is 8 + 1 = 9. Notice that when d_i \in {0, …, b – 1}, there is only one way to denote any number. This is what we are all used to.

In a redundant number system, we allow d_i to be chosen from a larger set of digits. For this series, we will stick to {0, …, b – 1, b}. To make things even more concrete, we further set b to 2, i.e., we are considering the redundant binary numbers with the sets of digits {0, 1, 2}.

The decimal number 9 can still be written as 1001 in binary (I am dropping the subscripts and will display binary numbers in math mode). But since we are using the redundant binary system, we also have other choices. In particular, 201 (2 * 4 + 1 = 9) and 121 (4 + 2*2 + 1 = 9) are also valid representations.

Let me introduce three terms before I continue.

• We say that a redundant binary number is regular if the 2s and 0s alternate. So 2012 is regular, but 2120 is not.
• When the last non-1 digit of a redundant binary number is 0, we say that it’s 0-exposed. For example, 2001 is 0-exposed. (But note that it is not regular.)
• When the last non-1 digit is 2, we say that it is 2-exposed. For example, 2102 is 2-exposed.

The regularity constraint is very special. First, convince yourself that even when restricting to regular representations, there are still redundancy in the representation of a number. For example, both 1202 and 1210 denote 18 and both of which are regular since the 2s and the 0s alternate.

Also note that if a number is either 2-exposed or 0-exposed.

The only operation that we will consider in this post is:

• add 1 to the least significant digit of a number (i.e., the rightmost)

We will denote this operation with an intuitive expression. For example, consider 12(1+1). That would be 122. Easy, huh?

Let’s repeat the operation one more time. Hmm, 12(2+1) would be 123, but that wouldn’t be too good since 3 is not an allowed digit. Well, we need carry. 123 = 131 = 211. OK, problem solved.

At this point, make sure you know how to do this add-one-to-the-last-digit operation.

For those of us that own the whole series of the Worst-Case Scenario Survival Handbook , you will have noticed that this operation can take time linear to the number of digits. Consider the input 22222222222222222(2+1). Oh no!

This is where the regularity constraint comes in. Suppose the number you start with is regular. How long can add-1 take? Consider the last digit of the number.

• If it’s a 0 or 1, then you can just bump it up to 1 or 2 respectively.
• If it’s a 2, then we need to carry 1 to the next digit (to the left). Ah! But since the number is regular, that digit cannot be a 2. The previous case now applies.

So in at most two steps, we will be done. That’s like O(1) time, right?

But, we may not be left with a regular number any more. For example, 12(1+1) is 122 and that’s not regular. The key observation is that we will end up with an irregular number if we start with a 2-exposed regular number. So we never want to increment a 2-exposed number.

The claim is that you can convert a 2-exposed number into a 0-exposed equivalent in O(1) time if you know where the rightmost 2 is. Let the number be written as xy2z, where z is the sequence of digits to the right of the rightmost 2, y is the digit immediate to the left of it, and x is the sequence to the left of y. Due to the regularity constraint, note that z must be all 1s if it is not null, and y only has two possibilities:

• x02z = x10z
x must be 2-exposed, so x10z is regular.
• x12z = x20z
x must be 0-exposed, so x20z is regular.

And both of these are 0-exposed and we know adding 1 to them takes O(1) time.

The remaining issue is how we know where the rightmost 2 is. This is easy. We maintain a stack of the locations of the 2s, with the rightmost on the top of the stack. Verify that the above two fixing operations both operate at the top of the stack.

Now do you understand how to add 1 in O(1) time?

Indeed, if the number is 2-exposed, fix it to become 0-exposed first. And we know that adding 1 to a 0-exposed number is easy.

But why am I telling you about redundant number systems? That would be the subject of Part 2.