You can approximate irrational square roots with rational numbers using linear interpolation between the integers as follows:
√1 = 1
√2 ≈ 4/3
√3 ≈ 5/3
√4 = 2
√5 ≈ 11/5
√6 ≈ 12/5
√7 ≈ 13/5
√8 ≈ 14/5
√9 = 3
etc...
How good an approximation is this?
For large numbers, might the previous or next fraction be a better approximation?
I can only compare against a known method of approximating irrationals with rationals: continued fractions, the values of which can most easily be found using a variant of Euclid's algorithm for finding GCD: start with the number a 1 as dividend and divisor respectively. The quotient is used in a side panel to determine how many of each of the first two numbers (the number in question and 1) go into making a tinier number, and the remainder becomes the new divisor while the old divisor becomes the dividend.
Applied to the square root of 2:
1.4142135623731 1 0
1 0 1
.4142135623731 1 -1
.1715728752538001 -2 3
.07106781186549976 5 -7
.02943725152280058 -12 17
.0121933088198986 29 -41
The quotient in each case is used to multiply the previous values in column 2 and in column 3 to subtract from the value before that. So the quotient of .4142135623731 divided by .1715728752538001 is 2, so in column 2 the value 5 is derived by 1 - 2*(-2) and in column 3, the value -7 is derived by -1 - 2*3.
The results of this process are shown below, and, for example, 7/5 is a better approximation of sqrt(2) than is 4/3. For sqrt(3), 7/4 is a better approximation than 5/3. For sqrt(5), 9/4 is better than 11/5. For sqrt(6), 22/9 is closer than 12/5; for sqrt(7), 8/3 beats 13/5; for sqrt(8), 17/6 beats 14/5; etc. Each of these is using the same number or fewer digits than the interpolation method.
The below results don't show the successive remainders, but the quotient used in each case is shown off to the right. The absolute value of the two columns is shown as they represent the numerator and denominator of the new approximation.
1 1
1 1 1
2 1.4142135623731
1 1 1
3 2 2
7 5 2
17 12 2
41 29 2
99 70 2
239 169 2
577 408 2
3 1.73205080756888
1 1 1
2 1 1
5 3 2
7 4 1
19 11 2
26 15 1
71 41 2
97 56 1
4 2
2 1 2
5 2.23606797749979
2 1 2
9 4 4
38 17 4
161 72 4
682 305 4
2889 1292 4
12238 5473 4
51841 23184 4
6 2.44948974278318
2 1 2
5 2 2
22 9 4
49 20 2
218 89 4
485 198 2
2158 881 4
4801 1960 2
7 2.64575131106459
2 1 2
3 1 1
5 2 1
8 3 1
37 14 4
45 17 1
82 31 1
127 48 1
8 2.82842712474619
2 1 2
3 1 1
14 5 4
17 6 1
82 29 4
99 35 1
478 169 4
577 204 1
9 3
3 1 3
10 3.16227766016838
3 1 3
19 6 6
117 37 6
721 228 6
4443 1405 6
27379 8658 6
168717 53353 6
1039681 328776 6
from
DefDbl A-Z
Dim a(3), b(3), crlf$
Function mform$(x, t$)
f$ = Format$(x, t$)
If Len(f$) < Len(t$) Then f$ = Space$(Len(t$) - Len(f$)) & f$
mform$ = f$
End Function
Private Sub Form_Load()
Text1.Text = ""
crlf$ = Chr(13) + Chr(10)
Form1.Visible = True
For n = 1 To 10
x = Sqr(n)
Text1.Text = Text1.Text & n & Str(x) & crlf
dvd = x: dvr = 1
a(1) = 1: b(1) = 0
a(2) = 0: b(2) = 1
For gen = 1 To 8
If dvr = 0 Then Exit For
q = Int(dvd / dvr)
r = dvd - dvr * q
a(3) = a(1) - q * a(2): b(3) = b(1) - q * b(2)
a(1) = a(2): a(2) = a(3)
b(1) = b(2): b(2) = b(3)
dvd = dvr: dvr = r
Text1.Text = Text1.Text & mform(Abs(b(3)), "#######") & mform(Abs(a(3)), "#######") & " " & q & crlf
Next gen
Text1.Text = Text1.Text & crlf
Next
Text1.Text = Text1.Text & "done"
DoEvents
End Sub
|
|
Posted by Charlie
on 2015-02-17 16:31:49 |
discussion
