## My first function.

Learning APL or new to Dyalog? Ask "silly" questions here, without fear...

### My first function.

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.
hbarkhof

Posts: 44
Joined: Mon Apr 09, 2018 8:37 am

### Re: My first function.

`      {⍵,+/¯2↑⍵}⍣16⊢11 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` Phil Last

Posts: 557
Joined: Thu Jun 18, 2009 6:29 pm

### Re: My first function.

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 ? :-)
hbarkhof

Posts: 44
Joined: Mon Apr 09, 2018 8:37 am

### Re: My first function.

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 161 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 ! AndyS|Dyalog

Posts: 235
Joined: Tue May 12, 2009 6:06 pm

### Re: My first function.

Thanks Andy. Really appreciate.
hbarkhof

Posts: 44
Joined: Mon Apr 09, 2018 8:37 am

### Re: My first function.

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 Fiona|Dyalog

Posts: 59
Joined: Mon Apr 22, 2013 12:59 pm

### Re: My first function.

Thank you Fional ! Indeed a very usefull workspace !
hbarkhof

Posts: 44
Joined: Mon Apr 09, 2018 8:37 am

### Re: My first function.

The fastest Fibonacci function for small ⍵ is:

`      fib←{⌊0.5+r÷⍨(2÷⍨1+r)*⍵ ⊣ r←5*0.5}      fib¨ ⍳300 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)¨ ⍳301 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*5378.0145      fib 788.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 121 34       (M +.× M +.× M +.× M +.× M +.× M +.× M +.× M) +.× 0 121 34      (+.×⍨⍣3 ⊢M) +.× 0 121 34`

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

Posts: 215
Joined: Thu Jul 28, 2011 10:53 am