Monday, January 7, 2013

Subtraction of Numbers

If you are in Hong Kong and you need help for university mathematics courses, please visit www.all-r-math.com.

Many many years ago, when I first encountered the computer algorithm for subtraction of numbers, I really do not know what happens.
Several days ago, I have read an article saying that the primary school kids, who are okay to do additions, face difficulties in subtractions.
The two problems seems unrelated, but they are really the same problem.
Addition is easy, subtraction is hard, for computers and kids alike!

Lets review how a computer do base 2 addition:

To add two numbers, with fixed length, say (01001101)+(00011101). We need three memory units: N1 to hold a digit for the first number, N2 to hold a digit for the second number, C to hold a carry digit.

Step 1. Load the last digit of the first number to N1, the last digit of the second number to N2, 0 to C. Then do the following operation:
N1N2CResult Digit and new C
0000, 0
0011, 0
0101, 0
0110, 1
1001, 0
1010, 1
1100, 1
1111, 1
(Basically, it means N1+N2+C=(new C, Result Digit).)
In our example, N1=1, N2=1, C=0, so the result is 0 and new C=1.

Step 2. Load the next digit (on the left side) of the first number to N1, the next digit of the second number to N2. Again follow the table above.
In our example, N1=0, N2=0, C=1, so the result is 1 and new C=0.

Step 3-Step 8. Repeat Step 2.
In our example, it is
  • N1=1, N2=1, C=1: result is 0, new C=1
  • N1=1, N2=1, C=1: result is 1, new C=1
  • N1=0, N2=1, C=1: result is 0, new C=1
  • N1=0, N2=0, C=1: result is 1, new C=0
  • N1=1, N2=0, C=0: result is 1, new C=0
  • N1=0, N2=0, C=0: result is 0, new C=0
The final answer, reading all the results backwards, is (01101010)

Looks fancy, but it is just how we do addition. Now, for subtraction.

Lets use the same two numbers: (01001101)-(00011101).

Step 1. Change the second number, switch 0 and 1, so it becomes (11100010).

Add the first number and the new second number: (010001101)+(11100010)=(00101111).

Add the answer by (00000001), and we get the answer (00110000).

Why does it work?
Because we are not doing really the usual addition and subtration, we are doing modulo arithmetic!!!

We say that m=n (mod R) is m-n is divisible by R. If we are doing arithmetic under this equivalence relation, we are doing modulo R arithmetic, or ZR-operations.
For example, in modulo 3 arithmatic, we have
+012
0012
1120
2201
×012
0000
1012
2021
The computer arithmetic is simply doing modulo 28 arithmetic. Therefore
(01001101)-(00011101)
=(001001101)-(000011101)
=(001001101)-(000011101)+(100000000)
=(001001101)-(000011101)+(011111111)+(000000001)
=(001001101)+(011100010)+(000000001)
=(01001101)+(11100010)+(00000001)

It explains the algorithm.

Now I wish to propose a new subtraction algorithm for kids, using the same idea.

Say, we want 19021-8742.

Rewrite the second number as 08742, then switch using 0<->9, 1<->8, 2<->7, 3<->6, 4<->5. The new number is 91257

Add the first number and the new number, ignore the leftmost digit: 19021+91257=10278.

Add 1, the final answer is 10279.

Lets try two more. 24311-13904 and 34052-23016.

24311
-13904
======
24311
+86095
------
10406
+ 1
------
10407
34052
-23016
======
34052
+76983
------
11035
+ 1
------
11036