User:Kbs
I'm interested in simple computing ideas. I made my first edits to the article
on Napier's bones a neat, simple aid to doing arithmetic.
Suggestions, brickbats and donations over here at my talk page.
Why Does the Square Root Process Work
The basic idea behind finding the square root of a number is to find
the largest perfect square less than or equal to a prefix of the
number. The square root of this perfect square also turns out to be a
prefix for the square root of the number. The procedure extends this
square root for longer and and longer prefixes of the number until we
determine the square root for the entire number, or more accurately,
the largest perfect square less than or equal to the number.
For instance, let's start out with some number say 46. The largest
perfect square less than or equal to it is 62 = 36. We'll
soon see that the largest perfect square less than or equal to any
number of the form 46## (that is, 46 followed by two more digits, so
this could be any number from 4600 to 4699) must look like
6#2. In other words, the square root also starts with a
6. For example, if we take say 4678, it turns out that
682 is the largest perfect square smaller than it.
We can extend this again in just the same way. The largest perfect
square less than or equal a number like 4678## will look like
68#2. So if choose say 467853, we'll discover that
6832 is the largest perfect square smaller than it and
so on.
So by arranging a number in groups of two and working our way from the
left to the right, we can eventually find the largest perfect square
less than or equal to the number.
Let's first see why we can extend the square root like this.
Suppose n2 is the largest perfect square less than or
equal to a given number N. We can state this as:
: n2 ≤ N < N+1 ≤ (n+1)2
Multiplying throughout by 100, we get
: 100n2 ≤ 100N < 100(N+1) ≤ 100(n+1)2
which we can rewrite as
: (10n)2 ≤ 100N < 100N+100 ≤ (10(n+1))2
Now if s is any number of the form N## (that is, N
followed by a couple of digits) you can verify that
: 100N ≤ s < 100N+100
Combining this with the previous inequality, we can conclude that
: (10n)2 ≤ s < (10(n+1))2
Now (10n)2 itself is a perfect square smaller than
s, so the largest perfect square, say p2 ≤ s
must also satisfy
: (10n)2 ≤ p2 ≤ s < (10(n+1))2
which implies
: 10n ≤ p < 10(n+1) = 10n+10
In other words, p itself must be of the form n#2.
Notice that s doesn't have to be an integer, so the technique
works for numbers with a fractional part as well.
Let's now understand how the method actually finds the
largest perfect square less than or equal to our number.
Remember that we're looking at longer and longer
prefixes of the number after we've grouped them
by twos, and let's work with our earlier example
: 46 78 53 99
The first step is really easy to understand. From our
earlier analysis, we know that the square root must begin
with a 6, because 62 is the largest perfect
square smaller than the first group of digits 46.
We've already got a table of perfect squares on the square root bone,
and the procedure compares it with the first group of digits 46 to get
the first digit of the square root 6, so you can see why this works.
Now we've got to find the largest perfect square less than the first
two groups of digits in the number. Let's call the number formed by
the first two groups of digits S1 (so in our example
S1 would be 4678.)
Let a be the first digit of the square root we already found
(which is 6.) Our goal now is to find the next digit say b, such
that <ab>2 is the largest perfect square less
than or equal to S1. (<ab> is the number
formed by the digits a and b, not the product.)
In other words, we want to find the digit b where
: S1 = (10a+b)2 + k
and k ≥ 0 is as small as possible.
But observe that the next step in the procedure is to find the
remainder, and you can verify that our method to find the
remainder actually computes
: R1 = S1 - 100a2
where R1 is the remainder which is 1078 in our example.
Expressing this using the previous equation, we can write the
remainder as
: R1 = (10a+b)2 + k - 100a2
: = 10(2a)b + b2 + k
where k ≥ 0 is as small as possible.
Now comes the key trick behind Napier's method to extract the square
root. We set the value of the second column in the square root bone on
the board. But the second column is twice the third column, so we
actually set 2a (which is 2*6 = 12 in our example) on the board.
The board now forms a multiplication table for the number 2a. But
if you read it in conjunction with first nine squares on the square
root bone, you can verify that the board forms a table of numbers of
the form
: 10(2a)n + n2
for every digit n. So in our example when we place the
bones for 2a = 2*6 = 12 on the board, we actually create
this table of numbers
| border="1" cellpadding="2" cellspacing="0" style="background:#ffdead;"
! | 1 | 2 | √ | |
| align=right
| 1 | 0/1 | 0/2 | 0/1 2 1 | 10*(2*6)*1 + 12 = 121 |
| align=right
| 2 | 0/2 | 0/4 | 0/4 4 2 | 10*(2*6)*2 + 22 = 244 |
| align=right
| 3 | 0/3 | 0/6 | 0/9 6 3 | 10*(2*6)*3 + 32 = 369 |
| align=right
| 4 | 0/4 | 0/8 | 1/6 8 4 | 10*(2*6)*4 + 42 = 496 |
| align=right
| 5 | 0/5 | 1/0 | 2/5 10 5 | 10*(2*6)*5 + 52 = 625 |
| align=right
| 6 | 0/6 | 1/2 | 3/6 12 6 | 10*(2*6)*6 + 62 = 756 |
| align=right
| 7 | 0/7 | 1/4 | 4/9 14 7 | 10*(2*6)*7 + 72 = 889 |
| align=right
| 8 | 0/8 | 1/6 | 6/4 16 8 | 10*(2*6)*8 + 82 = 1024 |
| align=right
| 9 | 0/9 | 1/8 | 8/1 18 9 | 10*(2*6)*9 + 92 = 1161 |
But we just saw that the remainder R1 = 1078 is of the
form
: 10*(2a)b + b2 + k
where k ≥ 0 is as small as possible. So we can easily figure
out b by picking the largest entry in the above table which is
smaller than the remainder.
In this case, b must be 8 because that's the row which makes k
as small as possible without making it negative. So we've figured out
that 682 is the largest perfect square smaller than 4678.
Let's continue the process. We now want to find the largest perfect
square less than or equal to the first three group of digits. Let's
write the number formed by the first three groups of digits as
S2, which is 467853 in our example.
As usual, we first compute the remainder R2 = 5453,
and you can verify that the process actually computes
- the previous remainder R1
- take away the row value 10*(2a)b + b2
- append the next pair of digits S2 - 100S1
which means we can write
: R2 = 100(R1 - 10*(2a)b - b2) + (S2 - 100S1)
Substitute for R1 our previous equation
: R1 = S1 - 100a2
and after some simplification, we get
: R2 = S2 - 100(10a+b)2
Now recall that our goal at this point is to figure out the third digit
c of the largest perfect square <abc>2
which is less than or equal to our current prefix S2.
In other words, we want to discover c where
: S2 = (100a+10b+c)2 + k
and k ≥ 0 is as small as possible.
Using this in our equation for the remainder, we can
write
: R2 = (100a+10b+c)2 + k - 100(10a+b)2
: = (100*2a + 10*2b)c + c2 + k
and k ≥ 0 is as small as possible.
The next step in the procedure is to rearrange the board.
We start with the current number on it, which is 2a,
and append to it the value in the second column which
is 2b. If 2b has two digits, then we first
append the first digit to 2a, and you can verify
that this procedure just sets the number on the
board to 10*2a + 2b.
In our example, a is 6 and b is 8, and we end up with
: 10*2*6 + 2*8 = 136
on the board. When we read the board in conjunction with the square
root bone, it forms a table of numbers of the form
: 10(10*2a + 2b)n + n2
for every digit n. So when we set the number 136 on the
board, we're really creating this table of numbers
| border="1" cellpadding="2" cellspacing="0" style="background:#ffdead;"
! | 1 | 3 | 6 | √ | |
| align=right
| 1 | 0/1 | 0/3 | 0/6 | 0/1 2 1 | (100*2*6 + 10*2*8)*1 + 12 = 1361 |
| align=right
| 2 | 0/2 | 0/6 | 1/2 | 0/4 4 2 | (100*2*6 + 10*2*8)*2 + 22 = 2724 |
| align=right
| 3 | 0/3 | 0/9 | 1/8 | 0/9 6 3 | (100*2*6 + 10*2*8)*3 + 32 = 4089 |
| align=right
| 4 | 0/4 | 1/2 | 2/4 | 1/6 8 4 | (100*2*6 + 10*2*8)*4 + 42 = 5456 |
| align=right
| 5 | 0/5 | 1/5 | 3/0 | 2/5 10 5 | (100*2*6 + 10*2*8)*5 + 52 = 6825 |
| align=right
| 6 | 0/6 | 1/8 | 3/6 | 3/6 12 6 | (100*2*6 + 10*2*8)*6 + 62 = 8196 |
| align=right
| 7 | 0/7 | 2/1 | 4/2 | 4/9 14 7 | (100*2*6 + 10*2*8)*7 + 72 = 9569 |
| align=right
| 8 | 0/8 | 2/4 | 4/8 | 6/4 16 8 | (100*2*6 + 10*2*8)*8 + 82 = 10944 |
| align=right
| 9 | 0/9 | 2/7 | 5/4 | 8/1 18 9 | (100*2*6 + 10*2*8)*9 + 92 = 12321 |
Once again, picking the largest value from this table smaller than the
remainder gives us our digit c which is 3. At this point,
we've found out that 6832 is the largest perfect square
less than or equal to 467853.
You can continue analyzing the technique in this manner and find
that the remainder R3 in the next step is
: R3 = S3 - 1000(100a+10b+c)2
and S3 is the number formed by the first four groups
of digits, which in our case is 46785399, also the entire number.
We want to find the fourth digit d where <abcd>2
is the largest perfect square smaller than S3, so
we need to discover d where
: S3 = (1000a+100b+10c+d)2 + k
and k ≥ 0 is as small as possible. Using this in the
previous equation, we find
: R3 = (1000*2a + 100*2b+10*2c)d + d2 + k
and k ≥ 0 is as small as possible.
The number we set on the board is the second column from the square
root bone 2c added to ten times the previous number on
the board 10*2a+2b, so the new number is
: 100*2a + 10*2b + 2c
and in conjunction with the square root bone we get a table of
the form
: (1000*2a+100*2b+10*2c)n + n2
for every digit n, and we use this to discover the
digit d.
You can use a similar analysis to analyze the method for larger
numbers, and show why this produces the integer portion of the square
root.
We won't fully show why continuing the process gives the fractional
digits of the square root, but one way to understand it is to first
observe that since (say) 262 is the largest perfect square
smaller than 700, we can write
: 262 ≤ 700 < 272
We can then divide everything by 100 to conclude that
: 2.62 ≤ 7 < 2.72
so we can see that the square root of 7 must be something like
2.6###...
In other words, if we've found the largest perfect square smaller than
100 times our number, we've also found the first fractional digit
of our square root.
Similarly, you can check that the largest perfect square smaller than
10000 times our number also gives us the first two fractional digits
of our square root, and so on.
When our procedure computes the fractional digits of the square
root, we really multiply the number by 100, 10000, 1000000 and so on
and find the largest perfect squares smaller than each of them to
figure out further fractional digits of the number.
Making this argument more formal will prove why the process generates
the fractional digits but we won't elaborate it here.
Extracting Cube Roots
Extracting the cube root uses an additional bone which has three
columns on it. The first column has the first nine cubes
1, 8, 27, ... 512, 729. The second column has the first nine
squares 1, 4, 9, ... 64, 81. The third column just has the
numbers 1 through nine.
| border="1" cellpadding="2" cellspacing="0" style="background:#ffd78c;border:thick double #ffc731;"
|+ Napier's rods with the cube root bone ! | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 3√ |
| align=right
| 1 | 0/1 | 0/2 | 0/3 | 0/4 | 0/5 | 0/6 | 0/7 | 0/8 | 0/9 | 0/01 1 1 |
| align=right
| 2 | 0/2 | 0/4 | 0/6 | 0/8 | 1/0 | 1/2 | 1/4 | 1/6 | 1/8 | 0/08 4 2 |
| align=right
| 3 | 0/3 | 0/6 | 0/9 | 1/2 | 1/5 | 1/8 | 2/1 | 2/4 | 2/7 | 0/27 9 3 |
| align=right
| 4 | 0/4 | 0/8 | 1/2 | 1/6 | 2/0 | 2/4 | 2/8 | 3/2 | 3/6 | 0/64 16 4 |
| align=right
| 5 | 0/5 | 1/0 | 1/5 | 2/0 | 2/5 | 3/0 | 3/5 | 4/0 | 4/5 | 1/25 25 5 |
| align=right
| 6 | 0/6 | 1/2 | 1/8 | 2/4 | 3/0 | 3/6 | 4/2 | 4/8 | 5/4 | 2/16 36 6 |
| align=right
| 7 | 0/7 | 1/4 | 2/1 | 2/8 | 3/5 | 4/2 | 4/9 | 5/6 | 6/3 | 3/43 49 7 |
| align=right
| 8 | 0/8 | 1/6 | 2/4 | 3/2 | 4/0 | 4/8 | 5/6 | 6/4 | 7/2 | 5/12 64 8 |
| align=right
| 9 | 0/9 | 1/8 | 2/7 | 3/6 | 4/5 | 5/4 | 6/3 | 7/2 | 8/1 | 7/29 81 9 |
Let's find the cube root of 22022635627 with the bones.
First, group its digits in threes starting from the right so
it looks like this:
: 22 022 635 627
Start with the leftmost group 22. Pick the largest cube on the
cube root bone less than or equal to 22, which is 8 from the
second row.
Because we picked the second row, the first digit of the solution is 2.
Subtract the cube 8 from 22 to get 14, and append the next group
of digits 022 to get the current remainder 14022.
Now place three times the current solution
: 3*2 = 6
on the leftmost end of the board. Multiply this number once
more by the current solution 2 to get
: 6*2 = 12
and place 12 on the right side next to the cube root bone. At this
point, the board and intermediate calculations should look like this.
| border="0" cellpadding="2" cellspacing="0" | |||||
| valign="top"
| {| border="1" cellpadding="2" cellspacing="0" align=left style="background:#ffd78c;border:thick double #ffc731;" ! | 6 | style="width:9em"| | 1 | 2 | 3√ |
| align=right
| 1 | 0/6 | 0/1 | 0/2 | 0/01 1 1 | |
| align=right
| 2 | 1/2 | 0/2 | 0/4 | 0/08 4 2 | |
| align=right
| 3 | 1/8 | 0/3 | 0/6 | 0/27 9 3 | |
| align=right
| 4 | 2/4 | 0/4 | 0/8 | 0/64 16 4 | |
| align=right
| 5 | 3/0 | 0/5 | 1/0 | 1/25 25 5 | |
| align=right
| 6 | 3/6 | 0/6 | 1/2 | 2/16 36 6 | |
| align=right
| 7 | 4/2 | 0/7 | 1/4 | 3/43 49 7 | |
| align=right
| 8 | 4/8 | 0/8 | 1/6 | 5/12 64 8 | |
| align=right
| 9 | 5/4 | 0/9 | 1/8 | 7/29 81 9 |
|
______________
|22 022 635 627 = 2
8
--
14 022
|}
Ignore the 6 bone (and use just the first column from the
cube root bone) and "read" the number in each row. For
example, read the sixth row as
: 0/6 1/2 2/16 → 7416
Now find the row with largest number less than the current remainder,
14022. You should find that 11529 from the ninth row is the largest
value less than 14022.
We're now working with the ninth row of the cube root bone. Multiply
the number in the second column of the cube root bone 81 with the
value on the left end of the board 6. Append a 0 to this result, and
add it to 11529.
This sounds more complicated than it actually is, as you can do these
steps quite conveniently with the bones. First write down the row
value from the right side of the board, 11529. Like regular
multiplication, we're going to multiply the number on the left side of
the board by 81. So write below 11529 the value on row 1 from the
left side of the board. Then write below it the value on row 8 and
add them all together.
11529
6 ← 1*6
48 ← 8*6
-----
16389
The only point to remember here is to shift the first row by one
instead of writing it directly below the number. Everything else
is similar to doing long multiplication with the bones.
Now compare the result with our remainder 14022. It's larger
than the remainder, so discard this result and repeat the operation
with the row above it -- the eighth row.
Once more, write down the value of the eighth row 10112. Read the
second column of the cube root bone 64 and multiply it by the value at
the left end of the board, 6. As before, write down the value of
fourth row 24 beneath 10112, and then the value of the sixth row 36
below that, and add them all together. This is how the arithmetic
should look.
10112
24 ← 4*6
36 ← 6*6
-----
13952
Now this value is indeed smaller than our remainder, so we've
got the second digit of the cube root, 8. Subtract 13952
from our current remainder 14022 to get 70, and append the
next group of digits 635 to get the current remainder 70635.
Now place three times the current solution 28
: 3*28 = 84
on the left side of the board. Multiply this once more
by 28
: 84*28 = 2352
and set that number on the right side of the board next
to the cube root bone.
As these numbers get bigger you can use the bones themselves to find
these values, but we won't demonstrate that process.
At this point, the board and intermediate calculations should
look like this.
| border="0" cellpadding="2" cellspacing="0" | ||||||||
| valign="top"
| {| border="1" cellpadding="2" cellspacing="0" align=left style="background:#ffd78c;border:thick double #ffc731;" ! | 8 | 4 | style="width:6em"| | 2 | 3 | 5 | 2 | 3√ |
| align=right
| 1 | 0/8 | 0/4 | 0/2 | 0/3 | 0/5 | 0/2 | 0/01 1 1 | |
| align=right
| 2 | 1/6 | 0/8 | 0/4 | 0/6 | 1/0 | 0/4 | 0/08 4 2 | |
| align=right
| 3 | 2/4 | 1/2 | 0/6 | 0/9 | 1/5 | 0/6 | 0/27 9 3 | |
| align=right
| 4 | 3/2 | 1/6 | 0/8 | 1/2 | 2/0 | 0/8 | 0/64 16 4 | |
| align=right
| 5 | 4/0 | 2/0 | 1/0 | 1/5 | 2/5 | 1/0 | 1/25 25 5 | |
| align=right
| 6 | 4/8 | 2/4 | 1/2 | 1/8 | 3/0 | 1/2 | 2/16 36 6 | |
| align=right
| 7 | 5/6 | 2/8 | 1/4 | 2/1 | 3/5 | 1/4 | 3/43 49 7 | |
| align=right
| 8 | 6/4 | 3/2 | 1/6 | 2/4 | 4/0 | 1/6 | 5/12 64 8 | |
| align=right
| 9 | 7/2 | 3/6 | 1/8 | 2/7 | 4/5 | 1/8 | 7/29 81 9 |
|
______________
|22 022 635 627 = 28
8
--
14 022
13 952
------
70 635
|}
Continue by reading the values on the right side of the board to
find the largest row smaller than the current remainder 70635.
You'll discover that even the smallest value from the first row 235201
is larger than the remainder. In such cases, append a zero to the
solution, append a zero bone to the left side of the board and append
two zeros on the right side of the board. Finally append the next group
to the remainder, and at this point the board and intermediate
calculations should look like this.
| border="0" cellpadding="2" cellspacing="0" | |||||||||||
| valign="top"
| {| border="1" cellpadding="2" cellspacing="0" align=left style="background:#ffd78c;border:thick double #ffc731;" ! | 8 | 4 | 0 | style="width:3em"| | 2 | 3 | 5 | 2 | 0 | 0 | 3√ |
| align=right
| 1 | 0/8 | 0/4 | 0/0 | 0/2 | 0/3 | 0/5 | 0/2 | 0/0 | 0/0 | 0/01 1 1 | |
| align=right
| 2 | 1/6 | 0/8 | 0/0 | 0/4 | 0/6 | 1/0 | 0/4 | 0/0 | 0/0 | 0/08 4 2 | |
| align=right
| 3 | 2/4 | 1/2 | 0/0 | 0/6 | 0/9 | 1/5 | 0/6 | 0/0 | 0/0 | 0/27 9 3 | |
| align=right
| 4 | 3/2 | 1/6 | 0/0 | 0/8 | 1/2 | 2/0 | 0/8 | 0/0 | 0/0 | 0/64 16 4 | |
| align=right
| 5 | 4/0 | 2/0 | 0/0 | 1/0 | 1/5 | 2/5 | 1/0 | 0/0 | 0/0 | 1/25 25 5 | |
| align=right
| 6 | 4/8 | 2/4 | 0/0 | 1/2 | 1/8 | 3/0 | 1/2 | 0/0 | 0/0 | 2/16 36 6 | |
| align=right
| 7 | 5/6 | 2/8 | 0/0 | 1/4 | 2/1 | 3/5 | 1/4 | 0/0 | 0/0 | 3/43 49 7 | |
| align=right
| 8 | 6/4 | 3/2 | 0/0 | 1/6 | 2/4 | 4/0 | 1/6 | 0/0 | 0/0 | 5/12 64 8 | |
| align=right
| 9 | 7/2 | 3/6 | 0/0 | 1/8 | 2/7 | 4/5 | 1/8 | 0/0 | 0/0 | 7/29 81 9 |
|
______________
|22 022 635 627 = 280
8
--
14 022
13 952
------
70 635 627
|}