Paul Rubin <
[email protected]d> writes:
It is problem 14 of projecteuler.net .
Here is my solution, maybe not idiomatic CL since I don't write much of
that these days. It takes about 0.17 sec of user time on my laptop
using sbcl --script, or 1.1 sec with compiled clisp. It doesn't work
with interpreted clisp because the clisp interpreter has no TRO and so
the tail recursion overflows the stack. I could rewrite it iteratively
but nah. A similar C++ version with gcc -O3 takes about 0.03 sec. I
haven't experimented with changing the size of the memo table or
anything like that. ================================================================
(defun collatz (n)
(cond ((oddp n) (1+ (* 3 n)))
(t (floor n 2))))
(defvar memo (make-array 1000000 :initial-element nil))
(defun clen (n)
(cond ((= n 1) 1)
((<= n 0) 'crash)
((and (< n (length memo)) (aref memo n)) (aref memo n))
(t (let ((a (1+ (clen (collatz n)))))
(if (< n (length memo))
(setf (aref memo n) a))
a))))
(defun run (&optional (n 1) (mi 0) (ma 0))
(if (> n 1000000)
(list mi ma)
(let ((a (clen n))
(nn (1+ n)))
(if (> a ma)
(run nn n a)
(run nn mi ma)))))
(print (run))
(terpri)
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)