The Fibonacci Numbers

[jdan]

Fibonacci Numbers

[How to read this blog post]

NB. We start our sequence with the pair 0 1
0 1
NB. 0 1

NB. To shift our pair up one step, we'll start by grabbing the last of the two
{: 0 1
NB. 1

NB. The next item in our sequence will be the sum of the previous two
+/ 0 1
NB. 1

NB. So to get our next pair we'll concatenate these
({: 0 1) , (+/ 0 1)
NB. 1 1

NB. In J, forks allow us to rewrite (f x) g (h x) as (f g h) x
({: , +/) 0 1
NB. 1 1

NB. Let's feed this result back into our pair-generator
({: , +/) 1 1
NB. 1 2
({: , +/) 1 2
NB. 2 3
({: , +/) 2 3
NB. 3 5
({: , +/) 3 5
NB. 5 8

NB. We can also compose our function
({: , +/) ({: , +/) 0 1
NB. 1 2
({: , +/) ({: , +/) ({: , +/) 0 1
NB. 2 3
({: , +/) ({: , +/) ({: , +/) ({: , +/) 0 1
NB. 3 5

NB. The power verb can do this for us
(({: , +/)^:2) 0 1
NB. 1 2
(({: , +/)^:10) 0 1
NB. 55 89

NB. We can grab just the last item
{. (({: , +/)^:10) 0 1
NB. 55

NB. We can redefine this in explicit verb form
NB. 'y' refers to our argument
fib =: 3 : '{. (({: , +/)^:y) 0 1'
fib 0
NB. 0
fib 10
NB. 55
fib 50
NB. 12586269025

[jonahx]

You can stay tacit for the final definition as well:

f=. [: {. ({:,+/)@]^:[&0 1

Now f n gives you the nth fib number.

[dhbradshaw]

This is so cool! The power transition blew me away.