[Axiom-mail] function cache and fibonacci

[terence cadd]

--- getting wildly different performance from these definitions
---
--- compiler likes fib2

)clear all

fib(n) ==
  n < 1 => error("fib : n less than 1")
  n = 1 => 1
  n = 2 => 2
  n > 2 => fib(n-1) + fib(n-2)

fib2(n : Integer) : Integer ==
  if n < 1 then error("fib2 : n less than 1")
  else if n = 1 then 1
  else if n = 2 then 2
  else fib2(n-1) + fib2(n-2)

fib3(n : PositiveInteger) : PositiveInteger ==
  if n < 1 then error("fib3 : n less than 1")
  else if n = 1 then 1
  else if n = 2 then 2
  else fib3(n-1) + fib3(n-2)

)set fun cache all fib fib2 fib3

---
---
---
---
---    In general, interpreter functions will cache all values.
--- (4) -> fib(10)
---    There are 15 exposed and 5 unexposed library operations named +
---       having 2 argument(s) but none was determined to be applicable.
---       Use HyperDoc Browse, or issue
---                                 )display op +
---       to learn more about the available operations. Perhaps
---       package-calling the operation or using coercions on the arguments
---       will allow you to apply the operation.
---    Cannot find a definition or applicable library operation named +
---       with argument type(s)
---                                     Void
---                                     Void

---       Perhaps you should use "@" to indicate the required return type,
---       or "$" to specify which version of the function you need.
---    AXIOM will attempt to step through and interpret the code.

---    (4)  89
---                                                         Type:
PositiveInteger
---                        Time: 0.05(A) + 0.01(E) + 0.02(M) + 0.01(K)
= 0.09 sec
--- (5) -> fib(20)

---    (5)  10946
---                                                         Type:
PositiveInteger
--- Time: 2.35(A) + 0.08(C) + 0.24(E) + 0.38(G) + 0.05(H) + 0.12(I) +
0.83(M) + 5.21(K) = 9.26 sec
--- (6) -> fib2(20)
---    Compiling function fib2 with type Integer -> Integer
---    fib2 will cache all previously computed values.

---    (6)  10946
---                                                         Type:
PositiveInteger
---                                                      Time: 0.01(T)
= 0.01 sec
--- (7) -> fib3(20)
---    There are no library operations named fib3
---       Use HyperDoc Browse or issue
---                                 )what op fib3
---       to learn if there is any operation containing " fib3 " in its
---       name.
---    Cannot find a definition or applicable library operation named fib3
---       with argument type(s)
---                                    Integer

---       Perhaps you should use "@" to indicate the required return type,
---       or "$" to specify which version of the function you need.
---    AXIOM will attempt to step through and interpret the code.
---    Compiling function fib3 with type PositiveInteger -> PositiveInteger

---    fib3 will cache all previously computed values.

---    (7)  10946
---                                                         Type:
PositiveInteger
--- Time: 2.32(A) + 0.14(C) + 0.16(E) + 0.53(G) + 0.05(H) + 0.67(M) +
5.75(K) + 0.02(R) = 9.60 sec
--- (8) ->

--- GCL (GNU Common Lisp)  2.6.7 CLtL1    Nov  5 2010 16:04:47
--- Source License: LGPL(gcl,gmp), GPL(unexec,bfd,xgcl)
--- Binary License:  GPL due to GPL'ed components: (XGCL READLINE UNEXEC)
--- Modifications of this banner must retain notice of a compatible license
--- Dedicated to the memory of W. Schelter

--- Use (help) to get some basic information on how to use GCL.
--- Temporary directory for compiler files set to /tmp/
---                         AXIOM Computer Algebra System
---                        Version: Axiom (September 2010)
---                Timestamp: Sunday November 7, 2010 at 00:00:45
--- ----------------------------------------------------------------------------