lisp - Euler #2 尝试后出现 Bignum 溢出错误

Question

我试图解决 Euler Problem 2具有以下尾递归函数:

(defun fib (num)
  (labels ((fib-helper (num a b)
         (cond ((or (zerop num)
                    (eql num 1))
                a)
               (t (fib-helper (decf num)
                              (+ a b)
                              a)))))
    (fib-helper num 1 1)))


(defun sum-even-fib (max)
  (labels ((helper (sum num)
         (cond ((oddp num) (helper sum (decf num)))
               ((zerop num) sum)
               (t (helper (+ sum (fib num))
                          (decf num))))))
    (helper 0 max)))

现在，当我尝试使用函数打印结果时

(defun print-fib-sum (max dir file)
  (with-open-file
      (fib-sum-str
       (make-pathname
         :name file
         :directory dir)
        :direction :output)
    (format fib-sum-str "~A~%" (sum-even-fib max))))

当 max 值为 4000000 时，出现错误

     ("bignum overflow" "[Condition of type SYSTEM::SIMPLE-ARITHMETIC-ERROR]" nil)

来自 *slime-events*。还有其他方法可以处理数字并打印到文件吗？

Answer 1

首先是几个小问题:

1. 使用 time而不是 top。

2. Common Lisp 标准不需要尾递归优化。虽然许多实现都这样做，但并非所有实现都优化了所有情况(例如 labels )。

3. 您的算法是 max 的二次方算法，因为它为所有索引单独计算第 n 个斐波那契数。你应该让它变成线性的。

4. 您正在计算偶数索引数的总和，而不是 even-valued numbers .

现在，您看到的算术错误:第 4,000,000 个斐波那契数非常大 - 大约 1.6^4M ~ 10^835951。它的length大约是 2,776,968。

你确定你的 lisp 可以表示这么大的 bignums 吗？