CODEWITHSUNDEEP
lispstack-overflowtail-recursionbignum
category
category

Reputation: 2165

Bignum overflow error after Euler #2 attempt

I've attempted to solve Euler Problem 2 with the following tail recursive functions:

(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)))

Now, when I try to print the result using the function

(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))))

with a max value of 4000000, I get the error

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

from *slime-events*. Is there any other way to handle the number and print to the file?

Upvotes: 0

Views: 108

Answers (3)

Rainer Joswig
Rainer Joswig

Reputation: 139321

Since CL does not promise that it supports TCO (for example ABCL on the JVM does not support TCO - tail call optimization), it makes sense to write it portably as a loop:

(defun rev-sum-even-fib (max-val)
  (loop for a = 1 then (+ a b) and b = 0 then a
        until (> a max-val)
        when (evenp a) sum a))

Upvotes: 0

category
category

Reputation: 2165

So I've solved Euler #2 with the following tail recursive code:

(defun rev-sum-even-fib (max-val)
  (labels ((helper (sum a b)
             (cond ((oddp a)
                    (helper sum (+ a b) a)) 
                   ((> a max-val)
                    sum)
                   (t
                    (helper (+ sum a) (+ a b) a)))))
    (helper 0 1 0)))

Here, the algorithm is linear in max and evaluates in

(time (rev-sum-even-fib 4000000))

Real time: 3.4E-5 sec.
Run time: 0.0 sec.
Space: 0 Bytes

Where I've omitted the numerical answer for obvious reasons.

Upvotes: 0

sds
sds

Reputation: 60054

First, a few small issues:

  1. Use time instead of top.

  2. Common Lisp standard does not require tail recursion optimization. While many implementation do it, not all of them optimize all cases (e.g., labels).

  3. Your algorithm is quadratic in max because it computes the nth Fibonacci number separately for all indexes. You should make it linear instead.

  4. You are computing the sum of even-indexed numbers, not even-valued numbers.

Now, the arithmetic error you are seeing: 4,000,000th Fibonacci number is pretty large - about 1.6^4M ~ 10^835951. Its length is about 2,776,968.

Are you sure your lisp can represent bignums this big?

Upvotes: 3

Related Questions