Newb: help with factoring function

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:

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

*** - 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.

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.

How much better is this?

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

*** - 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.

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

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

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

WARNING: LOOP: FOR clauses should occur before the loop's main body

I changed it slightly (superficially?) to this:

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

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:

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

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.

Hi! First post and lisp newbie

I had a go at writing a recurse version:

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

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?

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

LOOP factor:

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

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

*** - 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.

I think that you should first write a function that gives you the next prime number, and then use this function in your factorization function.

(defun primep (number)
  (when (> number 1)
    (loop for fac from 2 to (isqrt number) never (zerop (mod number fac)))))

(defun next-prime (number)
  (loop for n from (+ number 1) when (primep n) return n))

(defun factor (num)
  (do* ((factors nil (cons factor factors))
        (current-num num (/ num (apply #'* factors)))
        (factor (do((x (next-prime 0) (next-prime x)))
                     ((or (zerop (rem current-num x)) (= current-num 1)) x))))
         ((= num (apply #'* factors)) (reverse factors))))

Still having the same problem.

Oh, and if you think you recognize the first two functions, I'm still reading Practical Common Lisp .

Can you find a replacement for this line:

anomaly wrote:

        (current-num num (/ num (apply #'* factors)))

which doesn't need to multiply all factors found so far?

Harleqin wrote:Can you find a replacement for this line:

anomaly wrote:

        (current-num num (/ num (apply #'* factors)))

which doesn't need to multiply all factors found so far?

(current-num num (/ current-num (first factors)))

How's that? It works fine, but I'm still having the previously mentioned problem.

Edit: This one is using loop and it works perfectly fine:

(defun primep (number)
  (when (> number 1)
    (loop for fac from 2 to (isqrt number) never (zerop (mod number fac)))))

(defun next-prime (number)
  (loop for n from (+ number 1) when (primep n) return n))

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

Yes, you can refactor the end test of your outer loop in the same way.

As for your problem: your factor is never changed after it is set for the first time. factors is an ever growing list of 2s.

Let me take a look...

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

This is the version before using primep functions. By the way, finding the next prime is not a good idea, it is faster not to execute some simple divisions then finding the next prime first, because finding the next prime will take much more divisions in general. A good idea, though, is to keep a variable holding the last factor, so you will need to test only for factors equal or greater than the last factor found. But that you can do later, after fixing this.

Now, the problem is the syntax of do. The inner do is evaluated only once and factor is bound (eternally) to it, therefore the lisp ends up divinding undefinitely the number 6 by 2 until the list factors is so long it can't even make a function call - because the function can't handle that many arguments.

The correct version should be:

(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))
                   (do ((x 2 (+ x 1)))
                     ((or (zerop (rem current-num x)) (= current-num 1)) x))))
         ((= num (apply #'* factors)) (reverse factors))
      ))

Off course, you can bind the inner loop in a flet or a external defun, which would look much better then this mess. But there is one more issue I want to point.

What happens when you call (factor 6) (with the new version off course)?

factors --> nil
current-num --> 6

The inner do returns 2 (the call (rem 6 2) evals to zero).
Note that right now factors is still nil. Therefore (apply #'* factors) is equivalent to (*) and returns 1.
Then the test fails and the do is executed again.

factors --> (2)
current-num --> 3

Then the inner do returns 3.
Note again that here, 3 was still not collected in the list factors, therefore the test fails again.

factors --> (3 2)
current-num --> 1

The inner do returns 2 because (= current-num 1) is true. Then the test succeds and the correct answer is returned.

Well, this version works, but I see something weard here, and I believe you see it as well. The loop version has the same issue.