Essays/Fibonacci Sequence

From J Wiki
Jump to: navigation, search

The n-th element F_n of the sequence 0 1 1 2 3 5 8 13 21 34 55 ... can be computed in a variety of ways:


Double recursion

f0a and f0b use the basic identity  F_n = F_{n-2} + F_{n-1} . f0c uses a cache of previously computed values.  f0d depends on the identity F_{n+k}^{} = F_k F_{n+1} + F_{k-1} F_n , whence F_{2n}^{} = F_{n+1}^2 - F_{n-1}^2 and F_{2n+1}^{} = F_{n+1}^2 + F_{n}^2 obtain by substituting n and n+1 for k .

f0a=: 3 : 'if. 1<y do. (y-2) +&f0a (y-1) else. y end.' M.

f0b=: (-&2 +&$: -&1) ^: (1&<) M.

F=: 0 1x
f0c=: 3 : 0
 if. y >: #F do. F=: F,(1+y-#F)$_1 end.
 if. 0 <: y{F do. y{F return. end.
 F=: F y}~ t=. (y-2) +&f0c (y-1)
 t
)

f0d=: 3 : 0 M.
 if. 2 >: y do. 1<.y
 else.
  if. y = 2*n=.<.y%2 do. (n+1) -&*:&f0d n-1 else. (n+1) +&*:&f0d n end.
 end.
)

Single recursion

f1a=: 3 : 0
 {. y f1a 0 1x
:
 if. *x do. (x-1) f1a +/\|.y else. y end.
)

f1b=: {.@($:&0 1x) : ((<:@[ $: +/\@|.@])^:(*@[))

Iteration

f2c n computes the (2^n)-th Fibonacci number. It implements Newton iteration on the polynomial p(x)=x^2-x-1 , one root of which is the golden ratio \phi.

f2a=: 3 : '{. +/\@|.^:y 0 1x'

f2b=: 3 : 0
 t=. 0 1x
 for. i.y do. t=. +/\ |. t end.
 {. t
)

f2c=: 3 : '{:"(1) 2 x: ((1 + *:) % (_1 + +:))^:y 0x'

Power of phi

Power of the golden ratio \phi. Because of the limited precision of 64-bit IEEE floating-point numbers this method is good only for n up to 63.

f3=: 3 : '<. 0.5 + (%:5) %~ (2 %~ 1+%:5)^y'

Continued fraction

The numerator of the continued fraction (+%)/0,n$1x as a rational number.

f4=: {. @ (2&x:) @ ((+%)/) @ (0 , $&1x)

Generating functions

f5a and f5b compute the Taylor series coefficients of  x \over 1-x-x^2 .  f5c computes the weighted Taylor coefficients of {1 \over \phi} e^{x/2} \, {\sinh \phi x} .  f5d n computes m=:<.n*phi^.10 terms of the Fibonacci sequence, formatting to n*m decimal places the number 1 \over x^2-x-1 where x=: 10x^n .

f5a=: (0 1&p. % 1 _1 _1&p.) t.
f5b=: (%-.-*:)t.

f5c=: (^@-: * 5&o.&.((-:%:5)&*)) t:

f5d=: 3 : 0
 phi=. -:1+%:5
 d=. y*<.y*phi^.10
 (-y) ".@(,&'x')\ 2}. (j. d) ": % _1 _1 1 p. 10x^y
)

Sum of binomial coefficients

The second variant below sums the back-diagonals of Pascal's triangle as a square upper triangular matrix.

f6a=: i. +/ .! i.@-
f6b=: [ { 0 , +//.@(!/~)@i.

Matrix power

Computing the n-th power of a triangular unit matrix by repeated squaring.

f7=: 3 : 0
 mp=. +/ .*
 {.{: mp/ mp~^:(I.|.#:y) 2 2$0 1 1 1x
)

Q and Z ring extensions

Based on Binet's formula

\;\;F_n = {1\over\sqrt 5} \left(\left( {{1+\sqrt 5}\over 2}\right)^n - \left( {{1-\sqrt 5}\over 2}\right)^n \right) = {{(1+\sqrt 5)^n-(1-\sqrt 5)^n} \over {2^n \sqrt 5}}

operations are done in \mathrm{Q}[\sqrt 5] and \mathrm{Z}[\sqrt 5] with powers computed by repeated squaring.

times=: (1 5&(+/ .*)@:* , (+/ .* |.)) " 1
pow  =: 4 : 'times/ 1 0 , times~^:(I.|.#:y) x' " 1 0
f8a  =: {. @ (0 1r5&times) @ (-/) @ ((1r2 1r2,:1r2 _1r2)&pow)

f8b  =: {:@(1 1x&pow) % 2x&^@<:

Rewrite Rules

Based on a suggestion by Viktor Cerovski. 0→1 and 1→0 1.

f9seq=: 3 : ';@:{&(1;0 1)^:y 0'

f9a  =: +/ @ f9seq
f9b  =: 0: ` (#@f9seq@<:) @. *

For example:

   f9seq&.> i.6
+-+-+---+-----+---------+---------------+
|0|1|0 1|1 0 1|0 1 1 0 1|1 0 1 0 1 1 0 1|
+-+-+---+-----+---------+---------------+
   f9a"0 i.4 5
  0   1    1    2    3
  5   8   13   21   34
 55  89  144  233  377
610 987 1597 2584 4181



See also

Durham University, U.K. See especially the Matrix Methods paper.



Contributed by Roger Hui.