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.