ECE-1021

Arithmetic in a Positional Number System

(Last Mod: 27 November 2010 21:37:41 )

ECE-1021 Home



To perform most arithmetic operations, such as addition and multiplication, in a positional numbering system you must understand two concepts - first, how those operations are carried out on single digit numbers and, second, how those operations, when carried out on the component digits of a multi-digit number, interact with the operations on neighboring digits. For example, when adding two multi-digit numbers, add the corresponding digits of the two numbers, starting from the right, and invoke the concept of a "carry" from one position to the next. 

When you were first learning to do addition and multiplication, you had to memorize your addition and multiplication tables at least through 9+9 and 9x9 (and usually a bit higher). Few of you have any need to look up the result of 6x8 any more and do not even realize you are recalling a memorized fact - one that you probably spent quite a bit of time and effort to commit to memory back in grade school. But the fact remains that you are still referring to an addition and multiplication table, it just happens to be one that you have long since internalized.

If you are going to work with numbers in bases other than base-10, you will need to have access to the addition and multiplication tables for single digit quantities in those bases. If you work in those bases enough, it will be worthwhile to commit those tables to memory. But in the meantime it is perfectly reasonable to refer to those tables when needed. It is, however, pretty important that you understand what those tables are - which means that you should be able to produce those tables, from scratch, without difficulty.

Let's construct the tables for base-8 (also known as "octal"):

Base-8 Addition Table

+ 0 1 2 3 4 5 6 7
0 00 01 02 03 04 05 06 07
1 01 02 03 04 05 06 07 10
2 02 03 04 05 06 07 10 11
3 03 04 05 06 07 10 11 12
4 04 05 06 07 10 11 12 13
5 05 06 07 10 11 12 13 14
6 06 07 10 11 12 13 14 15
7 07 10 11 12 13 14 15 16

Base-8 Multiplication Table

x 0 1 2 3 4 5 6 7
0 00 00 00 00 00 00 00 00
1 00 01 02 03 04 05 06 07
2 00 02 04 06 10 12 14 16
3 00 03 06 11 14 17 22 25
4 00 04 10 14 20 24 30 34
5 00 05 12 17 24 31 36 43
6 00 06 14 22 30 36 44 52
7 00 07 16 25 34 43 52 61

The values were written as two digit numbers, using a leading zero where necessary, purely for consistency. The two tables can be combined into one by the simple expedient of placing both results in each cell separated by a space or a character. We'll use a forward slash and place the addition result to the left and the multiplication result to the right.

Base-8 Combined Addition/Multiplication Table

+/x 0 1 2 3 4 5 6 7
0 00/00 01/00 02/00 03/00 04/00 05/00 06/00 07/00
1 01/00 02/01 03/02 04/03 05/04 06/05 07/06 10/07
2 02/00 03/02 04/04 05/06 06/10 07/12 10/14 11/16
3 03/00 04/03 05/06 06/11 07/14 10/17 11/22 12/25
4 04/00 05/04 06/10 07/14 10/20 11/24 12/30 13/34
5 05/00 06/05 07/12 10/17 11/24 12/31 13/36 14/43
6 06/00 07/06 10/14 11/22 12/30 13/36 14/44 15/52
7 07/00 10/07 11/16 12/25 13/34 14/43 15/52 16/61

With the aide of this table - and the rules for how we carry out multi-digit addition, subtraction, multiplication, and division that we are already familiar with for base-10 - we can now perform arithmetic directly in base-8. This is not to say that we won't find ourselves a bit rusty and perhaps a bit too reliant on calculators to make it very comfortable to perform the arithmetic directly at first. But our goal here is not to do enough arithmetic directly in another base so as to be comfortable doing it. Our goal is to do enough so that we reacquaint ourselves with the fundamentals of how to do it directly so that when it comes time to develop algorithms that have these fundamentals at our disposal.

Example: Multiply the base-8 numbers 53 and 27 performing all of the arithmetic directly in base-8

  53     53         53

 x27    x 7        x 2

 ===    ===        ===

 455     25 (3x7)    6 (3x2)

126     43  (5x7)  12  (5x2)

====    ===        ===

1735    455        126

Result: 53 x 27 =  1573 (in base-8).

Example: Confirm the previous result by dividing 27 into 1735 directly in base-8

First we'll make a little table of the products of the divisor and each of the possible digits.

 27  27  27  27  27  27

 x2  x3  x4  x5  x6  x7

=== === === === === ===

 16  25  34  43  52  61

 4   6  10  12  14  16

=== === === === === ===

 56 105 134 163 212 241

 

         53

      ------

  27 / 1735

      -163

      ------

        105

       -105

      ------

          0

Result: 1735 divided by 27 is 53 (in base-8) which verifies our prior result.


Acknowledgements

The author would like to acknowledge the following individual(s) for their contributions to this module: