performance - 为什么这种简化会使我的功能变慢？

以下函数通过尾部递归和平方计算斐波那契级数：

(defun fib1 (n &optional (a 1) (b 0) (p 0) (q 1))
  (cond ((zerop n) b)
    ((evenp n)
     (fib1 (/ n 2)
          a
          b
          (+ (* p p) (* q q))
          (+ (* q q) (* 2 p q))))
    (t
     (fib1 (1- n)
          (+ (* b q) (* a (+ p q)))
          (+ (* b p) (* a q))
          p
          q))))

基本上，它把每一个奇数输入减少到偶数输入，把每一个偶数输入减少一半。例如，

F(21)
    = F(21 1 0 0 1)
    = F(20 1 1 0 1)
    = F(10 1 1 1 1)
    = F(5 1 1 2 3)
    = F(4 8 5 2 3)
    = F(2 8 5 13 21)
    = F(1 8 5 610 987)
    = F(0 17711 10946 610 987)
    = 10946

当我看到这个时，我想最好把偶数和奇数结合起来（因为奇数减一等于偶数），所以我写道

(defun fib2 (n &optional (a 1) (b 0) (p 0) (q 1))
    (if (zerop n) b
     (fib2 (ash n -1)
          (if (evenp n) a (+ (* b q) (* a (+ p q))))
          (if (evenp n) b (+ (* b p) (* a q)))
          (+ (* p p) (* q q))
          (+ (* q q) (* 2 p q)))))

希望这能加快速度，就像上面的方程

F(21)
    = F(21 1 0 0 1)
    = F(10 1 1 1 1)
    = F(5 1 1 2 3)
    = F(2 8 5 13 21)
    = F(1 8 5 610 987)
    = F(0 17711 10946 1346269 2178309)
    = 10946

但是，当我通过下面的代码检查fib（1000000）所需的时间时（忽略progn，我只是不想让屏幕上填满数字），结果会慢得多（在clozure cl、clisp和lispworks中要多花50%的时间）。

(time (progn (fib1 1000000)()))
(time (progn (fib2 1000000)()))

我只能看到fib2可能比fib1做得更均匀，那为什么它要慢得多呢？
编辑：我想N.M.搞定了，我编辑了第二组公式。例如，在上述F（21）的例子中，fib2实际上计算p和q中的F（31）和F（32），这是从未使用过的所以在f（1000000）中，fib2计算f（1048575）和f（1048576）。
懒得评价石头，这是一个很好的观点。我猜在普通的lisp中，只有“and”和“or”这样的宏被懒散地评估？
以下修改的fib2（定义为n>0）实际上运行得更快：

(defun fib2 (n &optional (a 1) (b 0) (p 0) (q 1))
    (if (= n 1) (+ (* b p) (* a q))
     (fib2 (ash n -1)
          (if (evenp n) a (+ (* b q) (* a (+ p q))))
          (if (evenp n) b (+ (* b p) (* a q)))
          (+ (* p p) (* q q))
          (+ (* q q) (* 2 p q)))))

最佳答案

插入中间结果的打印在计算结束时注意p和q。
您会注意到，在最后一步，fib2会为p和q计算更大的值这两个值解释了所有性能差异。
具有讽刺意味的是，这些昂贵的价值观没有得到使用。这就是为什么haskell没有遇到这个性能问题：未使用的值实际上不是计算出来的。