Newb: help with factoring function

Discussion of Common Lisp
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 5:13 pm

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.
"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 » Mon Mar 02, 2009 4:19 pm

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

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

Re: Newb: help with factoring function

Post by Harleqin » Mon Mar 02, 2009 4:39 pm

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?
"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 » Tue Mar 03, 2009 7:37 am

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

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

Re: Newb: help with factoring function

Post by Harleqin » Tue Mar 03, 2009 9:54 am

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.
"Just throw more hardware at it" is the root of all evil.
Svante

gugamilare
Posts: 406
Joined: Sat Mar 07, 2009 6:17 pm
Location: Brazil
Contact:

Re: Newb: help with factoring function

Post by gugamilare » Sat Mar 07, 2009 8:42 pm

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.

Post Reply