Estimating square roots to several significant figures using arithmetic operations
Foreword:
Some weeks ago, I was travelling by car over long distances. To easy my boredom, I tried to estimate the square root of a large number (I used the odometer reading) using only pencil and paper. This is what I found.
Notation:
sqrt(x) = the square root of x
x^2 = x raised to the power of 2; the square of x
Introduction:
This square root estimation method relies only on integer manipulations. As such, the calculations are reasonably straight forward. In each iteration, one division operation is required. However, these division operations should be very straightforward as only one significant figure is required. Each iteration will result in an additional significant figure of accuracy.
In the estimation of square roots, one can use the extremely exhaustive method of trail and error to continuously improve on the estimation accuracy. However, the multiplications rapidly become tedious as more digits are added to the estimation. Also, each trail does not guarantee an improvement of one significant figure.
The method presented here will take advantage of the fact that the sum of the first n odd numbers equals n^2. In this example, the approach taken is to approach the square root by adding another digit to the estimation. Hence, an estimation of sqrt(3) would be approached using this path:
1
1.7
1.73
1.732
1.7320
1.73205
…
It should be noted that the last significant digit in the estimate is never rounded up. Care should be taken in this respect. This is to done to simplify the calculations such that all iterations add to the previous estimate, instead of adding and subtracting. Of course, the algorithm can easily be modified to round up the last digit, if desired.
Sum of gnomons:
Gnomons- consecutive odd numbers
This is a list of the first few odd numbers-
1, 3, 5, 7, 9, 11, 13, 15…
The sum of the first 2 odd numbers is 1 + 3 = 4 = 2^2
The sum of the first 3 odd numbers is 1 + 3 + 5 = 9 = 3^2
The sum of the first 4 odd numbers is 1 + 3 + 5 + 7 = 16 = 4^2
The sum of the first 5 odd numbers is 1 + 3 + 5 + 7 + 9 = 25 = 5^2
The n-th odd number can be expressed as (2n-1). For example, the third odd number is (2*3 -1) = 5
Estimation procedure:
The procedure shown here will be based on estimating sqrt(56720).
We first partition the number 56720 into segments of 2 digits:
5 67 20
n^2 = 56720
Dividing both sides by 10,000:
(n/100)^2 = 56,720 / 10,000
(n/100)^2 = 5.6720
By inspection, the largest integer for (n/100) that would NOT exceed 5.6720 is 2. Therefore, the first estimate:
n/100 = 2
2^2 = 4
(n/100)^2 = 4
n = 200
n^2 = 40,000
Evidently, our first estimate (n=200) is crude, and its nowhere near the actual value of sqrt(56720).
Going back to our number:
n^2 = 56,720
divide both sides by 100:
(n/10)^2 = 567
Compare this to our earlier estimate of n = 200:
(200/10)^2 = 400
20^2 = 400
From the sum of odd numbers, we know that the sum of the first 20 odd numbers is 20^2. Therefore:
1 + 3 + 5 + … + (2*20-1) = 400
1 + 3 + 5 + … + 39 = 400
Extending the series by adding 4 terms:
1 + 3 + 5 + … + 39 + 41 + 43 + 45 + 47 + 49 = 625 = 25^2
Re-expressing the new terms:
1 + 3 + 5 + … + 39 + (39+2) + (39+4) + (39+6) + (39+8) + (39+10) = 625
1 + 3 + 5 + … + 39 + (39*5 + 2 + 4 + 6 + 8 + 10) = 625
20^2 + (2*20-1)*5 + f(5) = 625 = 25^2, where f(5) is the sum of the first 5 even numbers.
As seen in the last equation, the sum of the first 20 odd numbers can be extended by 5 terms by adding the 5 times the 20th odd number and the sum of the first 5 even numbers [denoted by f(5)].
For convenience, the sum of the first n even numbers can be listed in form of a lookup table.
Returning our estimation:
(n/10)^2 = 567
We also know that 20^2 = 400
The difference between 567 and 400 is 567-400 = 167
We must increase our estimate of (n/10) as much as possible without exceeding 567.
The 20th odd number is 39. We will try to fit as many new terms as possible into the current series (now at 20 terms). Try 167/39 = 4.28 = 4.
4 * 39 = 156, and
f(4) = 2 + 4 + 6 + 8 = 20
4*39 + f(4) = 176
20^2 + 176 = 24^2 = 576
Unfortunately, 576 is larger than 567, so we will try 23^2 instead of 24^2:
20^2 + 39*3 + f(3) = 400 + 117 + 12 = 529
This is our current estimate of n/10 = 23.
(n/10)^2 = 529
n^2 = 52,900
230^2 = 52,900
Keep in mind that we are trying to approach n^2 = 56,720.
The difference between 56,720 and 52,900 is 56,720 – 52,900 = 3,820.
The 230th odd number is 459. Remember that the sum of the first 230 odd numbers (from 1 to 459) is 230^2 = 52,900.
3,820 / 459 = 8.322 = 8
459 * 8 = 3672
f(8) = 2 + 4 + 6 + 8 +10 + 12 +14 +16 = 72
230^2 + (459*8) + f(8) = 56,644 = 238^2
Just to be sure, can we try 239^2?
238^2 + (2*238-1) +f(1) = 56,644 + 475 + 2 = 57,121
No, 239^2 is larger than 56,720, so our current estimate of sqrt(56720) is 239
n^2=56,720
(10n)^2 = 5,672,000
And our current estimate:
238^2 = 56,644
(10*238)^2 = 5,664,400
The difference between 5,672,000 and 5,664,400 is 7600.
The 2,380th odd number is 4,759.
7,600 / 4,759 = 1.63 = 1
2,390^2 + 4,759*1 + f(1) = 5,669,161 = 2,381^2
Our latest estimate of 10n = 2381, and n = 238.1
n^2 = 56,720
(100n)^2 = 567,200,000
238.1^2 = 5,669,161
23,810^2 = 566,916,100
The difference between 567,200,000 and 566,916,100 is 283,900
The 23810th odd number is (2*23810-1) = 47,619
283,900 / 47,619 = 5.96 = 5
5*47619 = 238,095
f(5) = 2 + 4 +6 + 8 + 10 = 30
23810^2 + (2*23810 -1)*5 + f(5) = 567,154,225
The latest estimate of 100n = 23815; n = 238.15
The subsequent iterations will no longer contain any narration.
n^2 = 56720
(1000n)^2 = 56,720,000,000
238.15^2 = 56,715.4225
238150 = 56,715,422,500
56,720,000,000 - 56,715,422,500 = 4,577,500
(2*238150 – 1) = 476,299
4,577,500 / 476,299 = 9.61 = 9
9*476,229 = 4286061
f(9) = 2 + 4 +6 + 8 + 10 + 12 + 14 + 16+ 18 = 90
238150^2 + (2*238150 – 1)*9 + f(9) = 56,715,422,500 + 4,173,291 + 90 = 5,671,970,928,100
238,159^2 = 5,671,970,928,100
238.159 ^2 = 56,719.70928100
2,381,590 ^2 = 5,671,970,928,100
5,672,000,000,000 - 5,671,970,928,100= 29,071,900
(2*2,381,590 -1) = 4,763,179
29,071,900 / 4,763,179 = 6.10 = 6
(2*2,381,590 -1)*6 = 28,579,074
f(6) = 2 + 4 +6 +8 + 10 +12 = 42
2381590^2 + (2*2,381,590 -1)*6 + 42 = 5,671,999,507,216
2381596^2 = 5,671,999,507,216
238.1596 = 56719.995…
Using an electronic calculator to verify the results:
sqrt(56720) = 238.1596103…
We are definitely on the right track.
Cite this article as:
Tan Yee Wei(2005), "Estimating square roots to several significant figures using arithmetic operations", from "Snippets of This and That"
http://tanyeewei.blogspot.com/2005/07/estimating-square-roots-to-several.html
Some weeks ago, I was travelling by car over long distances. To easy my boredom, I tried to estimate the square root of a large number (I used the odometer reading) using only pencil and paper. This is what I found.
Notation:
sqrt(x) = the square root of x
x^2 = x raised to the power of 2; the square of x
Introduction:
This square root estimation method relies only on integer manipulations. As such, the calculations are reasonably straight forward. In each iteration, one division operation is required. However, these division operations should be very straightforward as only one significant figure is required. Each iteration will result in an additional significant figure of accuracy.
In the estimation of square roots, one can use the extremely exhaustive method of trail and error to continuously improve on the estimation accuracy. However, the multiplications rapidly become tedious as more digits are added to the estimation. Also, each trail does not guarantee an improvement of one significant figure.
The method presented here will take advantage of the fact that the sum of the first n odd numbers equals n^2. In this example, the approach taken is to approach the square root by adding another digit to the estimation. Hence, an estimation of sqrt(3) would be approached using this path:
1
1.7
1.73
1.732
1.7320
1.73205
…
It should be noted that the last significant digit in the estimate is never rounded up. Care should be taken in this respect. This is to done to simplify the calculations such that all iterations add to the previous estimate, instead of adding and subtracting. Of course, the algorithm can easily be modified to round up the last digit, if desired.
Sum of gnomons:
Gnomons- consecutive odd numbers
This is a list of the first few odd numbers-
1, 3, 5, 7, 9, 11, 13, 15…
The sum of the first 2 odd numbers is 1 + 3 = 4 = 2^2
The sum of the first 3 odd numbers is 1 + 3 + 5 = 9 = 3^2
The sum of the first 4 odd numbers is 1 + 3 + 5 + 7 = 16 = 4^2
The sum of the first 5 odd numbers is 1 + 3 + 5 + 7 + 9 = 25 = 5^2
The n-th odd number can be expressed as (2n-1). For example, the third odd number is (2*3 -1) = 5
Estimation procedure:
The procedure shown here will be based on estimating sqrt(56720).
We first partition the number 56720 into segments of 2 digits:
5 67 20
n^2 = 56720
Dividing both sides by 10,000:
(n/100)^2 = 56,720 / 10,000
(n/100)^2 = 5.6720
By inspection, the largest integer for (n/100) that would NOT exceed 5.6720 is 2. Therefore, the first estimate:
n/100 = 2
2^2 = 4
(n/100)^2 = 4
n = 200
n^2 = 40,000
Evidently, our first estimate (n=200) is crude, and its nowhere near the actual value of sqrt(56720).
Going back to our number:
n^2 = 56,720
divide both sides by 100:
(n/10)^2 = 567
Compare this to our earlier estimate of n = 200:
(200/10)^2 = 400
20^2 = 400
From the sum of odd numbers, we know that the sum of the first 20 odd numbers is 20^2. Therefore:
1 + 3 + 5 + … + (2*20-1) = 400
1 + 3 + 5 + … + 39 = 400
Extending the series by adding 4 terms:
1 + 3 + 5 + … + 39 + 41 + 43 + 45 + 47 + 49 = 625 = 25^2
Re-expressing the new terms:
1 + 3 + 5 + … + 39 + (39+2) + (39+4) + (39+6) + (39+8) + (39+10) = 625
1 + 3 + 5 + … + 39 + (39*5 + 2 + 4 + 6 + 8 + 10) = 625
20^2 + (2*20-1)*5 + f(5) = 625 = 25^2, where f(5) is the sum of the first 5 even numbers.
As seen in the last equation, the sum of the first 20 odd numbers can be extended by 5 terms by adding the 5 times the 20th odd number and the sum of the first 5 even numbers [denoted by f(5)].
For convenience, the sum of the first n even numbers can be listed in form of a lookup table.
| n | f(n) | |
| 1 | 2 | 2 |
| 2 | 2+4 | 6 |
| 3 | 2+4+6 | 12 |
| 4 | 2+4+6+8 | 20 |
| 5 | 2+4+...10 | 30 |
| 6 | 2+4+...12 | 42 |
| 7 | 2+4+...14 | 56 |
| 8 | 2+4+...16 | 72 |
| 9 | 2+4+...18 | 80 |
Returning our estimation:
(n/10)^2 = 567
We also know that 20^2 = 400
The difference between 567 and 400 is 567-400 = 167
We must increase our estimate of (n/10) as much as possible without exceeding 567.
The 20th odd number is 39. We will try to fit as many new terms as possible into the current series (now at 20 terms). Try 167/39 = 4.28 = 4.
4 * 39 = 156, and
f(4) = 2 + 4 + 6 + 8 = 20
4*39 + f(4) = 176
20^2 + 176 = 24^2 = 576
Unfortunately, 576 is larger than 567, so we will try 23^2 instead of 24^2:
20^2 + 39*3 + f(3) = 400 + 117 + 12 = 529
This is our current estimate of n/10 = 23.
(n/10)^2 = 529
n^2 = 52,900
230^2 = 52,900
Keep in mind that we are trying to approach n^2 = 56,720.
The difference between 56,720 and 52,900 is 56,720 – 52,900 = 3,820.
The 230th odd number is 459. Remember that the sum of the first 230 odd numbers (from 1 to 459) is 230^2 = 52,900.
3,820 / 459 = 8.322 = 8
459 * 8 = 3672
f(8) = 2 + 4 + 6 + 8 +10 + 12 +14 +16 = 72
230^2 + (459*8) + f(8) = 56,644 = 238^2
Just to be sure, can we try 239^2?
238^2 + (2*238-1) +f(1) = 56,644 + 475 + 2 = 57,121
No, 239^2 is larger than 56,720, so our current estimate of sqrt(56720) is 239
n^2=56,720
(10n)^2 = 5,672,000
And our current estimate:
238^2 = 56,644
(10*238)^2 = 5,664,400
The difference between 5,672,000 and 5,664,400 is 7600.
The 2,380th odd number is 4,759.
7,600 / 4,759 = 1.63 = 1
2,390^2 + 4,759*1 + f(1) = 5,669,161 = 2,381^2
Our latest estimate of 10n = 2381, and n = 238.1
n^2 = 56,720
(100n)^2 = 567,200,000
238.1^2 = 5,669,161
23,810^2 = 566,916,100
The difference between 567,200,000 and 566,916,100 is 283,900
The 23810th odd number is (2*23810-1) = 47,619
283,900 / 47,619 = 5.96 = 5
5*47619 = 238,095
f(5) = 2 + 4 +6 + 8 + 10 = 30
23810^2 + (2*23810 -1)*5 + f(5) = 567,154,225
The latest estimate of 100n = 23815; n = 238.15
The subsequent iterations will no longer contain any narration.
n^2 = 56720
(1000n)^2 = 56,720,000,000
238.15^2 = 56,715.4225
238150 = 56,715,422,500
56,720,000,000 - 56,715,422,500 = 4,577,500
(2*238150 – 1) = 476,299
4,577,500 / 476,299 = 9.61 = 9
9*476,229 = 4286061
f(9) = 2 + 4 +6 + 8 + 10 + 12 + 14 + 16+ 18 = 90
238150^2 + (2*238150 – 1)*9 + f(9) = 56,715,422,500 + 4,173,291 + 90 = 5,671,970,928,100
238,159^2 = 5,671,970,928,100
238.159 ^2 = 56,719.70928100
2,381,590 ^2 = 5,671,970,928,100
5,672,000,000,000 - 5,671,970,928,100= 29,071,900
(2*2,381,590 -1) = 4,763,179
29,071,900 / 4,763,179 = 6.10 = 6
(2*2,381,590 -1)*6 = 28,579,074
f(6) = 2 + 4 +6 +8 + 10 +12 = 42
2381590^2 + (2*2,381,590 -1)*6 + 42 = 5,671,999,507,216
2381596^2 = 5,671,999,507,216
238.1596 = 56719.995…
Using an electronic calculator to verify the results:
sqrt(56720) = 238.1596103…
We are definitely on the right track.
Cite this article as:
Tan Yee Wei(2005), "Estimating square roots to several significant figures using arithmetic operations", from "Snippets of This and That"
http://tanyeewei.blogspot.com/2005/07/estimating-square-roots-to-several.html
posted by Tan Yee Wei at 7/21/2005 02:51:00 pm
<< Home