Newb: help with factoring function

Discussion of Common Lisp
anomaly
Posts: 6
Joined: Sun Mar 01, 2009 1:16 am
Location: North Carolina, US

Newb: help with factoring function

Post by anomaly » Sun Mar 01, 2009 1:40 am

Okay, so I'm pretty new to lisp, and in the middle of reading Practical Common Lisp, I decide to test my knowledge of loop by using it to write a prime factoring function. I realize I don't know enough, but now I'm sucked into the problem and keep looking up specifics trying to figure it out. I don't have it yet, but I think I'm close. Here's the code, tell me how close I am:

Code: Select all

(defun factor-loop (num)
  (let ((factors = '(1)) (remainder = nil) (current-num = (/ num (apply #'* factors))))
    (loop do (loop with x = 0
            while (or (= (rem num x) 0) (<= x (/ num 2)) (current-num = (/ num (apply #'* factors))))
            finally ((setf remainder (rem num x))(return)))
    appending factors remainder))
  return factors)
This is the error I'm getting, but it's too vague for me to understand exactly what's wrong:

Code: Select all

*** - LOOP: illegal syntax near REMAINDER in
       (LOOP WITH FACTORS = '(1) AND CURRENT-NUM = (/ NUM (APPLY #'* FACTORS))
        AND REMAINDER = NIL DO
        (LOOP WITH X = 0 WHILE (OR (= (REM NUM X) 0) (<= X (/ NUM 2))) FINALLY
         ((SETF REMAINDER (REM NUM X)) (RETURN)))
        APPEND FACTORS REMAINDER)
Again, I'm still quite new to lisp, so the answer is probably glaringly obvious.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Newb: help with factoring function

Post by ramarren » Sun Mar 01, 2009 3:31 am

First, your LET bindings are malformed. There is no "=" there, just ((variable1 binding1)(variable2 binding2) ... ). In any case you probably do not want those at all, since they can be expressed inside the loop.

