SBCL中数值计算代码大量cons内存的原因及优化问询

在SBCL（2.3.5）环境下运行以下代码时，内存cons量远超预期：

(defun number-of-digits (num)
  (do ((n 1 (1+ n))
       (num (floor num 10) (floor num 10)))
      ((zerop num) n)))

(defun p25 ()
  (do ((a 0 (+ a b))
       (b 1 a)
       (n 0 (1+ n)))
      ((>= (number-of-digits a) 1000) n)))

执行(time (p25))后得到如下结果：

(time (p25))
Evaluation took:
  0.890 seconds of real time
  0.888141 seconds of total run time (0.878463 user, 0.009678 system)
  [ Run times consist of 0.004 seconds GC time, and 0.885 seconds non-GC time. ]
  99.78% CPU
  1,864,981,440 processor cycles
  368,895,776 bytes consed
  
4782

代码未进行任何列表创建操作，现提出两个问题：

1. 如此大量的cons内存来自何处？原因是什么？
2. 如何消除或大幅减少此类内存cons消耗？

1. 内存cons的来源与原因 #

核心原因是大整数（bignum）运算的内存分配：

• 迭代生成斐波那契数时，a和b会快速增长为千位级超大整数。SBCL中，整数超过机器字长限制后会以bignum（多精度整数）形式存储，每次执行(+ a b)生成新斐波那契数时，都需要分配新内存块存储大整数的数位数据。
• 辅助函数number-of-digits中，每次(floor num 10)操作都会生成新的bignum（原数为bignum时，除以10的结果仍为bignum），这会额外产生大量内存分配。
• 虽然没有显式创建列表，但bignum是不可变对象，每次运算都会生成新实例，这些实例的分配就是cons内存的主要来源。

2. 减少cons消耗的优化方案 #

方案一：用数学公式直接计算结果（零cons） #

斐波那契数的位数可通过对数公式估算：第n个斐波那契数F(n)的位数为floor(log₁₀(F(n))) + 1。结合近似公式F(n) ≈ φⁿ / √5（φ为黄金分割比，约1.61803），可推导出：
log₁₀(F(n)) ≈ n*log₁₀(φ) - log₁₀(√5)

我们需要找到最小的n，使得位数≥1000，即log₁₀(F(n)) ≥ 999，代入公式直接解出n：

(defun p25 ()
  (let* ((phi (/ (1+ (sqrt 5)) 2))
         (log10-phi (log phi 10))
         (log10-sqrt5 (log (sqrt 5) 10)))
    (ceiling (/ (- 999 log10-sqrt5) log10-phi))))

这段代码完全不需要生成大整数，运行时cons量几乎为0，计算效率极高。

方案二：优化位数计算逻辑 #

如果必须通过迭代生成斐波那契数实现，可以优化number-of-digits函数，避免反复创建bignum：

• 直接用对数计算位数，替代循环除以10的操作，减少bignum实例生成。

优化后的代码：

(defun number-of-digits (num)
  (cond
    ((zerop num) 1)
    ((typep num 'fixnum) (length (write-to-string num)))
    (t (1+ (floor (log num 10))))))

(defun p25 ()
  (do ((a 0 (+ a b))
       (b 1 a)
       (n 0 (1+ n)))
      ((>= (number-of-digits a) 1000) n)))

该版本避免了大量不必要的bignum分配，能大幅降低cons量。

方案三：减少位数检查频率 #

迭代斐波那契数时，无需每次循环都检查位数。可以每10次或几十次迭代检查一次，减少不必要的计算，进一步降低内存消耗。

内容的提问来源于stack exchange，提问作者xiepan