2. Number System#

In this chapter we will study about number systems. We normally deal in decimal number system. First question which will come to your mind is what is a number system? Well, a number system is a system which determines the rules and symbols for numbers on how we are going to use them. The symbols for decimal number system are Arabic but they were taken from India, presumably. A number system consists of symbols for representing numbers and a dot for representing fractional numbers. Minus sign is used to represent negative numbers. A number system ranges from \(-\infty\) to \(+\infty\). It is best represented by a straight line given below.

Figure made with TikZ

Number axis

As you see the stretch of number axis, it makes me wonder what is infinity. Infinity in itself is not a number to be honest in the sense that it is more of a concept. Infinity is such a large number that cannot be written or achieved by anything of physical world. Infinity is immeasurable. Each point on this axis represents a number. It may be integer or fractional number. I hope you know what is an integer. An integer is a whole number like -1, -2, 0, 5, 7 etc. Real numbers have fractional parts like 1.234. I cannot go much into these basics. The important fact to note is that between any two points there exists infinite numbers. In other words between any two numbers there exists infinite numbers. For example, between 1.2 and 1.3 there are 1.21, 1.22, 1.23…, 1.29. Moreover between 1.21 and 1.22 there are 1.211, 1.212, 1.213 and so on.

Now let us come back to number system discussion. It enables us to represent a point on this axis. The numbers I have written are supposedly in decimal number system. Base of decimal number system is 10. Why because it consists of 10 distinct symbols 0 through 9. Similarly we can have any other number system. Popular number systems in computers are binary, octal and hexadecimal not to mention decimal of course.

2.1. Definitions and Notations#

  1. Quantity is amount or and extent, is expressed in terms of a unit of the same kind.

    Thus, 10, 5 bushels, 6 tons, 50 miles, 7 years, 100 dollars, m square feet, n cubic yards, are quantities, the units in order being the abstract number 1, 1 bushel, 1 ton, 1 mile, 1 year, 1 dollar, 1 square foot, 1 cubic yard.

  2. Two or more of the same kind are Commensurable or Incommensurable with reference to one another according as they can or can not be measured with the same unit.

    Thus, if the sides of a rectangle are 3 feet and 4 feet respectively, the diagonal is 5 feet, and is, therefore, commensurable with the sides; but the diagonal of a square is incommensurable with its sides, being \(\sqrt{2}\) times one of the sides.

  3. An Incommensurable Quantity, without comparison with another is one that cannot be in the quantity, exactly expresseddecimal notation.

    Thus, \(\sqrt{5}\) is an incommensurable quantity, being 2 plus a decimal fraction which never terminates.

  4. Algebra is that branch of pure mathematics which treats of numbers as and of expressed by symbols having general values,the nature, transformations, and use of equations

  5. Algebra differs from arithmetic in the following important particulars:

    1. In arithmetic values are counted in one direction only from 0; while in algebra, by means of positive and negative values quantities, are counted in two opposite directions from 0.

    2. Arithmetical quantities, denoted figures, have each a by single, definite value; while algebraical quantities, represented by letters have any value we choose to assign to them. These quantities can recognized anywhere operation, results formulae instead of answers. and the results, therefore, general formulae instead of specialized answers.

    3. In arithmetic a problem is solved by analyzing it, step by while in the conditions are instep; algebra expressed equations one or more unknown involving quantities, usually representing the answer or answers.

  6. Algebra employs five kinds of symbols, viz. of quantity, of abbreviation, of operation, of relation, and of aggregation,

  7. The Symbols of Quantity commonly employed are the following:

    1. The Arabic figures.

    2. The letters of the Roman alphabet, known quantities being the letters, and unknown the represented by leading quantities by final letters.

    1d. Similar quantities employed in the demonstration of a theorem the solution of a problem are often represented the same by the same letter with different as read accents, a’, a”, a’”, etc., prime, “a””, a”” a second prime and a””” a third prime. or by the same letter but different subscripts as \(a_1, a_2, a_3\) being read as “a sub-one”, “a sub-two” and “a sub-three.” Initial letters are sometimes used, as \(r\) for radius, \(s\) for sum and \(d\) for difference.

    2d. The Greek \(\pi\) is used for the ratio of the circumference of a circle to its diameter.

    3d. Zero, 0, used to denote not only the absence of value, but also a value that is less than quantity any assignable,

    4th. Infinity, \(\infty\), used to represent that is a quantity greater than any value assignable.

  8. The Symbols of Operation in algebra are those common to all branches of mathematics, the principal ones being the following:

    1st. The sign of addition, + , read “plus.” 2d. The of subtraction, - , read “minus.” 3d. The sign of multiplication, x, read “into,” or “times,” or “multiplied by.”.

    Multiplication is indicated also a dot between the by quantities. The quantities between which multiplication is indicated are quantities called Factors, and the result of the is called the Product.

    4th. The sign of division, \(\frac{}{}c\), read “divided by.” Division is indicated also by writing the dividend above, and the divisor below, a line, in the fractional form.

    5th. The sign of evolution, \(\sqrt{}\), called the radical sign, and read “the root of,” the root, or second root, one of square being the two factors into which a number is conceived to be resolved. The 3d, 4th, or nth root, which is meant one of the by 3, 4, or n factors into which a number is conceived to be resolved, is indicated by writing 3, 4, or n in the vertex of the angle if the, the this number being called the Index,

  9. Besides the above signs, or symbols of operation, there are certain of with reference positions to quantities that indicate operations, the principal ones being the followings:

    1. A Coefficient, which is a quantity written beside another quantity to show how many times the latter is taken.

      When algebraic quantities are written in succession with no sign between them, their product is signified, and factor, or any the of of factors, is the coefficient of the product anyproduct of the remaining factors.

      Thus, in 5 mnx, 5 is the coefficient of mnx, 5m is the coefficient of nx,and 5 mn is the coefficient of x. The name usually applies to the numerical factor, and when applied as 1 is it is not written.

    2. An Exponent, which is a quantity written at the right of and above another quantity, its meaning being as follows:

      a. quantity, meaning being (a) When an exponent is a positive integer, it indicates that the quantity affected by it is to be taken as a factor as many times as there are units in the The result of muliplication is called a Power hence a is said; positive integral exponent indicate power.

      Thus, \(a . a = a^2\), read “a square”, “a 2d power” or “a 2d” \(\\a . a . a = a^3\), read “a cube”, “a 3d power” or “a3d” \(\\a . a . a . a= a^3=4\), read “a 4th power”, “a 4th” \(\\a . a . a ... n~times~a= a^n\), read “a nth power”, “a nth”

      b. When an exponent is a positive fraction, [1] the numerator indicates a power and the denominator a root of the quantity affected by it.

      Thus, \(32^{\frac{4}{5}}\) is the \(4\) th power of \(32\) and \(5\) the power of \(5\). There is glitch in that statement and you supposed to find it.

      c. When an exponent is negative, it indicates the reciprocal of what could have been as a positive exponent. Thus, \(b^{x+y} = \frac{1}{x * y}\)

