Page 2 of 2

Re: Newb: help with factoring function

Posted: Sun Mar 01, 2009 5:13 pm
by Harleqin
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.

Re: Newb: help with factoring function

Posted: Mon Mar 02, 2009 4:19 pm
by anomaly

Code: Select all

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

Re: Newb: help with factoring function

Posted: Mon Mar 02, 2009 4:39 pm
by Harleqin
Can you find a replacement for this line:
anomaly wrote:

Code: Select all

        (current-num num (/ num (apply #'* factors)))
which doesn't need to multiply all factors found so far?

Re: Newb: help with factoring function

Posted: Tue Mar 03, 2009 7:37 am
by anomaly
Harleqin wrote:Can you find a replacement for this line:
anomaly wrote:

Code: Select all

        (current-num num (/ num (apply #'* factors)))
which doesn't need to multiply all factors found so far?

Code: Select all

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

Code: Select all

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

Re: Newb: help with factoring function

Posted: Tue Mar 03, 2009 9:54 am
by Harleqin
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.

Re: Newb: help with factoring function

Posted: Sat Mar 07, 2009 8:42 pm
by gugamilare
Let me take a look...

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

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