for

CSCI 301: Great Ideas in Computer Science

(c) 1993 - 2007 John E. Howland, All Rights Reserved

Department of Computer Science

Trinity University

One Trinity Place

San Antonio, Texas 78212-7200

Internet: jhowland@ariel.cs.trinity.edu

First, note that ordinary mathematical notation for numbers uses positional
notation. That is, the rightmost digit has a place value of 1
(10^{0}), the next rightmost digit has a place value of 10
(10^{1}), the next digit has a place value of 100 (10^{2}),
etc. Hence, 123 is 1x100 + 2x10 + 3x1.

To simplify our discussion we limit our arithmetic to 4 digit integers. Limiting the size of numbers we deal with is reasonable since we need to store numbers in the memory of a computer and we do not want to use a representation which wastes valuable memory space.

Consider the following subtraction problem:

4221 -0063 -----which is the same problem as

4221 +10000 -0063 -10000 ------which is the same problem as

4221 +9999 -0063 +0001 -10000 ------We first combine

+9999 -0063 ------ 99369936 is called the 9's complement of 0063. Next we add 1 to obtain the 10's complement.

9937The 10's complement is then

4221 +9937 ------ 14158Recall that we still need to subtract 10000, however, notice that this problem will always have a carry of 1 out of the 4th digit and since we are just representing 4 decimal digits, we accomplish the subtraction of 10000 by ignoring the carry. This process yields a result of 4158 which is the correct answer for the original problem. Note also, that we have accomplished the operation of subtraction by adding the 10's complement!

