/////////////////////////////////////////////////////////////////////////////////////////
//
//
//                          The Fibonacci Series 
//
// Fibonacci (Leonardo of Pisa) introduced a problem for his readers: 
// a pair of rabbits are put in a field and, if rabbits take a month to become mature and 
// then produce a new pair every month after that, how many pairs will there be in twelve 
// months time? 
// The assumption is during this time no rabbit will die. 
// The answer involves the series of numbers: 
//
// 1, 1, 2, 3, 5, 8, 13, 21, ...
// 
// In general "n"-th number can be expressed as
//
//      F(n) = F(n-1) + F(n-2), with F(1) = 1, F(2) = 1 
//
// The code below can calculate Fibonacci numbers using a rather simple
// algorithm. The code should be compiled with garbage collection enabled.
// ("Project"->"Settings"->"Compiler"->"Enable Garbage Collection").
//
// Using a modest PC with an AMP XP 1600++ CPU these are the execution
// times you may expect:
// 
//      
//      Query                   Time
//      --------------------------------
//      Fibonacci(100000)     00:00:02 
//      Fibonacci(500000)     00:00:22 
//      Fibonacci(1000000)    00:01:19 
//      Fibonacci(1500000)    00:04:57 
//      Fibonacci(1700000)    00:09:42
//      Fibonacci(2000000)    00:16:26
//      Fibonacci(2500000)    00:31:38
//      Fibonacci(3000000)    00:51:43
//      Fibonacci(3500000)    01:13:33
//      Fibonacci(4000000)    01:53:47
//      Fibonacci(4500000)    02:09:11
//      Fibonacci(5000000)    02:59:08
//      Fibonacci(6000000)    04:02:27
//      Fibonacci(8000000)    07:19:04
//      Fibonacci(10000000)   12:11:05
//
// Beware the execution time includes the printout (decimal) of the number. 
//
// Since the algorithm for calculating F(n) needs to calculate F(n-1) first,
// we can optionally printout all F(m) for m <= n. This is accomplished by
// running the query
//
//         FibonacciAll(n)
//
// For example, the query FibonnaciAll(15) will produce output
//
// F(1) = 1
// F(2) = 1
// F(3) = 2
// F(4) = 3
// F(5) = 5
// F(6) = 8
// F(7) = 13
// F(8) = 21
// F(9) = 34
// F(10) = 55
// F(11) = 89
// F(12) = 144
// F(13) = 233
// F(14) = 377
// F(15) = 610
//
//
/////////////////////////////////////////////////////////////////////////////////////////

// Calculate and print F(n)

proc Fibonacci(n:<L) iff
    Print('F(',n,') = \n') &
    m:.L & m := 0 & k:.L & k := 1 &
    Fib2(n,m,k) & Print (m)

local proc Fib2(n:<L,a:.L,b:.L) iff
    if  n > 0 then 
        c:.L & c := a + b &
        a := b & b:= c &
        Fib2(n-1,a,b)
    end

// Slight modification of the above code:
// Calculate F(n) and print all F(m) for m <= n

proc FibonacciAll(n:<L) iff
    m:.L & m := 0 & k:.L & k := 1 &
    Fib2All(1,n,m,k) 

local proc Fib2All(i:<L,n:<L,a:.L,b:.L) iff
    if i <= n then 
        Print('\nF(',i,') = ',b) &
        c:.L & c := a + b &
        a := b & b:= c &
        Fib2All(i+1,n,a,b)
    end

This page was created by F1toHTML