0 :0
This program calculates the nth fibonacci number
using algorithm 1A: binary recursion

compiled: N/A
executed: jconsole -jijx f1a.ijs n

note that jconsole -jijx f2c.ijs "n1 n2 n3 n4 ..." is also supported,
it will calculate a list of fibonacci numbers F(n1), F(n2), F(n3), F(n4)
)

NB. Naive binary recursion: F(n) = F(n-1) + F(n-2)
NB. (based on R.Hui's example from J Essays, which is much cooler
NB. than my old f =: 1:`( $:&<:&<: + $:&<: ) @. (1: < ] ) 
fib =: (-&2 +&$: <:) ^: (1&<)

NB. f handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
NB. implemented as fib(abs(n)) * pow(signum(n), n+1)
f =: fib&|**^>:

NB. take the last commandine argument, unbox, and convert to number
n =: _".>{:ARGV
NB. execute fib(n) and assemble the output string, report usage if any errors
main =: (":,'th Fibonacci number is '"_,":&f) :: ('Usage: jconsole f1a.ijs <n>'"_)
NB. entry point
echo main n
exit''

0 :0
This program calculates the nth fibonacci number
using algorithm 1B: cached binary recursion

compiled: N/A
executed: jconsole -jijx f1b.ijs n
)

NB. Naive binary recursion: F(n) = F(n-1) + F(n-2)
NB. Identical to algorithm 1A, except for memoization
NB. (based on R.Hui's example from J Essays)
fib =: (-&2 +&$: <:) ^: (1&<) M.

NB. f handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
NB. implemented as fib(abs(n)) * pow(signum(n), n+1)
NB. The only difference from 1A is that the argument is converted to
NB. extended precision first 
f =: (fib&|**^>:)&x:

NB. take the last commandine argument, unbox, and convert to number
n =: _".>{:ARGV
NB. execute fib(n) and assemble the output string, report usage if any errors
main =: (":,'th Fibonacci number is '"_,":&f) :: ('Usage: jconsole f1b.ijs <n>'"_)
NB. entry point
echo main n
exit''

0 :0
This program calculates the nth fibonacci number
using algorithm 2A: CACHED LINEAR RECURSION / RANDOM-ACCESS CONTAINER.

compiled: N/A
executed: jconsole -jijx f2a.ijs n
)

NB. flist creates a list of n first Fibonacci numbers.
NB. I believe I based this on an example from J Dictionary, and I am sure
NB. +/&(_2${.) is not the best-looking way to sum the last two list elements.
flist =: 0 1x"_` ((], +/&(_2&{.))&$:&<:) @. (1&<)

NB. fib returns the first element of the list
fib=: {:&flist

NB. f handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
NB. implemented as fib(abs(n)) * pow(signum(n), n+1)
NB. it also converts its result to a high precision integer
f =: (fib&|**^>:)&x:

NB. take the last commandine argument, unbox, and convert to number
n =: _".>{:ARGV
NB. execute fib(n) and assemble the output string, report usage if any errors
main =: (":,'th Fibonacci number is '"_,":&f) :: ('Usage: jconsole f2a.ijs <n>'"_)
NB. entry point
echo main n
exit''

0 :0
This program calculates the nth fibonacci number
using algorithm 2B: linear recursion with accumulator

compiled: N/A
executed: jconsole -jijx f2b.ijs n

note that jconsole -jijx f2b.ijs "n1 n2 n3 n4 ..." is also supported,
it will calculate a list of fibonacci numbers F(n1), F(n2), F(n3), F(n4)
)

NB. Simple recursion: F(n) = F(n-1) + F(n-2)
NB. based on J Essays by R.Hui, which was much better than my first
NB. try of 0x 1"0`((+/\@|.)@$:@<:)@.* -- it wasn't even tail-recursive!
NB. So, when fib(x) is called monadically, call itself with "1 0"
NB. as the right argument and x as the left argument.
NB. When called dyadically, call itself with
NB. (x-1) as the left argument and (x2 x1+x2) as the right argument,
NB. stop and return the last of the two numbers on the right
NB. when the left argument is zero.
fib=: {:@($:&1x 0) : ((<:@[ $: +/\@|.@])^:(*@[))

NB. f handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
NB. implemented as fib(abs(n)) * pow(signum(n), n+1)
NB. it also converts its result to a high precision integer
f =: (fib&|**^>:)&x:

NB. take the last commandine argument, unbox, and convert to number
n =: _".>{:ARGV
NB. execute fib(n) and assemble the output string, report usage if any errors
main =: (":,'th Fibonacci number is '"_,":&f) :: ('Usage: jconsole f2b.ijs <n>'"_)
NB. entry point
echo main n
exit''

0 :0
This program calculates the nth fibonacci number
using algorithm 2C: imperative loop with mutable variables

compiled: N/A
executed: jconsole -jijx f2c.ijs n

note that jconsole -jijx f2c.ijs "n1 n2 n3 n4 ..." is also supported,
it will calculate a list of fibonacci numbers F(n1), F(n2), F(n3), F(n4)
)

NB. Imperative loop: F(n) = F(n-1) + F(n-2)
NB. Start with "1 0", repeat n times the following:
NB. for the current (x y), swap to make (y x), then calculate (y, x+y).
NB. in the end, take the last of the two values.
fib =: {:&([+/\@|.@]^:[1x 0"0)

NB. f handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
NB. implemented as fib(abs(n)) * pow(signum(n), n+1)
NB. it also converts its argument to a high precision integer
f =: (fib&|**^>:)&x:

NB. take the last commandine argument, unbox, and convert to number
n =: _".>{:ARGV
NB. execute fib(n) and assemble the output string, report usage if any errors
main =: (":,'th Fibonacci number is '"_,":&f) :: ('Usage: jconsole f2c.ijs <n>'"_)
NB. entry point
echo main n
exit''

0 :0
This program calculates the nth fibonacci number
using algorithm 3A: matrix multiplication

compiled: N/A
executed: jconsole -jijx f3a.ijs n
)

NB. Matrix multiplication: 
NB.
NB.  |1 1| ^ (n-1)   |   Fn   F(n-1) |
NB.  |1 0|         = | F(n-1) F(n-2) |
NB.
NB. based on J Essays by R.Hui. Although I did realize that #: would be
NB. the way to implement power by squaring, I didn't figure out I.|.#:

NB. mm is matrix multiplication
mm =: +/ .*

NB. mp is a general function to raise an object x to an integer power y
NB. using the repeated squaring algorithm
NB. (it can use any named multiplication function in place of 'mm')
mp =: 4 : 'mm / ( mm ~^: (I.|.#: y ) x)'

NB. fib n raises the 2x2 matrix (1,1)(1,0) to the n-1 power and returns the top left value 
fib =: {.&,&((2 2$1x 1 1 0)&mp&<:)

NB. f handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
NB. implemented as fib(abs(n)) * pow(signum(n), n+1)
NB. it also converts its result to a high precision integer
f =: (fib&|**^>:)&x:

NB. take the last commandine argument, unbox, and convert to number
n =: _".>{:ARGV
NB. execute fib(n) and assemble the output string, report usage if any errors
main =: (":,'th Fibonacci number is '"_,":&f) :: ('Usage: jconsole f3a.ijs <n>'"_)
NB. entry point
echo main n
exit''

0 :0
This program calculates the nth fibonacci number
using algorithm 3B: fast recursion

compiled: N/A
executed: jconsole -jijx f3b.ijs n
)

NB. Uses the identity F(2n) = F(n+1)^2 - F(n-1)^2
NB. and F(2n+1) = F(n+1)^2 + F(n)^2
NB. taken from J Essays by R.Hui.
NB. Initially I made my own, tacit, version, but it was extremely unwieldy.
NB. I may revisit it later, but for now, enjoy explicit flow control.

fib=: 3 : 0
    if. 2 >: y do. 1<.y else.
        if. y = 2*n=.<.y%2
        do.   (n+1) -&*:&fib n-1
        else. (n+1) +&*:&fib n end.
    end.
)

NB. f handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
NB. implemented as fib(abs(n)) * pow(signum(n), n+1)
NB. it also converts its result to a high precision integer
f =: (fib&|**^>:)&x:

NB. take the last commandine argument, unbox, and convert to number
n =: _".>{:ARGV
NB. execute fib(n) and assemble the output string, report usage if any errors
main =: (":,'th Fibonacci number is '"_,":&f) :: ('Usage: jconsole f3b.ijs >n<'"_)
NB. entry point
echo main n
exit''

0 :0
This program calculates the nth fibonacci number
using algorithm 3C: BINET'S FORMULA

compiled: N/A
executed: jconsole -jijx f3c.ijs n
)

NB. This function uses Binet's Formula to calculate n'th Fibonacci number:
NB. F(n) = ((1+sqrt(5)^n - (1-sqrt(5)^n)/(sqrt(5)*2^n)
NB. Although J does not have arbitrary precision floating point numbers,
NB. it makes it possible to calculate this precisely by defining
NB. multiplication in ring extensions of Z and Q.
NB. This solution is, of course, taken from J Essays
times=: (1 5&(+/ .*)@:* , (+/ .* |.)) " 1
pow  =: 4 : 'times/ 1 0 , times~^:(I.|.#:y) x' " 1 0
fib  =: {:@(1 1x&pow) % 2x&^@<:

NB. f handles the negative arguments: F(-n) = F(n)*(-1)^(n+1)
NB. implemented as fib(abs(n)) * pow(signum(n), n+1)
NB. it also converts its result to a high precision integer
f =: (fib&|**^>:)&x:

NB. take the last commandine argument, unbox, and convert to number
n =: _".>{:ARGV
NB. execute fib(n) and assemble the output string, report usage if any errors
main =: (":,'th Fibonacci number is '"_,":&f) :: ('Usage: jconsole f3c.ijs <n>'"_)
NB. entry point
echo main n
exit''