Essays/Fibonacci Sequence
The n-th element 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 . f0c uses a cache of previously computed values. f0d depends on the identity , whence and 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 , one root of which is the golden ratio .
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'
Other variations are also viable.
Power of phi
Power of the golden ratio . Because of the limited precision of 64-bit IEEE floating-point numbers this method should be good only for n up to 63; in practice, it does a little better than that.
f3=: 3 : '<. 0.5 + (%:5) %~ (2 %~ 1+%:5)^y'
Comparing the result of this to another implementation, defined below, that has greater precision shows that f3 is good up to n of 70.
(f3=f8a"0) 60+i.12
1 1 1 1 1 1 1 1 1 1 1 0
A note here shows how to calculate phi to an arbitrary precision using a rational approximation.
That said, a concise way to approximate the golden ratio uses a continued fraction with an arbitrary length sequence of 1
s. For example: (+%)/40#1
. So, we can pre-calculate phi to an arbitrary precision, and use that to find early members of the fibonacce sequence. For example:
f3a=: 0.5 <.@+ (_1+2*phi) %~ (phi=:(+%)/1e3#1x) ^ ]
Continued fraction
The numerator of the continued fraction (+%)/0,n$1x as a rational number.
f4=: {. @ (2&x:) @ ((+%)/) @ (0 , $&1x)
Generating functions
The routines in this section no longer work as the primitive verb t. has been removed in current versions of J. If someone were to write a J version to calculate the Taylor coefficients (or, better yet, a Maclaurin series generator), it could be substituted in this section to revive these routines.
f5a and f5b compute the Taylor series coefficients of . f5c computes the weighted Taylor coefficients of . f5d n computes m=:<.n*phi^.10 terms of the Fibonacci sequence, formatting to n*m decimal places the number 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
operations are done in and with powers computed by repeated squaring.
times=: (1 5&(+/ .*)@:* , (+/ .* |.)) " 1
pow =: 4 : 'times/ 1 0 , times~^:(I.|.#:y) x' " 1 0
f8a =: {. @ (0 1r5×) @ (-/) @ ((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
- MathWorld
- On-line Encyclopedia of Integer Sequences A000045
- Wikipedia
- Lucas Sequences
- Fibonacci Resources by R.C. Johnson, Durham University, U.K. See especially the Matrix Methods paper.
- Fibonacci Index
- Fibonacci Sums
Contributed by Roger Hui.