Location arithmetic
Encyclopedia
Location arithmetic is a technique to do binary arithmetic using a chessboard-like grid. John Napier
John Napier
John Napier of Merchiston – also signed as Neper, Nepair – named Marvellous Merchiston, was a Scottish mathematician, physicist, astronomer & astrologer, and also the 8th Laird of Merchistoun. He was the son of Sir Archibald Napier of Merchiston. John Napier is most renowned as the discoverer...

 termed the technique in his treatise Rabdology
Rabdology
In 1617 a treatise in Latin entitled Rabdologiæ and writtenby John Napier was published in Edinburgh. Printed three yearsafter his treatise on the discovery of logarithms and in the same year...

, from the way that positions of counters on the board represented numbers.

Using simple moves of counters on the board, Napier showed ways to multiply, divide and even find the square roots of binary numbers. He was so pleased by his discovery that he said in his preface
... it might be well described as more of a lark than a labor, for it carries out addition, subtraction, multiplication, division and the extraction of square roots purely by moving counters from place to place.

Location numerals

Binary notation had not yet been standardized, and Napier used what he called location numerals to represent binary numbers. Roughly speaking, it used alphabets to stand for various powers of two.

He used a to represent 1, b for 2, c for 4, d for 8, e for 16 and so on. To represent a number as a location numeral, express it as a sum of powers of two and replace the powers by the letters. For example
87 = 1 + 2 + 4 + 16 + 64 = abceg


A location numeral can similarly be converted back into standard notation:
abdgkl = 1 + 2 + 8 + 64 + 512 + 1024 = 1611


He permitted letters to repeat, so the same number could be represented in multiple ways. For example
abbc = acc = ad = 9


Notice that since each letter is twice the value of the previous one, two occurrences of the same letter can be replaced with
one of the next letter without changing the value of the number. Thus you can always remove all repeated letters from a
location numeral, and Napier called this the abbreviated form of a number. If on the other hand a location numeral has repeated letters, it is the extended form of the number.

Napier showed ways to convert numbers into and out of abbreviated form which are identical to modern techniques to convert numbers into the binary numeral system
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...

 and we will not repeat them here.

Location numerals provide a simple way to do addition: just write two numbers in abbreviated form together and abbreviate the result. For example to add 157 (acdeh) to 230 (bcfgh) just write them together
acdeh + bcfgh = abccdefghh


and abbreviate the result
abccdefghhabddefghhabeefghhabffghhabgghhabhhhabhi


and abhi = 387 = 157 + 230 as expected.

Subtraction is only a little more complicated. To subtract bcfgh from abhi, first change abhi into its
extended equivalent abccdefghh and just remove the letters bcfgh
abccdefghh - bcfgh = acdeh


to get the result acdeh.

Napier used his non-standard representation of binary numbers to explain his techniques to do arithmetic. However, the rest of this article will rephrase his ideas using the more modern binary notation.

The grid

Location arithmetic uses a square grid where each square on the grid represents a value. Two sides of the grid are marked with
increasing powers of two. Any inner square can be identified by two numbers on these two sides, one being vertically below the inner
square and the other to its far right. The value of the square is the product of these two numbers.
Example grid
            32
            16
            8
    32       4
            2
            1
32 16 8 4 2 1

For instance, the square in this example grid represents 32, as it is the product of 4 on the right column and 8 from the bottom row. The grid itself can be any size, and larger grids simply permit us to handle larger numbers.

Notice that moving either one square to the left or one square up doubles the value. This property can be used to perform binary
addition using just a single row of the grid.

Addition

First, lay out a binary number on a row using counters to represent the 1s in the number. For example, 29 (= 11101 in binary) would be placed on the board like this:
11101 (= 29) on one row
   
0 1 1 1 0 1

The number 29 is clearly the sum of the values of the squares on which there are counters. Now overlay the second number on this row. Say we place 9 (= 1001 in binary) on it like this.
Overlay 1001 (= 9)
   
0 0 1 0 0 1

The sum of these two numbers is just the total value represented by the counters on the board, but some of the squares have more than one counter. Recall however, that moving to the left of a square doubles its value. So we replace two counters on a square with one counter to its left without changing the total value on the board. Note that this is the same idea used to abbreviate
location numerals. Let's start by replacing the rightmost pair of counters with a counter to its left, giving:
 

We still have another square with two counters on it, so we do it again:
   

But replacing this pair created another square with two counters on it, so we replace a third time:
Result 100110 = 38
   
1 0 0 1 1 0

Now each square has just one counter, and reading off the result in binary 100110 (= 38) gives the correct result.

Subtraction

Subtracting is not much more complicated than addition: instead of adding counters on the board we remove them. To "borrow" a value, we replace a counter on a square with two to its right.

Let's see how we might subtract 12 from 38. First place 38 (= 100110 in binary) on a row, and then place 12 (= 1100 in binary) under it:
      38
        12

For every counter on the lower row that has a counter above it, remove both counters. We can remove one such pair on the board,
resulting in:
     
       

Now we need to "borrow" counters to get rid of the remaining counter on the bottom. First replace the leftmost counter on the top row with two to its right:
     
         

Now replace one of the two counters with two more to its right, giving:
     
         

We can now take away one of the counters on the top row with the remaining counter on the bottom row:
11010 = 26
     
         

and read off 26, the final result.

Some properties of the grid

Unlike addition and subtraction, the entire grid is used to multiply, divide, and extract square roots. The grid has some useful properties utilized in these operations. First, all the squares on any diagonal going from the bottom left to the top right have the same value.
    256       32
  256       16 16
256       16   8
      16     4
    16       2
  16         1
32 16 8 4 2 1

