🚀 go-pugleaf

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