ArtsAutosBooksBusinessEducationEntertainmentFamilyFashionFoodGamesGenderHealthHolidaysHomeHubPagesPersonal FinancePetsPoliticsReligionSportsTechnologyTravel

Complement Systems of Integer Representation

Updated on June 1, 2012

There are two concepts of complements which are used in computer number representation and arithmetic:

  1. Digitwise Complement (also known as: Diminished Radix Complement)
  2. Modular Complement (also known as: Radix Complement)

These complement systems become important in integer representation systems with fixed size such as in computers.

Digitwise Complement

(Also known as: Diminished Radix Complement)

Let us assume we have integer representation system in which integers are written in positional notation with fixed number digits: n, n > 0. This means we have n slots (or, positions) each capable of storing one digit. A digit is a symbol. In radix "b", b > 1 we have b symbols. A digit has value: 0 (zero), 1 (one), ... upto (b - 1). (b-1) is largest symbol in radix b system.

Let y be an integer. Let y's n digits be: y0, y1, ... yn - 2, yn - 1. Meaning of this is that the value of y is:

y0 * b0 + y1 * b1 + ... + y(n-2) * b(n-2) + y(n-1) * b(n-1)

The digit yk is said to be in exponent k position. For k = 0 it is said to be in unit's position because regardless of the value of radix b, we have b0 = 1.

There are two positional notations depending on order in which we store digits in slots:

  1. Left to Right (that is, value of k increases from left to right)
  2. Right to Left (that is, value of k increases from right to left)

Most popular integer representation system which humans use has the radix of 10 with digits written from right to left. Humans also have special symbols for sign: "+" for positive and "-" for negative. The invention of complement systems was motivated by need to represent signed numbers in computers. In this article when we need to write out an integer in positional notation we shall use right to left notation.

Definition (Digitwise Complement)

Digitwise complement of y is defined as:

z = z0 * b0 + z1 * b1 + ... + z(n-2) * b(n-2) + z(n-1) * b(n-1)

where zk = (b - 1) - yk, k=0, 1, ... (n - 2), (n - 1).

In other words: we calculate for every k the digit of complement in exponent k position by calculating the (b - 1) complement of the digit of y in exponent k position. Since this is digitwise calculation we call such complement as Digitwise Complement (AKA Reduced Radix Complement). Effectively this is subtraction of y from a n digited number whose every digit is (b - 1). That is, we are subtracting y from integer:

(b - 1) * b0 + (b - 1) * b1 + ... + (b - 1) * b(n-2) + (b - 1) * b(n-1)

This is radix b number with n digits all digits being (b - 1). We simplify this expression:

(b - 1) * b0 + (b - 1) * b1 + ... + (b - 1) * b(n-2) + (b - 1) * b(n-1)

= (b - 1) * (b0 + b1 + ... + b(n-2) + b(n-1)) = bn - 1

In other words: z = bn - 1 - y.

Modular Complement

(Also known as: Radix Complement)

Definition (Modular Complement)

Modular complement of an n-digit number y is defined as an n-digit number z which satisfies following congruence relation modulo bn:

z ≡ -y (modulo bn)

Congruence relation modulo i is now defined:

Definition (Congruence Relation Modulo i)

If i is a positive number then by: "g ≡ h (modulo i)" is meant this:

there exists an integer j such that (g - h) = i * j.

In other words i divides (g - h) without leaving a non-zero remainder. That is:

i is a factor of (g - h) and equivalently: (g - h) is divisible by i

z ≡ -y (modulo bn) means that (z + y) is divisible by bn.

The congruence relation (modulo i) maps all integers into the range 0 (zero) through (i -1). The congruence relation (modulo bn) maps all integers into the range 0 (zero) through (bn - 1). Readers who wish to read more on congruence can read the book: Elementary Number Theory, Cryptography and Codes (Universitext).

The congruence relation is similar to the relation of equality. g and h are equal except by a multiple of i. Sometimes "g ≡ h (modulo k)" is written as: g ≡k h. Congruence has following two important properties:

  1. It is reflexive: for all integers g we have g ≡k g.
  2. It is symmetric: g ≡k h if and only if h ≡k g.

Just so that we can exploit above shorthand notation we will use symbol μ for quantity: bn.

If y > 0 is an n-digit number then an n-digit number which satisfies the relation z ≡μ -y is (μ - y). It is 0 when y = 0. This (and the fact that Digitwise complement of zero is μ - 1), gives us a simple relation between Modular complement and Digitwise complement:

