///////////////////////////////////////////////////////////////////////////////////////// // // // 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