My first function.

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

My first function.

Postby hbarkhof on 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.
hbarkhof
 
Posts: 44
Joined: Mon Apr 09, 2018 8:37 am

Re: My first function.

Postby Phil Last on 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
User avatar
Phil Last
 
Posts: 624
Joined: Thu Jun 18, 2009 6:29 pm
Location: Wessex

Re: My first function.

Postby hbarkhof on 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 ? :-)
hbarkhof
 
Posts: 44
Joined: Mon Apr 09, 2018 8:37 am

Re: My first function.

Postby AndyS|Dyalog on 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 !
User avatar
AndyS|Dyalog
 
Posts: 257
Joined: Tue May 12, 2009 6:06 pm

Re: My first function.

Postby hbarkhof on Thu May 03, 2018 10:28 am

Thanks Andy. Really appreciate.
hbarkhof
 
Posts: 44
Joined: Mon Apr 09, 2018 8:37 am

Re: My first function.

Postby Fiona|Dyalog on 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
User avatar
Fiona|Dyalog
 
Posts: 68
Joined: Mon Apr 22, 2013 12:59 pm

Re: My first function.

Postby hbarkhof on Fri May 04, 2018 9:33 am

Thank you Fional ! Indeed a very usefull workspace !
hbarkhof
 
Posts: 44
Joined: Mon Apr 09, 2018 8:37 am

Re: My first function.

Postby Roger|Dyalog on 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).
Roger|Dyalog
 
Posts: 238
Joined: Thu Jul 28, 2011 10:53 am


Return to New to Dyalog?

Who is online

Users browsing this forum: No registered users and 1 guest