Since a diagonal move can be broken down into a move to the right (which halves the value) followed by a move
up (which doubles the value), the value of the square stays the same.

In conjunction with that diagonal property, there's a quick way to divide the numbers on the bottom and right edges of the grid.
32 ÷ 8
          32
          16
          8
      4
          2
          1
32 16 8 4 2 1

Locate the dividend 32 along the right side and the divisor 8 on the bottom edge of the grid. Extend a diagonal from the dividend and locate the square where it intersects a vertical line from the divisor. The quotient lies at the right end of the grid from this square, which for our example is 4.

Why does this work? Moving along the diagonal doesn't change the value; the value of the square on the intersection
is still the dividend. But we also know it is the product of the squares along the bottom and right edge. Since the square on the bottom edge is the divisor, the square on the right edge is the quotient.

Napier extends this idea to divide two arbitrary numbers, as shown below.

Multiplication

To multiply a pair of binary numbers, first mark the two numbers
on the bottom and the right side of the grid. Say we want to
multiply 22 (= 10110) by 9 (= 1001).
10110 * 1001
             
             
            1
            0
            0
            1
  1 0 1 1 0

Now place counters at every "intersection" of vertical and
horizontal rows of the 1s in each number.
       
       
1
      0
      0
1
  1 0 1 1 0

Notice that each row of counters on the grid is just
22 multiplied by some
power of two. In fact, the total value of the counters is the
sum of two rows
22*8 + 22*1 = 22*(8+1) = 22*9

So the counters on the board actually represent the product
of the two numbers, except it isn't possible to "read off" the
answer just yet.

Recall that moving counters diagonally doesn't change the value,
so move all the counters on inner squares diagonally until they
hit either the bottom row or the left column.
           
           
     
     
       
   

Now we make the same moves we did for addition. Replace
two counters on a square with one to its left. If the square
is on the left column, replace two counters with one above
it. Recall that the value of a square doubles if you move up,
so this doesn't change the value on the grid.

Let's first replace the two counters on the second square
at the bottom with one to its left which leaves two
counters at the corner.
           
           
           
         
           
   

Finally, replace the two counters on the corner with one above it
and "read off" the binary number in an L-shaped fashion, starting from
the top left down to the bottom left corner, and then over to the
bottom right.
Result 11000110
             
             
             
1          
1          
       
  0 0 0 1 1 0

Read the counters along the L but don't double count the corner square.
You will read the binary result 11000110 = 198 which is indeed 22*9.

Why can we read the binary number in this L-shaped fashion? The
bottom row is of course just the first six powers of two, but
notice that the leftmost column has the next five powers of
two. So we can directly read off an 11 digit binary number from
the L-shaped set of 11 squares that lie along the left and bottom
sides of the grid.
1024          
512          
256          
128          
64          
 
  32 16 8 4 2 1

Our small 6x6 grid can only multiply numbers each up to 63, and in
general an nxn grid can multiply two numbers each up to
2n+1-1. This scales very fast, so board with 20 numbers per side, for
instance, can multiply numbers each up to a little over two million.

Division

Martin Gardner
Martin Gardner
Martin Gardner was an American mathematics and science writer specializing in recreational mathematics, but with interests encompassing micromagic, stage magic, literature , philosophy, scientific skepticism, and religion...

presented a slightly easier to understand
version of Napiers division method, which is what is
shown here.

Division works pretty much the reverse of multiplication. Say we want
to divide 485 by 13. First place counters for 485 (= 111100101) along
the bottom edge and mark 13 (= 1101) along the right edge. To save
space, we'll just look at a rectangular portion of the board because
that's all we actually use.
485 ÷ 13
                  1
                  1
                  0
                  1
     

Starting from the left, the game is to move counters diagonally into
"columns of divisors" (that is, with one counter on each row marked
with a 1 from the divisor.) Let's demonstrate this with the leftmost
block of counters.
                1
              1
              0
            1
         

Now the next block of counters we might try would begin with the
leftmost counter on the bottom, and we might attempt something like
              1
      ?       1
                0
      ?       1
             

except that we don't have any counters that we can move diagonally
from the bottom edge into squares that would form the rest of the
"column of divisors."

In such cases, we instead "double down" the counter on the bottom
row and form a column one over to the right. As you will soon see, it
will always be possible to form a column this way. So first replace
the counter on the bottom with two to its right.
                1
                1
                  0
                1
         

and then move one diagonally to the top of the column, and move
another counter located on the edge of the board into its spot.
              1
        ?     1
                0
              1
             

It looks like we still don't have a counter on the bottom edge to move
diagonally into the remaining square, but notice that we can instead
double down the leftmost counter again and then move it into the
desired square.
              1
          ?     1
                  0
              1
           

and now move one counter diagonally to where we want it.
              1
              1
                0
            1
             

Let's proceed to build the next column. Once again, notice that moving
the leftmost counter to the top of the column doesn't leave enough
counters at the bottom to fill in the remaining squares.
            1
          ?   1
                0
        ?   1
               

So we double down the counter and move one diagonally into the next
column over. Let's also move the rightmost counter into the column,
and here's how it looks after these steps.
            1
          ? 1
                0
          1
           

We still have a missing square, but we just double down again and move
the counter into this spot and end up with
      1 0 0 1 0 1
            1
            1
                0
            1
             

At this point, the counter on the bottom edge is so far to the right
that it cannot go diagonally to the top of any column, which signals
that we are done.

The result is "read" off the columns—each column with counters is
treated as a 1 and empty columns are 0. So the result is
100101 (= 37) and the remainder is the binary value of any counters
still left along the bottom edge. There is one counter on the third
column from the right, so we read it as 100 (= 4) and we get 485
÷ 13 = 37 with a remainder 4.

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK