dumb optimation problem

Made the following agorithm:

(defmacro a= (val1 func)
   `(let ((it ,val1))
      (= it (funcall ,func it))))

(defun lame-prime-check (p)
   (declare (fixnum p i)
            (optimize (safety 0) (fixnum-safety 0)))
    (cond ((< p 2) nil)
           ((a= (/ p 2) #'floor) nil)
           (t
            (loop for i from 3 to (isqrt p) by 2 do
                  (when (a= (/ p i) #'floor)
                    (return-from lame-prime-check nil)))
            t))

CAPI-TUTOR 97 > (time (loop for i from 0 to 1000000 do
                             (lame-prime-check i)))
Timing the evaluation of (LOOP FOR I FROM 0 TO 1000000 DO  
(LAME-PRIME-CHECK I))

User time    =       19.656
System time  =        0.000
Elapsed time =       19.719
Allocation   = 428171796 bytes
0 Page faults
Calls to %EVAL    15000061
NIL

(Managed to save 11 s of the original version.)
Why do I get the large allocation value?
I suspect (/ p i) has something to do with it.
Before the macro optimation the value was exactly double this.

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

Re: dumb optimation problem

On 6 Feb 2007, at 20:11, John Thingstad wrote:

>
> I suspect (/ p i) has something to do with it.
> Before the macro optimation the value was exactly double this.
>

Me too.  if you divide two integers you will cons a rational in  
almost all cases.  You probably want either the second value of FLOOR  
or MOD.

--tim

Re: dumb optimation problem

Tim Bradshaw <tfb@cley.com> writes:

> Me too.  if you divide two integers you will cons a rational in  
> almost all cases.  You probably want either the second value of FLOOR  
> or MOD.

Probably REM:

(defun lame-prime-check (p)
  (declare (fixnum p i)
           (optimize (safety 0) (fixnum-safety 0)))
  (cond ((< p 2) nil)
        ((= (rem p 2) 0) nil)
        (t
         (loop for i from 3 to (isqrt p) by 2 do
               (when (= (rem p i) 0)
                 (return-from lame-prime-check nil)))
         t)))
-- 
  (espen)

Re: dumb optimation problem

Yeah, does seem to be the divide. Here's what I came up with, using the second val of floor as suggested above:

(proclaim '(inline candidate-prime))
(defun candidate-prime (p v)
(multiple-value-bind (q r) (floor p v)
    (declare (ignorable q))
    (not (or (< p 2) (zerop r)))))

(defun cb-lame-prime-check (p)
(when (candidate-prime p 2)
    (loop for i from 3 to (isqrt p) by 2
          always (candidate-prime p i))))

CL-USER 1 > (extended-time (dotimes (idx 100000) (cb-lame-prime-check idx)))
Timing the evaluation of (PROGN (DOTIMES (IDX 100000) (CB-LAME-PRIME-CHECK IDX)))

User time    =        0.390
System time =        0.002
Elapsed time =        0.545
Allocation   = 2411780 bytes
18 Page faults
Calls to %EVAL    1300057

                                      total    /   user     /   system
total gc activity              =      0.012675 /   0.012605 /   0.000070
main promote (    0 calls)     =      0.000000 /   0.000000 /   0.000000
mark and sweep (    2 calls)   =      0.012675 /   0.012605 /   0.000070
internal promote (    0 calls) =      0.000000 /   0.000000 /   0.000000
promote (    0 calls)          =      0.000000 /   0.000000 /   0.000000
fixup (    0 calls)            =      0.000000 /   0.000000 /   0.000000
compact (    0 calls)          =      0.000000 /   0.000000 /   0.000000
NIL

Cheers,
Chris

On 2/7/07, Espen Vestre <ev@netfonds.no > wrote:

Tim Bradshaw <tfb@cley.com> writes:

> Me too.  if you divide two integers you will cons a rational in
> almost all cases.  You probably want either the second value of FLOOR
> or MOD.

Probably REM:

(defun lame-prime-check (p)
  (declare (fixnum p i)
           (optimize (safety 0) (fixnum-safety 0)))
  (cond ((< p 2) nil)
        ((= (rem p 2) 0) nil)
        (t
         (loop for i from 3 to (isqrt p) by 2 do
               (when (= (rem p i) 0)
                 (return-from lame-prime-check nil)))
         t)))
--
  (espen)