1. Natural numbers Numbers 1, 2, 3 4, … used in ordinary counting are called natural numbers or positive integers. The set of natural numbers is denoted by N.

Thus N = {1, 2, 3, 4, 5, …}

2. Integers: The numbers …, -3, -2, -1, 0, 1, 2, 3, … are called integers. These are whole numbers i.e. not fractions. The set for integers is denoted by I or Z.

This I or Z = {…, -3, -2, -1, 0, 1, 2, 3, …}

Clearly, \(N \subset Z\).

3. Zero: 0 is an integer but a special integer. It is neither negative not positive but 1’s complement in binary number system has two zero one positive and one negative while 2’s complement has only one zero. Zero is treated as a non-negative as well as non-positive integer.

Examples:

  1. Set of positive integers = {1, 2,3, …}

  2. Set of negative integers = {-1, -2, -3, …}

  3. Set of non-negative integers = {0, 1, 2, …}

  4. Set of non-positive integers = {0, -1, -2, …}

Figure made with TikZ

Integer Classification

4. Rational Numbers: is a number of form \(\frac{a}{b}\) where \(a\) and \(b\) are integers and \(b\ne 0\). The set of rational numbers is denoted by Q.

Thus Q= \(\{\frac{a}{b}: a,b\in Q \text{ and } b\ne 0\}\). Since \(b\) is an integer it can very well be 1 therefore each number of the form \(\frac{a}{1}\) which is nothing but \(a\) is also a rational number.

Clearly, \(N\subset Z\subset Q\). Examples of rational numbers are \(\frac{2}{3}, -\frac{3}{4}, 7\) etc. 0 is an integer and hence a rational number.

5. Decimal form of a rational number is either recurring or terminating As we know that base of decimal number system is 10 which has two prime factors. Now if denominator of a rational number is not one and contains any other factor than 2 and 5 then the rational number will be recurring and if it is only product of powers of 2 and 5 or is 1 then the rational number will be terminating. This can be generalized for any base or radix \(r\) which has say prime factors \(r_1, r_2, ..., r_n\) then in that case if denominator contains any other factor than these then that rational number will be recurring else terminating.

For example \(\frac{3}{4}=0.75\) while \(\frac{3}{7}=.4285714285714...\)

It is safe to assume that \(a\) and \(b\) do not have a common factor because that factor can be eliminated without changing the value of the rational number.

6. Standard form of a rational number: A rational number of the form \(\frac{a}{b}\) is said to be in standard form if \(a\) and \(b\) have no factor in common other than 1 and \(b>0\).

