Just learning- Syntax Help please?

[Frisco]

Code: Select all

(defun bigPrime (number)
  (let ((ans 0))
  (do ((iterator 1 (+ iterator 2)))
      ((equal number iterator)'yay!)
    (do ((currCheck 1 (+ currCheck 1)))
	((equal currCheck iterator))
	    (if (equal currCheck iterator)
		(setf ans currCheck)
		(if (equal 0 (rem currCheck iterator))
		    (setf currCheck iterator)
		    ()))))))

The object of this program is to find the largest prime factor of the passed number.
It compiles, but I get a warning that "ans" is unused.
So I'm obviously doing something wrong, because it's ready to be used, 4 lines up from the bottom.

So, just looking for help, but also open to comments about how to make this code faster and more efficient, as I'm new to Lisp and used to thinking in C.

[ramarren]

Stylistic notes: Don't use camelCase. Common Lisp reader upcases symbols by default, so it loses capitalization. Usually components of symbol name are separated by dashes. Also, don't use EQUAL for numeric comparison, use =, which is faster and checks types. It is usually best to use most specific construct. Use WHEN/UNLESS for conditionals with only one branch.

Most people also don't use DO directly. I would recommend using either LOOP or iterate. In general changing iteration counter from inside the loop is not a good idea, since it makes the code unclear. Where did your learn Lisp from? I would recommend Practical Common Lisp.

It compiles, but I get a warning that "ans" is unused.

SBCL 1.0.45 doesn't give such warning. But the value of "ans" is never read, so some compilers might warn about it. The name implies that it is supposed to be returned, but it is not. Creating a variable for return value is rarely necessary, it is usually best to express a function as nested expressions, which will return the required value naturally.

I don't really see how your algorithm is supposes to achieve its stated goal. It doesn't even terminate for even numbers. What you need to find a largest prime factor, unless I'm missing some algorithm specifically for this, is to either find all primes smaller than number and test them one by one, or do a full factorization and pick the greatest factor. The latter is simplest to implement, especially if you apply brute force without even checking primality, by using simple trial division.

[Frisco]

First, thanks for trying to explain things out instead of face-palming and giving up.

I'm (attempting to) teach myself from the book "ANSI Common LISP", by Paul Graham.
I'll check out your link and see if it helps.

Wasn't thinking at all when deciding to use camelCase. Taught to do in C++ and it just kind of came naturally.

Haven't gotten to the "loop" or "iterate" commands yet, but thought I could do this with "do".

It's intentionally supposed to skip even numbers for speed, seeing as none of them are prime. Yes, I'm aware that it wouldn't terminate if fed an even number. I'll only be plugging in odds.

How I planned the algorithm:
This was written with the intention of brute-forcing from 1 to the number, checking all of them for primality. "Ans" would store the biggest one and return it at the end.

So thanks again- I'll fix the stylistic stuff and then find some other program to write until I've seen how loop and iterate work.

[ramarren]

I'm (attempting to) teach myself from the book "ANSI Common LISP", by Paul Graham.

Unfortunately, Paul Graham doesn't really like Common Lisp as it is. Which is why he created his own language, Arc. Personally I prefer Common Lisp, even though it is far from perfect. There are some notes here which points out how Grahams style differs from more typical CL style.

Wasn't thinking at all when deciding to use camelCase. Taught to do in C++ and it just kind of came naturally.

I suppose it beats using underscores as separators, but thankfully Lisp doesn't have a problem with dashes in identifiers (and many more characters which are usually invalid). One advantage here is that it allows much nicer symbol completion than in many other dynamic languages, since dashes act as unambiguous component separator, so CL supporting editor (usually Emacs) can easily expand for example m-v-b to multiple-value-bind, which makes using those long operators much less cumbersome.

This was written with the intention of brute-forcing from 1 to the number, checking all of them for primality. "Ans" would store the biggest one and return it at the end.

But the problem is I don't see where you check that the number is not only prime, but a factor of your input number. As it is, as far as I can tell, it find a biggest prime smaller or equal than the number, which is very much not the same thing. One way to approach it is to find the smallest factor, which must be a prime for obvious reasons, and then repeat on a reduced number until it is boiled down to one. This avoids separate primality testing, although it is obviously not really efficient. I guess the other way would be to generate all primes up to half a number using Eratosthenes sieve and check them one by one from the top. That is fairly trivial. As long as your numbers are smaller than array-dimension-limit, but at that point it would consume too much time anyway.

until I've seen how loop and iterate work.

Note that those are quite similar. One main difference are that LOOP is built in, and iterate is not. It is a really nice example how CL can be extended with macros, since it is just a library. Currently the best and pretty good way to install libraries is quicklisp. The reason why I personally prefer iterate is that is uses symbolic expressions (ie. parentheses) more, which makes it much easier to manipulate with Emacs+paredit s-exp handling operations.

[Warren Wilkinson]

But the problem is I don't see where you check that the number is not only prime, but a factor of your input number. As it is, as far as I can tell, it find a biggest prime smaller or equal than the number, which is very much not the same thing.

Yeah I thought so too at first. I was looking for a multiplication followed by an = test. But Frisco actually uses a rem and zerop test (which I think is the better way to test).

Let me just add some spacing to make the code more readable on this forum. Frisco, you never say if the function is giving you the answers you wanted or not -- does it work when you run it?

Code: Select all

(defun bigPrime (number)
  (let ((ans 0))
    (do ((iterator 1 (+ iterator 2)))
           ((equal number iterator) 'yay!)
      (do ((currCheck 1 (+ currCheck 1)))
             ((equal currCheck iterator))
         (if (equal currCheck iterator)
            (setf ans currCheck)
            (if (equal 0 (rem currCheck iterator))
                (setf currCheck iterator)
                ()))))))

If it works great, the only problem I have is (setf currCheck iterator). This makes it tricky to mentally follow the loops. It might be clearer written as (these are code sketches, I haven't tested them):

Code: Select all

(defun primep (n)
   (do ((i 2 (1+ i)))
         ((= i n) t)
     (when (zerop (rem n i)) (return-from primep nil))))

(defun biggest-pfactor (n)  ;; guaranteed to terminate at i = 1. 
  (assert (> n 0))
  (do ((i n (1- i)))
         ((and (primep i) (zerop (rem n i))) i)))

Another (faster) option would be to precompute the primes.

Code: Select all

(defvar *primes* '(23 17 13 7 5 3 2))  ;; Primes from biggest to smallest.

(defun biggest-pfactor (n) 
   (do ((primes *primes* (cdr primes)))
          ((zerop (rem n (car primes))) (car primes))))

[ramarren]

Yeah I thought so too at first. I was looking for a multiplication followed by an = test. But Frisco actually uses a rem and zerop test (which I think is the better way to test).

That is the primality test. There is only one REM and it doesn't involve the number itself.

[Warren Wilkinson]

That is the primality test. There is only one REM and it doesn't involve the number itself.

My bad. I am a poor loop decoder =)

[Frisco]

Trying to catch up on all of the comments here...

-No, it doesn't run at all in its current state. Not even incorrectly. It throws an error when I try to run it.

- Now that you all sufficiently bashed _ANSI Common Lisp_ is there another free (or very cheap) book or online tutorial that teaches Common Lisp? A site that has practice exercises? How did all of you learn?

- The user-defined libraries link is cool- thanks.

- Completely forgot zerop...thanks again.

- Upon review, you're right, it never actually checks whether the prime is a factor of the passed number. Kinda getting that feeling one gets after realizing they did something exceedingly dumb.

- The code is looking a lot better now. Thanks again again for all the help.

[ramarren]

- Now that you all sufficiently bashed _ANSI Common Lisp_ is there another free (or very cheap) book or online tutorial that teaches Common Lisp? A site that has practice exercises? How did all of you learn?

I don't think "bashing" is quite the right word... ANSI Common Lisp is not a bad programmin/Lisp book, it is just not quite exactly about Common Lisp specifically. Practical Common Lisp is available online. It doesn't have exercises though. PAIP is a great book, and despite the name it is mostly about CL rather than AI, but it is alas not legally available online, and it is quite expensive. There is Gentle Introduction to Symbolic Computation, but it explains things from a very basic level which might not be suitable if you have significant experience with programming already.

I have found in the past Common Lisp the Language to be helpful. It is not really a tutorial, and it predates the ANSI standard, so some parts are out of date, but it is somewhat more accessible than the hyperspec. Of course, learning to read the hyperspec is fundamental, but perhaps not the best way to learn the language.

[findinglisp]

I would recommend both ANSI Common Lisp (ACL) and Practical Common Lisp (PCL) as good first Common Lisp books, as long as you are familiar with programming in some other language already. I don't even really agree with Ramarren that Graham doesn't like Common Lisp. I think he does; he just designed ARC to shave off the warts he saw. I don't think anybody can look at any language and honestly say, "That's completely perfect; wouldn't change a thing." Every language I have ever worked with has one wart or another. Lisp is just so mind-blowingly amazing when you get the hang of it that you care less and less about the warts.

IMO, it's more proper to say that Graham has a fairly idiomatic Lisp style. He prefers functional code and generally doesn't like CLOS. But as a newbie, you shouldn't be tackling CLOS yet in any case. So, learning from Graham is perfectly appropriate, IMO. Then, go pick up PCL and get a big dose of advanced CLOS, which PCL handles quite well, IMO.

In short, don't stress on your starting point. ACL is as good a starting point as any. Just realize that you're learning one man's point of view and style, which you would be in any case. So be sure to broaden yourself later by reading a couple more books. As an aside, I was one of those guys who always used (uses?) K&R indenting when writing C code, mostly because that was the first C-programming book I ever read and I simply adopted it. You'll probably pick up some biases from Graham, too, but that's no biggie. Just realize that you have them. Common Lisp is a rich language that can accommodate a number of different programming styles. None are particularly more "right" than another; just different.