Modular Complement = Digitwise Complement + 1

Example: 1-digit Radix 2 Integers

In this case n=1 and b=2.

Integer  Digitwise  Modular

0        1          0
1        0          1



Equipping With A Maximum

In order that a number representation system be useful we need to have a maximum that the system can represent.

For even numbered radix in Digitwise complement system, it is customary to have it set so that entire set of digit configurations is split into exact halves. This ensures that for every digit configuration which we characterise as positive there is a negative digit configuration.

By way of example, if radix b = 2 * c, then we can equip the range of integers with a maximum m as defined below:

m = m(n-1)m(n-2) ... m1m0

m(n-1) = c - 1

mk = b - 1 for k < (n - 1)

In this case in Digitwise complement if we equip the range of integers with a maximum integer of 0 (zero) then we have no positive number in the system. But reason for that is that size of integers permitted n is just 1.

In case of Modular complement also we do not have positive number for same reason. In case of Digitwise complement only two integers that system can represent are complements of each other. In case of Modular complement there is no positive number but only integer other than 0 is complement of 1 which happens to be its own complement with value -1. This can be verified by congruence relation modulo μ, which is 21 in this example:

-1 ≡μ 1 because 1 -(-1) = 1 +1 = 2 is divisible by 2.

In case of Digitwise complement 1 is complement of 0. This is not peculiar to Digitwise complement system with n=1. It is true for all Digitwise complement systems regardless of n. In all Digitwise complement system two representations of zero are available: one as ordinarily it would be written and one which is complement. It is not apparent in 1-digit system (but will become clear when we consider higher n values), the numbers which are ordinarily written are considered as positive with their complement being considered negative numbers. Thus one zero is termed as +0 and its complement is termed as -0.

In case of Modular complement for 1-digited numbers with 1 as maximum we have positive number but system has no room for its complement.

Lesson from this is: for radix 2 we need to have n > 1 for being able to have a system that has a positive number and a negative number. n=1 is too short.

Example: 1-digit Radix 3 Integers

In this case n=1 and b=3.

Integer  Digitwise  Modular

0        2          0
1        1          2
2        0          1


In this case in Digitwise complement if we have a maximum integer of 1 then we have one positive number and one integer 2 which is complement of 0. In case of Modular complement we have a positive number 1. In case of Modular complement there is positive number and 2 is complement of 1 which makes its value as -1.

In case of Digitwise complement if we have a maximum integer of 1 then we have positive number in the system but it is complement of itself. When such situation arises it is arbitrary design decision as to whether these integers are to be considered as positive or negative.

By way of example, if radix b = 2 * c + 1, then we can equip the range of integers with a maximum m in either of two ways:

m = m(n-1)m(n-2) ... m1m0

mk = b - 1 for k < (n - 1)

And most significant digit can either be:

  1. m(n-1) = c - 1, or
  2. m(n-1) = c

In case of Modular complement with maximum integer set at 1 we have positive number and we have its complement too in the system.

Digitwise complement system will always have two digit configurations for 0. But having an integer which is complement of itself happens only if b is odd numbered. Either we characterise numbers which are complement of itself as non-negative numbers or we characterise them as negative numbers.

Lesson from this is: in Digitwise complement system do not use odd numbered radix if you want all non-negative numbers to have complements which do not fall in the range assigned for non-negative numbers.

Example: 2-digit Radix 2 Integers

In this case n=2 and b=2.

Integer  Digitwise  Modular

00        11          00
01        10          11
10        01          10
11        00          01


In this case in Digitwise complement if we have a maximum positive integer of 01 then we have one positive number and two complements of which one is for zero. In case of Modular complement we have a positive number 01. In case of Modular complement there is positive number 01 and 11 is complement of 01. And it has now 10 which is its own complement.

The radix 2 is of interest to us because that is the radix used in underlying hardware infrastructure that computer designers almost exclusively use. The fact that for 2-digit radix 2 Modular system with maximum set so that the integer range is cut into two equal halves we have an integer which is complement of itself is not unique to these constellations of parameters. It happens for all even numbered radices:

If radix b = 2 * c, then we equip the range of integers with a maximum m as defined below:

m = m(n-1)m(n-2) ... m1m0

m(n-1) = c - 1

mk = b - 1 for k < (n - 1)

With such maximum we define integer p with digit configuration as follows:

p = p(n-1)p(n-2) ... p1p0

where p(n-1) = c and

