debray@arizona.edu (Saumya K. Debray) (12/28/88)
A couple of recent postings to this group have expressed relief that Richard O'Keefe is no longer around to criticize the style and substance of Prolog code posted to the net. After waiting for a while to see the reaction to such sentiments, and being surprised at the silence, let me state for the record that I'm disappointed that people should feel this way: I can't remember any posting by Richard that was technically incorrect, and sulking at constructive criticism seems immature to me. For the record, Richard has criticized my code more than once. I've learned a lot from his comments, both on my code and on code written by others. ---------------------------------------------------------------------- While I can't pretend to be Richard O'Keefe (that would be hard to do :-), there were a few points in some recently posted code that seemed worth commenting on. The code in question is > isprime(2). > isprime(M) :- > \+ divides(M, 2), > J is M//2+1, > isprime_x(M, J, 1). > > divides(I, D) :- I is I//D*D. 1. A number of recent postings had this definition for divisibility testing. Unless I'm missing something, the definition divides(I, D) :- I mod D =:= 0. seems quite a bit easier to understand. Besides, on many machines that have an integer-division instruction, the remainder is computed at the same time and left in some easily accessed location, typically a register. On such machines, a good compiler would be able to avoid generaing a "multiply" instruction with the second definition, but probably not with the original one. Since multiplication is typically a very expensive operation, and this program uses divides/2 a lot, this (potential) savings from this seem worthwhile. 2. What is really wanted, instead of \+ divides(M, 2), is not_divides(M, 2), where not_divides/2 is defined as not_divides(I, D) :- I mod D =\= 0. with this, there won't be a choice point created for the \+. 3. To test whether a number N is prime, it's really not necessary to test all the way up to ceil(N/2 + 1), where ceil(K) is the least integer no smaller than K -- it suffices to test upto ceil(sqrt(N) + 1). On SB-Prolog, for example, testing whether 1291 is a prime took 1220 mS on a Vax-8650 when testing upto ceil(N/2 + 1), but only 60 mS when testing upto ceil(sqrt(N)+1) -- a speedup of a factor of over 20! [I didn't try Quintus and Sicstus Prologs because as far as I could see, they didn't provide a sqrt function, and I was too lazy to write one.] -- Saumya Debray CS Department, University of Arizona, Tucson internet: debray@arizona.edu uucp: arizona!debray