My first function.
8 posts
• Page 1 of 1
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.
=================================
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⊢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

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 oneliner!
Thanks a lot Phil. I think you have more than 1 month experience ? :)
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 halfway house solution might be something like the following:
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 !
A halfway 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 !

AndySDyalog  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
The Fibonacci entry is at https://dfns.dyalog.com/n_fibonacci.htm

FionaDyalog  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:
It is based on Binet's formula,
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 ⍵"? 64bit floats run out of precision at 2*53, so ⍵ must be less than
For large ⍵, a fast method derives from the matrix equation
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.
You do need to do the +.× using extended precision arithmetic (not available as APL primitives).
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÷⍨15*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 ⍵"? 64bit 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[n1]+f[n]) = M +.× f[n1],f[n]
(f[n],f[n+1]) = M +.× f[n1],f[n]
f[n+1] = ⊃⌽ M +.× f[n1],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).
 RogerDyalog
 Posts: 215
 Joined: Thu Jul 28, 2011 10:53 am
8 posts
• Page 1 of 1
Who is online
Users browsing this forum: No registered users and 1 guest
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group