pk = 0 for k < (n - 1)

The Digitwise complement of this integer is q as defined below:

q = q(n-1)q(n-2) ... q1q0

where q(n-1) = c - 1 and

qk = 2 * c - 1 for k < (n - 1)

The Modular complement of this integer is r as defined below:

r = r(n-1)r(n-2) ... r1r0

where r(n-1) = c - 1 + [1] and (Note: [1] is the carry addition of 1 unit position produces

rk = 0 for k < (n - 1) (Note: when 1 is added to (2 * c - 1) which is (b - 1) we get all zeroes and a carry for most significant digit)

This proves that in Modular complement system there will be always a negative integer which is complement of itself.

In case of Digitwise complement if we equip the range of integers with a maximum integer of 01 then we have positive number in the system. In case of Modular complement we have positive number and we have its complement too in the system which is -1 in value.

Lesson from this is: in radix 2 Modular complement system n > 1 permits at least one non-zero integer on positive as well as negative side. We have a digit configuration which is complement of itself other than 0 which is a feature of all even numbered radices. Having 0 as its own complement is not a problem because our intent is to have system capable of representing negative numbers and if in the system we do not have two digit configurations for zero then the system we devise would be simpler.

Negative Numbers

Having a complement system in which complements are different is useful for the purpose of representing negative numbers. A range of integers equipped with a maximum integer will allow us to represent negative integers. The device of maximum integer permits splitting our set of digit configurations into two parts: one for non-negatives and the other for negatives. Choice of maximum too is a design decision.

Advantage of Modular complement system is the fact that in the system we can just use the arithmetic operations on values and provided the result of operations was going to be in the range of integer system is capable of representing our result would be correct. Reason for this is the fact that arithmetic in congruence relation preserves congruence relationship. That is:

  1. if a ≡k c and b ≡k d then (a + b) ≡k (c + d)
  2. if a ≡k c and b ≡k d then (a - b) ≡k (c - d)
  3. if a ≡k c and b ≡k d then (a * b) ≡k (c * d)

In other words provided result of addition and multiplication are in the range of our integer system the result would be correct. Meaning of this is we can just do arithmetic blindly. Only when we do operations which produces result exceeding maximum positive or minimum negative in the system we have to worry.

Popularity of 2's complement system of integer representation is pecisely because of ease with which we can construct hardware component for arithmetic. 2's complement is radix 2 Modular complement system. In almost all 2's complement systems maximum integer designed into the system is 2(n-1) - 1. This makes identification of negative number simple. If most significant bit is "1" then the integer is negative.

Example: 3-digit Radix 2 Integers

In this case n=3 and b=2.

Integer  Digitwise  Modular

000      111        000
001      110        111
010      101        110
011      100        101
100      011        100
101      010        011
110      001        010
111      000        001


We will consider only Modular system in this example. We fix 011 as the maximum non-negative integer. We list these numbers with their values with sign (in decimal in parentheses):

Integer  Signed Value  Modular

000      +000 (0)        000
001      +001 (+1)       111
010      +010 (+2)       110
011      +011 (+3)       101
100      -100 (-4)       100
101      -011 (-3)       011
110      -010 (-2)       010
111      -001 (-1)       001


We give some examples of additions and subtractions to highlight the problem of result falling outside the range:

  1. 1 + 2 = 001 + 010 = 011 = 3
  2. 1 - 2 = 001 + Modular(010) = 001 + 110 = 111 = -1
  3. -1 + 2 = Modular(001) + 010 = 111 + 010 = [1]001 (Note: Here [1] is a carry which cannot be stored in n=3 system therefore, it is discarded. The result 0001 = +1 is correct)
  4. 3 + 3 = 011 + 011 = 110 = -2 (invalid result)
  5. -3 - 3 = Modular(011) +Modular(011) = 101 + 101 = [1]010 = 2 (Note: Here carry [1] is discarded and result is invalid)

Discussion

As we saw in arithmetic examples (4) and (5) we get invalid result when resulting values falls outside of range the system permits. These are called overflow. How can we detect overflow?

Size of an Integer

Before we grapple with the problem of overflow we introduce two concepts:

  1. Size of an Integer
  2. Sign Extension

We discuss the concept of size of an integer in this section. We will discuss the concept of sign extension in next section.

In radix 10 which is our familiar decimal system following integers are identical:

123
0123
00123


Smallest number of digits that are required to write this number is 3. We can remove all leading zeroes without affecting the value of number 123. 3 is the size of this number. If this number were to be stored in a computer which permits storage of (say) 10-digit numbers then also its size would remain 3.

When we humans use such numbers we are free to use "+" and "-" symbols to represent sign of numbers. But in computer we have to use either Modular complement system or any other system. To introduce the concept of size in the context of Modular complement system we use the example of radix 10 Modular complement system although our real aim is to understand radix 2 systems.

Supposing we have 2-digit radix 10 Modular complement system with maximum non-negative number fixed at 49. Our system is capable of representing numbers from 0 (zero) through 49 on non-negative side and -1 through -50 on negative side. This system requires two digit slots to store numbers in the system.

Now keeping radix fixed at 10 can we store any number in this 2-digit system in smaller number of digits? To answer this question we must ask another question: Is the smaller number of digits going to be stored in a Modular complement system? If the answer is yes, then what will be its maximum non-negative number? Again to fix our ideas let us have for "smaller" number of digits consider a system of 1-digit numbers. For a 2-digit system this is only smaller number of digits possible. We set its maximum integer at 4. That is, we are going to declare a 2-digit number as size 1 digit number if we can store it in size 1 digit number without changing its value.

Only 2-digit numbers which can be stored in 1-digit system are: 0 through 4 on non-negative side and -1 through -5 on negative side . The number 5 in 1-digit system has negative value. Therefore number 05 in 2-digit system has size of 2 digits. The reason for this is if we strip off leading zero we are left with "5" which is a negative number: -5. Therefore, only non-negative 2-digit numbers that can be squeezed into 1-digit Modular system are 0 through 4.

Similarly 2-digit number 99 is negative number in 2-digit system. Its value is -1. And it can be stored in 1-digit system by just removing leading 9. Thus, there are 5 non-negative 2-digit numbers: 00 (zero) through 04 which can be stored in 1-digit system by removing leading zero. There are 5 negative 2-digit numbers: 99 (-1) through 95 (-5) which can be stored in 1-digit system by removing leading 9. There are a total 10 2-digit numbers which can be stored in 1-digit system. We can say that "size" of these 10 numbers is 1. There are 90 other numbers in 2-digit system whose sizes are 2.

Sign Extension

In last section we saw that in specially rigged 1-digit radix 10 Modular complement system there are 10 integers which could preserve values these integer had when they were stored in another specially rigged 2-digit radix 10 Modular system. Thus these 2-digit integers require just 1 digit to store. In other words we can shrink the storage required from 2 digits to 1 digit for numbers: -5 through +4. These 10 numbers however are represented in 2-digit radix 10 Modular complement system as: 95 through 99 and 00 through 04. When these are squeezed into 1-digit system they become: 5 through 9 and 0 through 4. I say that these systems are "specially rigged" because we are no longer pretending that the maximum these two systems will come equipped with can be arbitrary. Rather maximum will be specially chosen so that it will split all digit configurations into equal halves for non-negatives and negatives.

Following table documents these findings. In the table you can see how they will look like in 2-digit system, how humans would write them and how they look like in 1-digit system:

2-digit  Human  1-digit

95       -5     5
96       -4     6
97       -3     7
98       -2     8
99       -1     9
00        0     0
01       +1     1
02       +2     2
03       +3     3
04       +4     4


Try to look at this table from another point of view. It has all the 10 integers a 1-digit Modular system is capable of storing. These are listed in rightmost column. What happens if we try to store smaller sized number in bigger sized storage? Answer is this table. This table shows exactly what will happen if a 1-digit radix 10 number is to be stored in similar 2-digit system. Increasing the number of slots is opposite of shrinking. It is expanding.

Writing 0123 instead of 123 is an example of expanding. But humans assume a "+" sign when they write 123. We can similarly write -0123 when we expand -123 by one digit. But we do not have sign symbol in Modular systems. In Modular systems the sign information is encoded by having a maximum number. The maximum number "cuts" the entire range of numbers into two parts.

When expanding a number in Modular systems we cannot just prefix "0" (zero) digits. We can prefix zero digits if to begin with the number was non-negative. We must prefix the digits (b - 1) if the number is negative. (b - 1) is 9 in case of radix 10.

For example, number 123 in 3-digit radix 10 Modular system can be expanded to (say) a number in 5-digit radix 10 Modular system by prefixing two zeroes: 00123. But the number 567 in 3-digit system is a negative number with human written decimal value of -433. To expand 567 we must prefix two 9's: 99567.

In case of radix 2 such expanding operation is called Sign Extension because it involve a simple operation of copying the sign which in case of radix 2 Modular systems is 1 = (b -1). But in case of radices other than 2 most significant digit might not be exactly (b - 1). Therefore, much better term is Sign Propagation or Sign Padding. Even these expressions are misnomers. We are not interested in preserving sign of original number, but also its value. The number 567 in 3-digit system has same value as number 99567 in 5-digit system, namely; -433. Because all terms which use the sign to describe this operation are misleading I prefer calling it simply as: Digit Padding. If I must be extra clear I can say: Value Preserving Digit Padding.

Overflow Detection

We are now ready to define overflow:

Definition (Overflow)

An arithmetic operation has caused overflow if result of same operation when performed on same operands stored in a storage capable of storing more digits cannot be shrunk back into original storage. In other words, size of result has exceeded the number of digit slots in original system.


Special Case of Radix 2 Modular System

Let us assume we have integer representation system using radix b in which integers are written in positional notation with fixed number digits: n. Let y be an integer. Let y's n digits be: y0, y1, ... yn - 2, yn - 1. Meaning of this is that the value of y is:

y0 * b0 + y1 * b1 + ... + y(n-2) * b(n-2) + y(n-1) * b(n-1)

Similarly let z be an integer with n digits:

z0 * b0 + z1 * b1 + ... + z(n-2) * b(n-2) + z(n-1) * b(n-1)

Definition (Carry)

For exponent k position the carry ck and sum digit sk, are defined in relation to two integers y and z as follows:

c0 = 0

ck = quotient of division of (y(k-1) + z(k-1) + c(k-1)) for k > 0

s(k-1) = remainder of division of (y(k-1) + z(k-1) + c(k-1)) for k > 0

In other words: (y(k-1) + z(k-1) + c(k-1)) = ck * b + s(k-1) for k > 0

For k > 0, we say that ck is "carry-out" of exponent (k-1) position and c(k-1) is "carry-in" of same position. It can be proven that for all radices b, a carry cannot be anything other than 0 (zero) or 1.

For the case of radix 2 Modular complement system with a maximum which halves the digit configurations it can be proven that when overflow occurs the "carry-in" and "carry-out" of most significant digit are not same.

This rule also applies for the case of negation operation on the least valued integer in Modular systems equipped with maximum which halves digit configurations. The negative of of such integer does not exist in the system and any attempt to calculate negative of such number should be declared as having caused overflow.

For example; in 2-digit radix 2 Modular system 10 is least valued integer. Its value in human written format is: -2. But 2-digit radix 2 Modular system permits only integer values: -2 through 1. There is no +2 in the system.

We illustrate what would happen if we attempt negation operation on 10 in 2-digit radix 2 system:

Integer  Value in signed decimal

10       -2
                                                         .
Digitwise complement = 01
                                                         .
Add 1 in unit's position:
                                                         .
010 <--- Carry-in (next higher digit carry-in is carry-out
 01          from lower digit     
 +1
===
 10
                                                         .
Please note carry-out of most significant digit is "0"
But carry-in was "1"


As you can see the attempt to calculate the negative of 10 causes an overflow.

Case of Radices > 2

In case of higher radices rule of "carry-in ≠ carry-out" cannot be used for overflow detection. Below I give a counter example in which we add two hexadecimal numbers represented in radix 16 Modular complement system with maximum which halves digit configurations:

Add D7C5 to D7C5:
10100 <---Carry
 D7C5
+D7C5
------
1AF8A discard 1 carry (result is correct)


As you can see in this case the sum of numbers is correct result although carry-in is not same as carry-out on most significant digit.

We do this calculations again to demonstrate that our original definition of overflow is indeed detecting no overflow. This time we expand the number of digit slots by 1. That is, we prefix both the numbers with digit "F" because both the numbers are negative in the Modular system we are using.

Add D7C5 to D7C5:
First we prefix "F". We get FD7C5.
110100 <---Carry
 FD7C5
+FD7C5
-------
1FAF8A discard 1 carry, we get: FAF8A
                                                   .
We are able to "shrink" the number back into 4 digit 
storage without affecting the sign: AF8A. Therefore, there is
no overflow.


As this counter example demonstrates we cannot use the rule of "carry-in ≠ carry-out" in cases other than radix 2.

Comments

    0 of 8192 characters used
    Post Comment

    No comments yet.

    Click to Rate This Article