Dyalog Forums

Posted: **Wed May 02, 2018 10:26 am**

Hi. This is my first written function. It displays the first 16 figures of the Fibonacci series.
=================================
z←fibonacci;vec;tel;a;b
vec←⍳16
tel←1
a←1
b←2
vec[tel]←a
tel←tel+1
vec[tel]←b
:While (a+b)<1000
tel←tel+1
a←a+b
b←a+b
vec[tel]←a
tel←tel+1
vec[tel]←b
:EndWhile
z←vec
=====================================
I think and guess there must be a much smarter way to do the same ?

Henk.

Posted: **Wed May 02, 2018 10:01 pm**

      {⍵,+/¯2↑⍵}⍣16⊢1
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597
⍝ not necessarily the most efficient but hard to condense.
⍝ ⍣ is the power operator that causes its function left operand to be run
⍝ as many times as the value of its scalar integer right operand starting
⍝ with its right argument with subsequent calls using the previous result

Posted: **Thu May 03, 2018 6:31 am**

WOW ! That is not smarter , it is genius ! I expected it could be something with less rows but a one-liner!
Thanks a lot Phil. I think you have more than 1 month experience ? :-)

Posted: **Thu May 03, 2018 10:16 am**

It'll come over time ! The most important thing is that your function works - you can always revisit code you've already written and improve it; I've spent a working life time doing that and there's still a long way to go.

A half-way house solution might be something like the following:

Code: Select all

 ∇r←fib n
 r←1 1
 :While n≥≢r
     r,←+/¯2↑r
 :EndWhile
 ∇

          fib 16
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597

The dfns workspace contains a recursive version of a fibonacci function which may be of interest. Indeed, the dfns workspace is full of functions that will probably be of use to you !

Posted: **Thu May 03, 2018 10:28 am**

Thanks Andy. Really appreciate.

Posted: **Fri May 04, 2018 8:07 am**

In case you've not yet come across the dfns workspace that Andy refers to, it's at https://dfns.dyalog.com and includes hundreds of really useful tips and examples.

The Fibonacci entry is at https://dfns.dyalog.com/n_fibonacci.htm

Posted: **Fri May 04, 2018 9:33 am**

Thank you Fional ! Indeed a very usefull workspace !

Posted: **Tue May 08, 2018 9:35 am**

The fastest Fibonacci function for small ⍵ is:

      fib←{⌊0.5+r÷⍨(2÷⍨1+r)*⍵ ⊣ r←5*0.5}

      fib¨ ⍳30
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 
      17711 28657 46368 75025 121393 196418 317811 514229

It is based on Binet's formula,

      fibBinet←{phi←2÷⍨1+5*0.5 ⋄ psi←2÷⍨1-5*0.5 ⋄ (5*0.5)÷⍨-/(phi,psi)*⍵}

      (fib = fibBinet)¨ ⍳30
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

but exploits the fact that (psi*⍵)÷5*0.5 is less than 1, so that rounding (phi*⍵)÷5*0.5 suffices. The fib definition makes clear that the Fibonacci numbers grow exponentially with a base of 2÷⍨1+r ←→ phi ←→ 1.61803 AKA the golden ratio.

How small is "for small ⍵"? 64-bit floats run out of precision at 2*53, so ⍵ must be less than

      r←5*0.5
      (2÷⍨1+r) ⍟ r × 2*53
78.0145

      fib 78
8.94439E15
      0 ⍕ fib3a 78
 8944394323791488

For large ⍵, a fast method derives from the matrix equation

      (f[n],f[n-1]+f[n]) = M +.× f[n-1],f[n]
      (f[n],f[n+1])      = M +.× f[n-1],f[n]
      f[n+1]             = ⊃⌽ M +.× f[n-1],f[n]

where M ← 2 2⍴0 1 1 1. Since matrix multiplication is associative, you can replace repeated multiplication of M by a vector, by repeated squaring of M and then multiply the result of that by a vector.

      M +.× M +.× M +.× M +.× M +.× M +.× M +.× M +.× 0 1
21 34 
      (M +.× M +.× M +.× M +.× M +.× M +.× M +.× M) +.× 0 1
21 34
      (+.×⍨⍣3 ⊢M) +.× 0 1
21 34

You do need to do the +.× using extended precision arithmetic (not available as APL primitives).

Dyalog Forums

My first function.

My first function.

Re: My first function.

Re: My first function.

Re: My first function.

Re: My first function.

Re: My first function.

Re: My first function.

Re: My first function.