Your outer loop has no terminating condition, and appending doesn't work that way. I don't even really understand what inner loop is supposed to achieve, but (current-num = (/ num (apply #'* factors))) is definitely wrong, and there are unnecessary parentheses in finally clause. The final "return factors" looks like loop expression, but is outside a loop, so it doesn't do anything.

I would suggest that you review the basics before trying to do something with loop. Also, I have always found the Iterate library to be more clear than LOOP for iteration.

anomaly
Posts: 6
Joined: Sun Mar 01, 2009 1:16 am
Location: North Carolina, US

Re: Newb: help with factoring function

Post by anomaly » Sun Mar 01, 2009 5:15 am

How much better is this?

Code: Select all

(defun factor-loop (num)
  (loop with factors = '(1)
        with remainder = nil 
        with current-num = (/ num (apply #'* factors)) then (/ num (apply #'* factors))
        do (loop with x = 0
                 while (or (= (rem num x) 0) (<= x (/ num 2)))
                 finally ((setf remainder (rem num x))(return)))
  until (= num (apply #'* factors))
  collecting remainder into factors))
I'm still getting an error, though a slightly different one:

Code: Select all

*** - LOOP: illegal syntax near THEN in
       (LOOP WITH FACTORS = '(1) WITH REMAINDER = NIL WITH CURRENT-NUM =
        (/ NUM (APPLY #'* FACTORS)) THEN (/ NUM (APPLY #'* FACTORS)) DO
        (LOOP WITH X = 0 WHILE (OR (= (REM NUM X) 0) (<= X (/ NUM 2))) FINALLY
         ((SETF REMAINDER (REM NUM X)) (RETURN)))
        UNTIL (= NUM (APPLY #'* FACTORS)) COLLECTING REMAINDER INTO FACTORS)
As for an explanation, the idea is to find the prime factorization of a number. Starting with the original number, say 12, we find the smallest number that it divides by evenly(technically it's the smallest prime number, and only looking at prime numbers would probably speed things up a bit, but I'm obviously not ready for optimization yet), which would be 2 in this example. Now we add 2 to our list of factors (initialized with 1) and define our new, or "current", number to be 12 / 2, or 6, and repeat. There's no actual recursion in this example, but that's the general idea. The inner loop finds the lowest prime factor. The outer loop updates the list of factors and current-num, and ends when the list of factors multiplies up to the original number.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Newb: help with factoring function

Post by ramarren » Sun Mar 01, 2009 6:02 am

It's closer, but it still seems like it was assembled by a tornado ;-)

Working code would look somewhat like this, although I try to avoid loop, so can't be sure if this is the most idiomatic way

Code: Select all

(defun factor-loop (num)
  (loop for factors = '(1) then (cons remainder factors)
        for current-num = (/ num (apply #'* factors))
        until (= num (apply #'* factors))
        for remainder = (loop for x from 2
                              until (zerop (rem current-num x))
                              finally (return x))
        finally (return factors)))
In inner loop you have to perform arithmetic iteration. "with x =" establishes a constant binding, so your inner loop will loop forever. Also, as I said before, finally takes a single form, so you have too many parentheses, and in any case the (return) there doesn't do anything, because that loop would return anyway if it ever reached the finally clause, which it wouldn't.

Also, you cannot collect into an existing variable. If you want a variable to have an initial value, I think the best way is like in my example code, to use for...=...then. Note that "then" works only with for, not with "with" as you have tried, also if the then is the same as initial it is not necessary.

anomaly
Posts: 6
Joined: Sun Mar 01, 2009 1:16 am
Location: North Carolina, US

Re: Newb: help with factoring function

Post by anomaly » Sun Mar 01, 2009 6:29 am

I thank you for your patience. When I tried to run your example it told me:

Code: Select all

WARNING: LOOP: FOR clauses should occur before the loop's main body
I changed it slightly (superficially?) to this:

Code: Select all

(defun factor (num)
  (loop for factors = '(1) then (cons remainder factors)
        for current-num = num then (/ num (apply #'* factors))
        for remainder = (loop for x from 2
                              until (zerop (rem current-num x))
                              finally (return x))
        until (= num (apply #'* factors))
        finally (return factors)))
and it refuses to end. One of these loops must be stuck.

ramarren
Posts: 613
Joined: Sun Jun 29, 2008 4:02 am
Location: Warsaw, Poland
Contact:

Re: Newb: help with factoring function

Post by ramarren » Sun Mar 01, 2009 6:37 am

SBCL doesn't emit this warning, but CLISP does... weird, especially since the this loop doesn't even have a main body, unless the until clause counts. The reason that the loop goes infinite is that it tries to compute the inner loop for current-num equal to 1, and the termination condition is never true. With the until in its original position it quits before that.

The correct way to reform the loop would be:

Code: Select all

(defun factor-loop (num)
  (loop for factors = '(1) then (cons factor factors)
        for current-num = (/ num (apply #'* factors))
        for factor = (unless (= current-num 1)
                       (loop for x from 2
                             until (zerop (rem current-num x))
                             finally (return x)))
        until (= num (apply #'* factors))
        finally (return factors)))
Or, even better, separate the inner loop into another function. Small functions doing one thing only are usually easiest to write, read and debug.

Harleqin
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: Newb: help with factoring function

Post by Harleqin » Sun Mar 01, 2009 8:47 am

I think that the extended LOOP construct is too confusing for beginners. It is better to start out with the simple DO syntax. Even better, this example application lends itself nicely for learning recursion.
"Just throw more hardware at it" is the root of all evil.
Svante

Rune Nesheim
Posts: 2
Joined: Sun Jan 04, 2009 5:44 pm

Re: Newb: help with factoring function

Post by Rune Nesheim » Sun Mar 01, 2009 11:57 am

Hi! First post and lisp newbie ;)

I had a go at writing a recurse version:

Code: Select all

(defun find-next-factor (n x)
  (if (zerop (rem n x))
      x
      (find-next-factor n (+ x 1))))

(defun factors-rec (n)
  (labels ((rec (n acc)
             (let ((current-num (/ n (apply #'* acc))))
               (if (= current-num 1)
                   acc
                   (rec n (cons (find-next-factor current-num 2) acc))))))
    (rec n nil)))
How is that?

Harleqin
Posts: 71
Joined: Wed Dec 17, 2008 5:18 am
Location: Bonn, Germany

Re: Newb: help with factoring function

Post by Harleqin » Sun Mar 01, 2009 1:33 pm

Not too bad, Rune. One question, though: each cycle, you are dividing n by all factors that you have found so far. Can you reduce the amount of calculation here?
"Just throw more hardware at it" is the root of all evil.
Svante

anomaly
Posts: 6
Joined: Sun Mar 01, 2009 1:16 am
Location: North Carolina, US

Re: Newb: help with factoring function

Post by anomaly » Sun Mar 01, 2009 2:22 pm

Okay, I have a working LOOP version, so I decided to see if I could translate it into one based on DO.

LOOP factor:

Code: Select all

(defun factor (num)
  (loop for factors = nil then (cons factor factors)
        for current-num = (/ num (apply #'* factors))
        for factor = (unless (= current-num 1)
                       (loop for x from 2
                             until (zerop (rem current-num x))
                             finally (return x)))
        until (= num (apply #'* factors))
        finally (return (reverse factors))))
DO factor:

Code: Select all

(defun factor (num)
  (do* ((factors nil (cons factor factors))
        (current-num num (/ num (apply #'* factors)))
        (factor (do((x 2 (+ x 1)))
                     ((or (zerop (rem current-num x)) (= current-num 1)) x)
                    )))
         ((= num (apply #'* factors)) (reverse factors))
      ))
As I said, the first one works perfectly fine, but the second one only seems to work for numbers of the form (a^b). For example, 8, 16, and 9 all work just right. However when I try 12, or 6, it freezes for several minutes before saying:

Code: Select all

*** - APPLY: too many arguments given to *
I think the inner DO loop is looping infinitely and adding 1 to the end of factors over and over again until it's just to big to evaluate, but that's just a theory and I don't know why it would.

Post Reply