Essays/Continued Fractions
Continued fractions can be computed using the phrases (+%)/ and (+%)/\. For example:
(+%)/ 10$1 1.61818 (+%)/ 1,10$2 1.41421 (+%)/\ 10$1 1 2 1.5 1.66667 1.6 1.625 1.61538 1.61905 1.61765 1.61818 (+%)/\ 1,10$2 1 1.5 1.4 1.41667 1.41379 1.41429 1.4142 1.41422 1.41421 1.41421 1.41421 (+%)/\ 10$1x 1 2 3r2 5r3 8r5 13r8 21r13 34r21 55r34 89r55 (+%)/\ 1,10$2x 1 3r2 7r5 17r12 41r29 99r70 239r169 577r408 1393r985 3363r2378 8119r5741
As the last two examples show, using extended precision numbers gives rational approximations to the underlying quantities.
n cf y and the equivalent n cfx y compute n terms of the
continued fraction representation of y. For fixed-precision y, the
verbs are good only for small n due to the limited precision of
64-bit IEEE floating-point numbers.
cfx=: 4 : 0
z=. a=. <.r=. y
for. i.x do. z=. z, a=. <. r=. % r - a end.
)
cf=: 4 : '{:"1 (,<.)@%@-/^:(<x) (,<.) y'
20 cf (1+%:5)%2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
20 cf %:2
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
20 cf ^1
2 1 2 1 1 4 1 1 6 1 1 8 1 1 10 1 1 12 1 1
30 cf %:2
1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 3 3 1 3 1 1
40 cf (<.@o. % ]) 10^50x
3 7 15 1 292 1 1 1 2 1 3 1 14 2 1 1 2 2 2 2 1 84 2 1 1 15 3 13 1 4 2 6 6 99 1 2 2 6 3 5
Some continued fractions:
%:2 1 2 2 2 2 2 2 2 2 2 2 ... 1,n$2 %:3 1 1 2 1 2 1 2 1 2 1 2 ... 1,n$1 2 %:5 2 4 4 4 4 4 4 4 4 4 4 ... 2,n$4 %:6 2 2 4 2 4 2 4 2 4 2 4 ... 2,n$2 4 %:7 2 1 1 1 4 1 1 1 4 1 1 ... 2,n$1 1 1 4 %:8 2 1 4 1 4 1 4 1 4 1 4 ... 2,n$1 4 2 %~ 1+%:5 golden ratio 1 1 1 1 1 1 1 1 1 1 1 ... n$1 ^1 2 1 2 1 1 4 1 1 6 1 1 ... 2 , ,1,.(2+2*i.n),.1 2%~_1+^1 0 1 6 10 14 18 22 26 30 ... 0 1,6+4*i.n o. 1 3 7 15 1 292 1 1 1 2 1 ... OEIS A001203 3 o. 1 1 1 1 3 1 5 1 7 1 9 1 ... , 1 ,. 1+2*i.n 7 o. 1 0 1 3 5 7 9 11 13 15 17 ... 0 , 1+2*i.n 0.57721566490153 ... Euler's constant 0 1 1 2 1 2 1 4 3 13 5 ... OEIS A002852 *: -. 0.57721566490153 ... 0 5 1 1 2 6 1 8 372792 ... sci.math 1991
Continued fractions of quadratic irrationalities (irrational numbers that are solutions to some quadratic equation with integer coefficients) are periodic.
NB.*qcf v continued fraction for quadratic irrationality (a·√n+b)/c
NB. y = n,a,b,c
NB. Returns 2 boxed lists, first is non-periodic part, second is
NB. periodic part.
qcf=:(100&$:) : (4 : 0)
n=.x:{.y
if. n=*:t=.<.@%:n do. t;i.0 return. end.
'a b c'=.x:3{.1}.y,1 0 1
k=.0
lrs=.,:a,b,c NB. list of previous remainders to track period
cf=.i.0 NB. accumulated continued fraction
while. x>k=.k+1 do.
f=. <. c %~ b + <. a* %:n NB. save the sign of a (a*%:n instead of %:n**:a)
cf=.cf,f
NB. r'=1/((a·√n+b)/c - f)= (c·a·√n-c·(b-f·c))/(a²n-(b-f·c)²)
a1=.c*a
b1=.c*-b-f*c
c1=.(n**:a)-*:b-f*c
'a b c'=.t=.(% +./)a1,b1,c1
i=.lrs i. t
if. i<#lrs do.
(i{.cf);(i}.cf)
return.
end.
lrs=.lrs,t
NB. smoutput f;a,b,c
end.
cf;i.0
)
The argument to this function is 4 element list (n,a,b,c) which represents (a·√n+b)/c or a single number n which represents simply √n. The result is boxed list of 2 integer lists: first being the non-repeating part and second being periodic part of continued fraction.
Example: Solve the equation x(x+1)(x+2)(x+3)= 0.5625.
This equation of the fourth degree is special and can be reduced to two quadratic equations;
the four roots are -3/2 (double, local maximum), (-3+√10)/2 and (-3-√10)/2.
Source: A.G. Tsypkin / A.I. Pinsky, Methods of Solving Problems in High-School Mathematics, Mir Publishers, Moscow, 1983.
qcf 10 1 _3 2 NB. (-3+√10)/2 ┌─┬────┐ │0│12 3│ NB. 0 12 3 12 3 12 3 12 3 ··· └─┴────┘ (+%)/ 0 12 3 12 3 12 3 12 3 0.0811388 qcf 10 _1 _3 2 NB. (-3-√10)/2 ┌───────┬────┐ │_4 1 11│3 12│ NB. _4 1 11 3 12 3 12 3 12 3 12 ··· └───────┴────┘ (+%)/ _4 1 11 3 12 3 12 3 12 3 12 _3.08114
See also
MathWorld
On-line Encyclopedia of Integer Sequences
Contributed by Roger Hui, with additional contributions by Andrew Nikitin and Ewart Shaw.