Re: Optimization flag for unchecked fixnums in SBCL?

Paul Rubin <no.email@nospam.invalid> writes:

I looked in the manual and didn't see a way to do this.  The following
Haskell code (Euler problem 14) takes about 0.5 seconds on my old laptop:
>
    cl :: Int -> Int
    cl n = if odd n then 3*n+1 else n`quot`2
    dl n = (1+) . length . takeWhile (/= 1) . iterate cl $ n
    main = print . maximum $ [(dl n, n) | n <- [1..1000000]]
>
Int is Haskell's built-in fixnum type.  Integer is bignums and that
version takes about 7 seconds.
>
The below CL version takes 5 seconds (this is chopped down from a
memoized version that takes about 0.2 seconds).  I tried a few different
ways to tell the compiler that `collatz' should take and return fixnums,
but I didn't find the right way.  Any help?  Thanks.
>
    (defun collatz (n)
      (cond ((oddp n) (1+ (* 3 n)))
            (t (floor n 2))))
>
    (defun clen (n)
      (cond ((= n 1) 1)
            ((<= n 0) 'crash)
            (t (1+ (clen (collatz n))))))
>
    (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)

I don't understand the math but here is a quick change that shaves it
down some.

CL-USER> (time (run))
Evaluation took:
  2.054 seconds of real time
  2.052833 seconds of total run time (2.052229 user, 0.000604 system)
  99.95% CPU
  4,733,868,882 processor cycles
  0 bytes consed
 
(837799 525)

WARNING: redefining COMMON-LISP-USER::COLLATZ in DEFUN
COLLATZ
CL-USER> (compile 'collatz)
COLLATZ
NIL
NIL
CL-USER> (time (run))
Evaluation took:
  1.626 seconds of real time
  1.625390 seconds of total run time (1.625332 user, 0.000058 system)
  99.94% CPU
  3,748,148,144 processor cycles
  0 bytes consed
 
(837799 525)
CL-USER>


Here is an assist. you are getting killed with clen. i don't understand
the math well; but this should help.

(defun collatz (n)
  ;; declare the type N to number
  (declare (type number n)
           (optimize (speed 3) (space 0) (safety 0)))
  ;; this ensures N is < 32-bits wide and zeros out the rest of the bits.
  (setq n (mask-field (byte 32 0) n))
  ;; the compiler can assume N has enough space for simple arithmetic as
  ;; opposed to generic functions.
  (cond ((oddp n)
         (1+ (* 3 n)))
        (t
         ;; this will ensure that only one value is returned from floor.
         ;; Normally floor returns 2 values - here we tell the compiler that
         ;; we only want the first value.
         (nth-value 0 (floor n 2)))))


your problem with clen is the generic+ at the end of your cond
statement. I'm going to try this in C. What haskell compiler do you use?

anyway this should help (i think).