The 10's complement of a number acts like a negative representation for that number, that is, adding the 10's complement of x is the same as subtracting x. A little experimentation shows that if the left most digit is 5 or greater, then that number represents a negative. For example, (using 4 digit 10's complement representations) 9999 is -1 and 5000 is -5000 and 5001 is -4999.

The reason we wish to use base 2 rather than base 10 is that electronics technology has not been able to produce inexpensive, reliable and fast circuits which have 10 stable states (used to represent the 10 base 10 digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9). However, it is possible to build inexpensive, reliable and fast circuits which have 2 stable states (used to represent the 2 base 2 digits 0 and 1). A popular family of circuits, TTL, (Transistor Transistor Logic) uses 0 volts to represent the digit 0 and +5 volts to represent the digit 1.

For simplicity, we limit our example to base 2 numbers having 6 bits (binary digits). The problem of

31 -26 ---is, written in binary notation,

011111 -011010 ---------which is the same as the problem:

011111 +1000000 -011010 -1000000 --------which is the same problem as:

011111 +111111 -011010 +000001 -1000000 --------We first combine

111111 -011010 ------- 100101100101 is called the 1's complement of 011010. Notice that the 1's complement is obtained by simply changing 0's to 1's and 1's to 0's. This is easily implemented with a very simple and very basic TTL circuit element called a complementer or a not circuit. Next we add 1 to the 1's complement.

100101 +000001 ------- 100110We call 100110 the 2's complement of 011010. Next we add the 2's complement to our original number.

011111 +100110 -------- 1000101As before, since we are representing just 6 bits, we accomplish the subtraction of 1000000 by ignoring the carry out of the 6th bit yielding a result of

000101which is the answer (5 base 10).

2's complement representations may be used to represent negative values. A 2's complement representation is negative if the leftmost bit is 1 otherwise the representation is positive. Using 6 bit 2's complement representations, 111111 = -1, 100000 = -32, 100001 = - 31 and 011111 = 31.

124 = 1x10Also, notice that the ratio of the place value of any two consecutive digits is always b. In Example 3.1.4, b = 10.^{2}+ 2x10^{1}+ 4x10^{0}

There are other commonly used number systems where the ratio of two consecutive digits is not always the same. For example, when we keep time in the form centuries, years, days, hours, minutes and seconds, the ratios between the consecutive digits are 100, 365, 24, 60 and 60. That is, there are 60 seconds in a minute, 60 minutes in an hour, 24 hours in a day, 365 days in a year and 100 years in a century. If we want to convert time, measured in seconds to time measured in centuries, years, days, hours, minutes and seconds we would use the following procedure:

b. Divide the number of minutes (the quotient of the previous division) by 60 (the number of minutes per hour). The remainder of this division is the number of minutes. The quotient of this division is the number of hours.

c. Divide the number of hours (the quotient of the previous division) by 24 (the number of hours per day). The remainder of this division is the number of hours. The quotient of this division is the number of days.

d. Divide the number of days (the quotient of the previous division) by 365 (the number of days per year). The remainder of this division is the number of days. The quotient of this division is the number of years.

e. Finally, divide the number of years (the quotient of the previous division) by 100 (the number of years per century). The remainder of this division is the number of years. The quotient of this division is the number of centuries.

Suppose that we represent the ratios of the place values of each digit in a
number system as a list of numbers. We call such a list a *base* list.
The base list for a time number system might be 100 365 24 60 60. This list
is determined by the fact that there are 60 seconds in a minute, 60 minutes in
an hour, 24 hours in a day, 365 days in a year and 100 years in a century.
Algorithm 3.1.5, which converts time in seconds to time measured in centuries,
years, days, hours, minutes and seconds uses the elements of the base list
100 365 24 60 60 in reverse order, dividing each quotient by the next (in
reverse order) base list value. The remainders produced by this process are
the digits in the new number system from least significant to most significant.
This process is modeled by the following J verb:

rep =: #:Suppose we wish to convert 1000000 seconds to centuries, years, days, hours, minutes and seconds. Then we would write:

100 365 24 60 60 rep 1000000 ==> 0 11 13 46 40That is, 1000000 seconds is 0 years, 11 days, 13 hours, 46 minutes and 40 seconds. If you carry out the individual steps of the algorithm on this example, you can see that 1000000 divided by 60 is 16666 with a remainder of 40, 16666 divided by 60 is 277 with a remainder of 46, etc.

Notice that even though this algorithm divides by 100 (the number of years in a
century), the result does not contain an item for the number of centuries.
This is because the number of centuries is the quotient of the division by 100
whereas the number of years is the remainder of the division by 100. The
`rep` verb contains a provision to obtain the quotient as well as the
remainder of the division by the last element (in reverse order). If the first
element of the base list (last element in reverse order) is zero, no division
is performed and the `rep` verb terminates, returning the quotient as
its answer.

To compute the 6 digit base 2 representation of 25 you would use a base list of 2 2 2 2 2 2.

2 2 2 2 2 2 rep 25 ==> 0 1 1 0 0 1To compute the 4 digit base 3 representation of 29 you would write:

3 3 3 3 rep 29 ==>

1 0 0 2The J verb

base =: #.For example, to compute the number of seconds in 0 years, 11 days, 13 hours, 46 minutes and 40 seconds you would write:

100 365 24 60 60 base 0 11 13 46 40 ==> 1000000Notice that the

2 2 2 2 2 2 2 2 base 0 1 1 1 1 1 1 1 ==> 127 3 3 3 3 base 1 0 0 2 ==> 29Finally, we should notice that the first element (last element in reverse order) of a base list is not used in the

One byte integers, n, satisfy:

unsigned 0 <= n <= 255 = -1 + 216 bit integers (short integers), n, satisfy:^{8}. signed -128 <= n <= 127 = -1 + 2^{7}

unsigned 0 <= n <= 65535 = -1 + 232 bit integers (long integers), n, satisfy:^{16}signed -32768 <= n <= 32767 = -1 + 2^{15}

unsigned 0 <= n <= 4294967295 = -1 + 2Recently, some machines are being produced which operate directly on 64 bit integers.^{32}signed -2147483648 <= n <= 2147483647 = -1 + 2^{31}

0000 - 0 1000 - 8 0001 - 1 1001 - 9 0010 - 2 1010 - A 0011 - 3 1011 - B 0100 - 4 1100 - C 0101 - 5 1101 - D 0110 - 6 1110 - E 0111 - 7 1111 - FHence, the 32 bit 2's complement value of -1 has the following hexadecimal representation:

FFFFFFFFThe 16 bit 2's complement value of 2 has the following hexadecimal representation:

0002etc.

BCD integers are variable length strings of bytes in memory where groups of 4 bits are used to represent decimal digits. This means that 2 decimal digits may be packed into each byte. Some systems support use of unused bits in the leftmost digit to represent the sign of the number. For example, 329 would require two bytes of memory and would look like (using hexadecimal notation)

0329

An example might be +1.234 x 10^{23}

^{}Numbers written in scientific notation are usually written in a
normal form (for example the value of the fraction being written so that it is
between 1 and 10). If the result of some calculation is .0001 x
10^{15}, then it must be normalized as

1.000 x 10^{11}

When scientific notation is used to represent inexact values on a computer it is usually referred to as floating point notation.

When graphed, adjacent floating point numbers close to zero are very closely spaced, however, the gaps between adjacent floating point numbers far from zero are more than astronomically large!

In an effort to try to standardize inexact computation, the IEEE formed a committee in the mid 1980's which produced the IEEE Standard 754 for binary floating point arithmetic. Since then, most computer manufacturers have begun to use this standard for representations which is given, in part, in Section 3.5.1.

___________________________________________ Symbol Description ___________________________________________ v value of the number s sign bit e biased exponent i explicit one's bit (extended type only) f fraction

The value v of the number is determined by these fields as shown in the following table:

Values of single-format numbers (32 bits)

___________________________________________________________ e f v class of v ___________________________________________________________ 0<e<255 (any) v=(-1)^{s}x 2^{(e-127)}x (1.f) normalized e=0 f!=0 v=(-1)^{s}x 2^{(e-126)}x (0.f) denormalized e=0 f=0 v=(-1)^{s}x 0 zero e=255 f=0 v=(-1)^{s}x infinity infinity e=255 f!=0 v is a NaN NaN

The value *v* of the number is determined by these fields as shown in the
following table:

Values of double-format numbers (64 bits)

___________________________________________________________ e f v class of v ___________________________________________________________ 0<e<2047 (any) v=(-1)For example, the double representation (in hex notation) of 1.5 is^{s}x 2^{(e-1023)}x (1.f) normalized e=0 f!=0 v=(-1)^{s}x 2^{(e-1022)}x (0.f) denormalized e=0 f=0 v=(-1)^{s}x 0 zero e=2047 f=0 v=(-1)^{s}x infinity infinity e=2047 f!=0 v is a NaN NaN

3FF8000000000000is

3F847AE147AE147A

The value v of the number is determined by these fields as shown in the following table:

Values of extended-format numbers (80 bits)

___________________________________________________________ e i f v class of v ___________________________________________________________ 0<=e<=32766 1 (any) v=(-1)^{s}x 2^{(e-16383)}x (1.f) normalized 0<=e<=32766 0 f!=0 v=(-1)^{s}x 2^{(e-16383)}x (0.f) denormalized 0<=e<=32766 0 f=0 v=(-1)^{s}x 0 zero e=32767 (any) f=0 v=(-1)^{s}x infinity infinity e=32767 (any) f!=0 v is a NaN NaN

The rationals are those which can be represented in the form

a/b where a and b are integers and b not zero.

An equivalent formulation is that the rationals are those numbers which have a repeating representation using some radix.

The irrational numbers can be characterized as those numbers whose representation in any radix never repeat.

This means that an infinite amount of memory would be required to exactly represent an irrational number. Since this is impossible, we are forced to cut off the representation after a fixed number of digits. As soon as this is done, we are no longer representing the irrational exactly, but rather, we have substituted a rational (which approximates the irrational) whose radix representation repeats in the digit zero.

This means that all computer numeric representations (called machine numbers) are necessarily rational numbers.