7. Irrational numbers: Consider a rational number \(\frac{a}{b}=\sqrt{2}\). By definition of rational numbers \(a\) and \(b\) cannot have a common factor. But then \(a,b\in Z\) which is not the case here as \(a \text{ or } b\) is not an integer. Therefore, it is not a rational number. The reason is if both of them are integers then the rational number cannot be square root of a number. Hence, we can conclude that this fraction \(\frac{a}{b}\) is an irrational numbers and there are infinite such irrational numbers.

8. Decimal form of an irrational number is neither terminating nor recurring For example :math:sqrt{5}=1.732…

9. Real numbers: All rational and irrational numbers are also known as real numbers which is denoted by set R.

Clearly, \(N\subset Z\subset Q\subset R\)

2.2. Binary Number System#

As the name suggests binary number system has base of 2. Therefore it has only two symbols. 0 and 1. This is the most popular system for computers because TTL NAND and NOR gates which are the most basic logic gates using which other gates are implemented in processor has only two voltage output levels because of their operation in cut-off and saturation zones. These terms are better understood with the help of a book on electronics which is out of scope of this book. All binary numbers consist of 0 and 1. So the count is like 0, 1, 10, 11, 100, 101, 110, 111, 1000 and so on.

2.2.1. Counting in Binary Number System#

First 0 then 1 the what? Why 10? Because that is the next bigger number you can form using 0 and 1. Also, 10 when converted to decimal is 2. This represents base. 10 in any number system represents the base of that system. After conversion to decimal. Note you can read it ten but it is not really ten. There are no tens in binary. When you say ten by default we mean that of decimal system. A number has no meaning without its base. So you can better write it as \(10_2\). The subscript denotes the base.

2.2.2. Conversion of Decimal and Binary#

Consider a decimal number. Let us say 53 then how would be convert it to binary. The technique is that of division. Please watch following carefully:

2 | 53 | 1
----------
2 | 26 | 0
----------
2 | 13 | 1
----------
2 | 6  | 0
----------
2 | 3  | 1
----------
2 | 1  |

So the binary is \(110101_2\). Please allow me to explain the process even though it is trivial and obvious. First we divide 53 by 2 and write the remainder. Then quotient is 26. We repeat the process for 26 therefore remainder is 0 and quotient is 13. This we go on repeating till we have 1 as quotient. Note that all the remainders will be 0 or 1 because divisor is 2. Similarly, final quotient is always 1. Now we take final quotient and start writing remainders from top to bottom.

To convert binary to decimal let us examine following:

\[1*2^5 + 1*2^4 + 0*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 53_{10} \]

The power is to 2 because 2 is the base of source. It starts from 0 for unit’s position and increases to 1 and 2 for ten’s and hundred’s position and so on. 1’s and 0’s are the values of that place. If you note carefully powers of 2 grow like 1, 2, 4, 8, 16, 32, 64, 128 and so on. Any number can be written by using these powers at most one time. For example consider 100. I know it is less than 128 so I will use 64. Then 36 remains. So I will use 32 and then 4. This means \(100 = 64 + 32 + 4\) which means power 6, 5 and 2 have been used. Therefore, I can quickly write down number as \(1100100_2\).

Fractional numbers are slightly more complicated. Let us consider \(1.1_2\). In decimal it will be \(1 + \frac{1}{2}\). This is 1.5 in decimal. Note that when you convert a fractional part of binary to decimal denominator will always be power of 2. For that matter when you convert from any base to decimal denominator will be powers of that base. Important Therefore, when you convert from decimal to some base n then denominator of that decimal number can have only those prime factors which are available in the set of prime factors of n.

Operations such as addition, subtraction, multiplication and division are similar in all number systems.

2.3. A Generic Positional Number System#

Let us try to describe a number in a generic number system which is given below:

(1)#\[(.. c_mb^{m-1} + c_{m-1}b^{m-2}+ ... + c_2b^1 + c1_b^0 + c_{-1}b^{-1} + ... + c_{-m}b^{-m} ) \\ = (... c_mc_{m-1}...c_2c_1.c_{-1}...c_{-m})_b\]

As you can see all the terms with \(c\) are called digits. The leftmost or leading digit is called most significant digit and the rightmost or trailing digit is called least significant digit. The . is called a point which separates the integral part which is towards its left from the fractional part which is towards its right. \(b\) is known as radix or base of the number system. Note that all digits will be between 0 to \(b-1\). So in our decimal system \(b\) is 10 therefore we have digits from 0 to 9. In binary number system it is 2 therefore digits permitted are 0 and 1.

These are the basics of number systems i.e. the numbers themselves. When we return back from our journey of Mathematics to Data structures and Algorithms I will discuss more on number theory and about Alan Turing and how the world’s shape changed because of him and foundation of computer science was laid.