User:Kbs

From Wikipedia, the free encyclopedia

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.

[edit] 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 6² = 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#². In other words, the square root also starts with a 6. For example, if we take say 4678, it turns out that 68² 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#². So if choose say 467853, we'll discover that 683² 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 n² is the largest perfect square less than or equal to a given number N. We can state this as:

n² ≤ N < N+1 ≤ (n+1)²

Multiplying throughout by 100, we get

100n² ≤ 100N < 100(N+1) ≤ 100(n+1)²

which we can rewrite as

(10n)² ≤ 100N < 100N+100 ≤ (10(n+1))²

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)² ≤ s < (10(n+1))²

Now (10n)² itself is a perfect square smaller than s, so the largest perfect square, say p² ≤ s must also satisfy

(10n)² ≤ p² ≤ s &lt (10(n+1))²

which implies

10n ≤ p < 10(n+1) = 10n+10

In other words, p itself must be of the form n#².

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 6² 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 S₁ (so in our example S₁ 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>² is the largest perfect square less than or equal to S₁. (<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

S₁ = (10a+b)² + 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

R₁ = S₁ - 100a²

where R₁ is the remainder which is 1078 in our example. Expressing this using the previous equation, we can write the remainder as

R₁ = (10a+b)² + k - 100a²

= 10(2a)b + b² + 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 + n²

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

But we just saw that the remainder R₁ = 1078 is of the form

10*(2a)b + b² + 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 68² 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 S₂, which is 467853 in our example.

As usual, we first compute the remainder R₂ = 5453, and you can verify that the process actually computes

• the previous remainder R₁
• take away the row value 10*(2a)b + b²
• append the next pair of digits S₂ - 100S₁

which means we can write

R₂ = 100(R₁ - 10*(2a)b - b²) + (S₂ - 100S₁)

Substitute for R₁ our previous equation

R₁ = S₁ - 100a²

and after some simplification, we get

R₂ = S₂ - 100(10a+b)²

Now recall that our goal at this point is to figure out the third digit c of the largest perfect square <abc>² which is less than or equal to our current prefix S₂.

In other words, we want to discover c where

S₂ = (100a+10b+c)² + k

and k ≥ 0 is as small as possible.

Using this in our equation for the remainder, we can write

R₂ = (100a+10b+c)² + k - 100(10a+b)²

= (100*2a + 10*2b)c + c² + 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 + n²

for every digit n. So when we set the number 136 on the board, we're really creating this table of numbers

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 683² 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 R₃ in the next step is

R₃ = S₃ - 1000(100a+10b+c)²

and S₃ 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>² is the largest perfect square smaller than S₃, so we need to discover d where

S₃ = (1000a+100b+10c+d)² + k

and k ≥ 0 is as small as possible. Using this in the previous equation, we find

R₃ = (1000*2a + 100*2b+10*2c)d + d² + 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 + n²

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) 26² is the largest perfect square smaller than 700, we can write

26² ≤ 700 < 27²

We can then divide everything by 100 to conclude that

2.6² ≤ 7 < 2.7²

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.

[edit] 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.

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.

 ______________
|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

⁰/₆ ¹/₂ ²/₁₆ → 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.

 ______________
|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.

 ______________
|22 022 635 627    =   280
  8
 --
 14 022
 13 952
 ------
     70 635 627