Session 5

Arithmetics: Theory and Computation

  1. Define natural numbers as strings of +1 obtained by by repetition of the basic operation of +1 starting from 0: 1=0+1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1, 1+1+1+1+1+1, 1+1+1+1+1+1+1, 1+1+1+1+1+1+1+1, 1+1+1+1+1+1+1+1+1, and so on. Natural numbers are thus defined as strings of +1 of different lengths. Denote the set of natural numbers so obtained by N as the set of natural numbers. For any given n ∈ N (n belonging to the set natural numbers N) there is a natural number n+1 obtained by adjoining +1 to the string of +1 defining n. There is thus no biggest natural number; it is always possible to adjoin yet another +1. As more compact notation we use a decimal (positional) representation with 2=1+1, 3=1+1+1, 4=1+1+1+1, 5=1+1+1+1+1,…or binary representation with 10=1+1, 11=1+1+1, 100=1+1+1+1, 101=1+1+1+1+1+1,…
  2. Define n > m or m < n to mean that the string representing n is longer than that for m.
  3. Define the sum m + n under the +1 operation of addition as the string of +1 corresponding to m followed by the string for n.
  4. Show that m+n = n+m if n, m ∈ N. (hint: use that m+n and n+m correspond to the same string of +1 decomposed in two different ways: first m and  then n, and vice versa). The is the commutative law for addition.
  5. Define the product n*m  for n, m ∈ N under the operation * of multiplication as n times repeated addition of m be represented by a rectangular pattern of +1 with m columns and n rows.
  6. Show that n*m = m*n  for n, m ∈ N. (hint:use the argument in 3 with string replaced by rectangular array). This is the commutative law for multiplication.
  7. What is the effect of multiplying by 10 in decimal system, and by 2 in binary system?
  8. Show that k*(m + n) = k*m + k*n for  k, n, m ∈ N. This the distributive law. (hint: argue by rectangular patterns).
  9. Extend to subtraction recalling Binary Subtraction.
  10. Given  n, m ∈ N not 0, show that  n has a unique decomposition as n = q*m + r where q, m ∈ N and r<m. Here q is called the quotient and r the remainder. Note that q can be determined by successively computing p*m for p=0, 1, 2, 3,.. and choosing q = p  as the first number such that (p+1)*m > n, and then defining r = n – q*m. The code to do this computation is very simple and can be used to replace the algorithm for long division in hand calculation as stumbling stone for many students.  Write this code. Compare with binary code for long division computing the quotient digit by digit.
  11. Recall Basic Mathematics 1-15 building your own pocket calculator for addition, subtraction, multiplication, and division of natural numbers in binary form.
  12. Extend to Rational Numbers.
  13. The two’s complement of an N-bit binary number is defined as its complement with respect to exp(2,N): The sum of a number and its two complement is exp(2,N). For instance, for the three-bit number 010, the two’s complement is 110, because 010 + 110 = 8 which is equal to exp(2,3). See that the two’s complement is calculated by inverting the bits and adding one. Write a code which computes the two complement for a given number. Two’s complement is the most common method of representing negative binary numbers. Figure out how.