For lulz, I clocked a dumb loop version.

    (defun fib (n)
        (loop repeat n
              for a = 1 then b
              for b = 1 then c
              for c = (+ a b)
              finally (return a)))

Edit: I confess the speed of the loop got me curious and.... javascript has numeric overflow. That would be a hell of a surprise if you weren't expecting it.

Edit2: (I realize overflow isn't the right term, but it is amusing that I can calc the 10000th fib in elisp... not so much in javascript. And yes, even elisp falls over sooner than sbcl does.)

OFC I would rewrite that as a iterative form (and any Schemer here could :D), but here we are testing performance :D.

I suppose there is a bit of something in there about using the right algorithm. But I can understand picking one that will take time for comparing speed. I'm not sure either is really representative of work you expect an editor to do, though. Curse of benchmarks.

Intuition: if you were to expand and flatten the recursive calls, you'd end up with something like

(+ 1 0 1 1 0 1 1 0 ... 1 0)

with exactly (fib n) 1s (base case (fib 1)), and no more than (fib n) 0s (base case (fib 0)).

Simple example:

     (fib 3)
     = (+ (fib 2) (fib 1))
     = (+ (+ (fib 1) (fib 0)) 1)
     = (+ (+ 1 0) 1)
     = (+ 1 0 1)

  With scm, using (trace proc):
 
 scm -f fib.scm
 
 call fib 9
    call fib 8
      call fib 7
        call fib 6
          call fib 5
          retn fib 5
          call fib 4
          retn fib 3
        retn fib 8
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
      retn fib 13
      call fib 6
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
      retn fib 8
    retn fib 21
    call fib 7
      call fib 6
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
      retn fib 8
      call fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
      retn fib 5
    retn fib 13
  retn fib 34
  call fib 8
    call fib 7
      call fib 6
        call fib 5
          call fib 4
          retn fib 3
          call fib 3
          retn fib 2
        retn fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
      retn fib 8
      call fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
      retn fib 5
    retn fib 13
    call fib 6
      call fib 5
        call fib 4
          call fib 3
          retn fib 2
          call fib 2
          retn fib 1
        retn fib 3
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
      retn fib 5
      call fib 4
        call fib 3
          call fib 2
          retn fib 1
          call fib 1
          retn fib 1
        retn fib 2
        call fib 2
          call fib 1
          retn fib 1
          call fib 0
          retn fib 0
        retn fib 1
      retn fib 3
    retn fib 8
  retn fib 21
  55
 
 scm -f fib-iter.scm
 
 call fib-iter 1 0 10
    call fib-iter 1 1 9
      call fib-iter 2 1 8
        call fib-iter 3 2 7
          call fib-iter 5 3 6
          retn fib-iter 55
        retn fib-iter 55
      retn fib-iter 55
    retn fib-iter 55
  retn fib-iter 55
  55

That is, knowing all of these facts, it is still impressive how fast you can get (fib 1000000) using iteration and bignums.

Which is still not fast -- on my laptop, Python takes about 9s for fib(1000000). But compared to an exponentially-growing function, that's a blink of an eye.

Granted, this is also true of fixednum in common lisp. At least "biting you" with that should only be performance. (I can't think of many other ways for that one to get you.)

Edit: I should further ack that "getting around" it is as simple as adding "n" to one of the constants. So, it is nicely done.

I wonder if there’s some room for improvement since using GMP is pretty standard for most languages.

Edit: forgot to link to a BigInt comparison in major language implementations http://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint-...

> (time (fibonacci 40)) (time (fibonacci 40)) no collections 1.364130664s elapsed cpu time 1.364456065s elapsed real time 0 bytes allocated 102334155

    $ csc -optimize-level 5 fib.scm 
    $ time ./fib

    real 0m5.506s
    user 0m5.489s
    sys  0m0.010s

    $ csc -optimize-level 5 -stack-size 4m fib.scm 
    $ time ./fib

    real 0m5.295s
    user 0m5.277s
    sys  0m0.011s

I stopped writing Chicken scheme code a few years ago; it was fun due to the ease of interoperating with C, but I found Chibi a better fit for that niche eventually.