Essays/Continued Fractions

From J Wiki
Jump to navigation Jump to search

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.