nvec ← ##.fibonacci num                     ⍝ Tail-recursive Fibonacci.
                                            ⍝ Leonardo Fibonacci 1170-1250.

An illustration of tail recursion with a left argument accumulator:

    fibonacci←{     ⍝ Tail-recursive Fibonacci.
        ⍺←0 1
        ⍵=0:⍬⍴⍺
        (1↓⍺,+/⍺)∇ ⍵-1
    }

Compare this coding with the naïve stack-recursive version:

    fib←{
        ⍵∊0 1:⍵
        +/∇¨⍵-1 2
    }

Some alternatives:

Nick Nikolov and Jay Foad suggest:

    fib ← {⊃(+/,⊃)⍣⍵⊢1}
and:
    fib ← +.!∘⌽⍨⍳       ⍝ ⎕io←0

John R. Clark suggests these non-recursive functions:

    fib ← {+/{⍵!⌽⍵}(⍳⍵)-⎕io}            ⍝ JRC[1]
and
    fib ← {1↓⍎((3×⍵)⍴'⌽+\'),'1 0'}      ⍝ JRC[2]

JRC[1] may be cast as a derived function, using monadic commute:

    fib ← +/∘(!∘⌽⍨)∘(-∘⎕io)∘⍳           ⍝ see →tacit←

and JRC[2] may be converted to use the primitive power operator:

    fib ← {⍬⍴⌽∘(+\)⍣⍵,0 1}              ⍝ ⍣ is primitive power operator.

or the equivalent derived function, using reduction for power (see →pow←):

    fib ← ⍬∘⍴∘⊃∘(⊢∘⌽∘(+\)/)∘(,∘(⊂0 1))∘⍳

In a similar way, power can be applied on the following matrix multiplication:

    |1 1|   |A B|   |A+C B+D|
    |1 0| × |C D| = | A   B |

to obtain a terse but costly fib function:

    fib ← {⊃(+.×⍣⍵)⍨2 2⍴1 1 1 0}

Another simple way is to perform a "hidden scan" with a reduction (see →scan←):

    fib ← {⊃{⍵,+/¯2↑⍵}/⍵⍴1}

The following function illustrates the relationship between the  Fibonacci sequ-
ence and rational approximations to the "golden mean" (Phi). See →phinary←.

    fib←{1∧+∘÷/0,⍵/1}
         │ │   └───── continued fraction: 0 1 1 1 ...
         │ └───────── approximation to Phi-1: 0 1 0.5 0.666 ...
         └─────────── numerator of rational: 0 1 1 2 3 5 8 13 21 34 ...

Dick Bowman reminds us of Binet's formula, which also uses Phi:

    fib ← {((phi*⍵)-(1-phi←.5×1+5*.5)*⍵)÷5*.5}

Peter-Michael Hager suggests this pleasantly symmetrical coding of Binet's form-
ula:

    fib←{
        p←0.5×1+5*0.5
        q←0.5×1-5*0.5
        ((p*⍵)-q*⍵)÷p-q
    }

In the above, constants p and q could be pre-evaluated and bound as the left and
right operands of a dyadic operator:

    fib ← (0.5×1+5*0.5) {((⍺⍺*⍵)-⍵⍵*⍵)÷⍺⍺-⍵⍵} (0.5×1-5*0.5)

or:

    fib ← (0.5×1+1 ¯1×5*0.5)∘{(-⌿⍺∘.*⍵)÷-/⍺}

As  Binet's formula employs only scalar functions, it may be applied to an array
argument. Using the above definition:

    fib (0 1 2)(2 2⍴2+⍳4)
┌─────┬───┐
│0 1 1│2 3│
│     │5 8│
└─────┴───┘

Jane Sullivan extends Binet's formula to the real and complex domains.  A D-cod-
ind of Jane's real-valued function might look like this:

    fib←{                                           ⍝ Sullivan
        z←0.5×1+s←5*0.5
        ((z*⍵)-(2○○⍵)×z*-⍵)÷s
    }

Ref: Sullivan J. "Functional Extensions to the Fibonacci Sequence", Vector 15.4.

Note that Jane's function is defined for negative arguments:

    ⎕pp←3 ⋄ fib ¯5 ¯4.5 to 5                        ⍝ fib ¯5 ¯4.5 .. 5
5 0.0513 ¯3 0.083 2 0.134 ¯1 0.217 1 0.352 0 0.569 1 0.92 1 1.49 2 2.41 3 3.9 5

Veli-Matti Jantunen suggests this coding for large Fibonacci numbers, eg >10000.

    fib←{⎕ml←3
        ⍵≤2:1

        {(+/∧\⍵='0')↓⍵
        },'ZI9'⎕fmt(⍵-2){
            ⍺>0:(⍺-1)∇(↑⌽⍵)({
                ∧/⍵<1e9:⍵ ⋄ (1e9|⍵)+1⌽⍵≥1e9
            }(↑⍵)+↑⌽⍵) ⋄ ↑⌽⍵
        }2⍴⊂(-⌈⍵÷40)↑1
    }

Paul Mansour offers this function, which uses OO techniques:

    Fibonacci←{⎕io←0        ⍝ First ⍵ fibonacci numbers.
        s←⎕NS''             ⍝ Class
        s.(f←{⍺←⎕THIS ⋄ ⍺.i<2:⍺.n ⋄ ⊢⍺.n←+/⍺.a[⍺.i-1+⍳2].n}) ⍝ Method
        v←⎕NS¨⍵⍴s           ⍝ Collection
        v.i←⍳⍵              ⍝ Item number
        v.n←⍵↑0 1           ⍝ Initialize
        v.a←⊂v              ⍝ Each knows all
        v.b←(1+⍳⍵)⍴¨⊂v      ⍝ Each knows self and previous?
        v.f 0               ⍝ Compute
    }

And finally: "That joke about the Fibonacci sequence was worse than the last two
jokes put together" - JD

Lucas numbers
-------------
Initialising the recursion with 2 1, instead of 0 1, returns the Lucas sequence:

    2 1∘fibonacci¨ 0 to 20          ⍝ François Lucas 1842-1891.
2 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 5778 9349 15127

http://en.wikipedia.org/wiki/Lucas_number

Fibonacci-based number system
-----------------------------
The Fibonacci sequence may be used as the base of a number system:

    fibcode←{               ⍝ fibonacci-coding of number ⍵.

        pair←{              ⍝ fib-pair
            n←+/⍵           ⍝ next term.
            ⍺<n:⍵           ⍝ term large enough: finished.
            ⍺ ∇ 1↓⍵,n       ⍝ next pair
        }                   ⍝ :: i j ← n ∇ i j

        vec←{               ⍝ ⍺ is accumulator.
            n(i j)←⍵        ⍝ remaining number and current fib pair.
            i=0:⍺,1         ⍝ exhausted radix list: accumulator, sentinel.
            f←(j-i),i       ⍝ next fib pair.
            t←n≥j           ⍝ next term and
            r←n-t×j         ⍝   remainder.
            (t,⍺)∇ r f      ⍝ accumulated fib-coding.
        }                   ⍝ :: [b] ← [b] ∇ n(i j)

        ⍬ vec ⍵,⊂⍵ pair 0 1 ⍝ fi
    }

    ↑⍕∘fibcode¨0 to 10      ⍝ fibonacci coding of 0..10
1
1 1
0 1 1
0 0 1 1
1 0 1 1
0 0 0 1 1
1 0 0 1 1
0 1 0 1 1
0 0 0 0 1 1
1 0 0 0 1 1
0 1 0 0 1 1

See: http://en.wikipedia.org/wiki/Fibonacci_coding

Example:

      fibonacci¨⍳10                 ⍝ ⎕io=1: F1 .. F10
1 1 2 3 5 8 13 21 34 55

      fibonacci¨ 0 to 9             ⍝ first 10 Fibonacci numbers: F0 ..F9.
0 1 1 2 3 5 8 13 21 34

⍝ compare monitor of tail-recursive version:

      fibonacci mdf 20
 0 fibonacci←{     ⍝ Tail-recursive Fibonacci.
21     ⍺←0 1
21     ⍵=0:⍬⍴⍺
20     (1↓⍺,+/⍺)∇ ⍵-1
 0 }

⍝ ... with monitor of stack-recursive version:

      fib mdf 20
    0 fib←{
21891     ⍵∊0 1:⍵
10945     +/∇¨⍵-1 2
    0 }

See also: factorial mdf pow to cfract tacit nats
See also: phinary ratrep ratsum

Back to: contents

Back to: Workspaces