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+<.@%: 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.

Essays/Continued Fractions

See also