I had some fun with this a while back: https://gist.github.com/cellularmitosis/aa3001c8d5a961f7b382f6576978b644

What is purpose of this? Optimize a function which uses a terrible algorithm? Why not use a good algorithm? In Racket for instance

(define (memoize/1 f)
  (define h (make-hasheqv))
  (λ (a)
    (hash-ref! h a (thunk (f a)))))

(define fib
  (memoize/1
   (λ (x)
     (if (< x 2) 
         1
         (+ (fib (- x 2)) 
            (fib (- x 1)))))))

And now

> (time (fib 39))
cpu time: 0 real time: 0 gc time: 0
102334155
> (time (fib 50000))
cpu time: 77 real time: 88 gc time: 29
174387413787277868303885543...

(10,000 digit number, results are from cold Racket so memo table was empty initially.)

Is entertaining then to try to compute say (log (fib 500000) 10). Bignums tend to get pretty slow then.

You didn’t say on which machine you did your measurements… Here’s Gambit on a 5 year old intel based machine achieving 0.148 seconds:

$ ./configure --enable-single-host --enable-march=native CC=gcc-9 ; make -j8 ; sudo make install
...
$ gsc -exe fib.scm
$ ./fib
(time (fib 39))
    0.147854 secs real time
    0.147816 secs cpu time (0.147732 user, 0.000084 system)
    no collections
    64 bytes allocated
    3 minor faults
    no major faults
63245986
$ sysctl -n machdep.cpu.brand_string
Intel(R) Core(TM) i7-8700B CPU @ 3.20GHz
$ cat fib.scm
(declare
  (standard-bindings)
  (fixnum)
  (not safe)
  (block)
  (not interrupts-enabled)
  (inlining-limit 1000)
)

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

(println (time (fib 39)))

Chez Scheme: 0.393200000s

At least with abcl you may want to consider using the builtin compiler for a considerable speedup, don’t know about the others:

C:\>abcl
CL-USER(1): (defun fib (x) (if (< x 2) 1 (+ (fib (- x 2)) (fib (- x 1)))))
FIB
CL-USER(2): (time (fib 39))
86.97 seconds real time
0 cons cells
102334155
CL-USER(3): (compile 'fib)
FIB
NIL
NIL
CL-USER(4): (time (fib 39))
8.958 seconds real time
0 cons cells
102334155
CL-USER(5):

Medley: 11.4 (compiled)

(running online https://online.interlisp.org )

Let’s see some Janet and Fennel times.

Next question: SBCL type annotations and optimization levels?

This type of post doesn’t make sense without source code, hardware used, OS, distro, compiler/interpreter/runtime/library versions, virtualization, etc.

How many times do you calculate Fibonacci in a normal program?

Thanks. Will have to look into switching our fibonacci-as-a-service over from ccl.

Without type declarations I have CCL computing (fib 39) in 0.365 seconds and (fib 39) in 0.743 seconds. This is because CCL inlines the fixnum case for generic addition, and SBCL does not.