anjo@swi.psy.uva.nl (Anjo Anjewierden) (11/03/90)
I read: Richard A. O'Keefe, "The Craft of Prolog", MIT Press 1990. with great interest. There is at least one section that may be inconsistent with statements made elsewhere in the book. Section 4.4 gives the following problem (the section is about reducing the search space): The problem is as follows: "D1, D2, ..., D9 are distinct decimal digits, none of them zero, such that for each 1 <= n <= 9 the n digits D1 ... Dn form a number which is divisible by n." [p. 126] A Prolog program solving this problem is the following (I have paired the select/3 and divisible/2 calls inside answer/1): % "The Craft of Prolog", p. 127 divisible(N, Ds) :- divisible(Ds, 0, N). divisible([], 0, _). divisible([D|Ds], R0, N) :- R1 is (R0*10 + D) mod N, divisible(Ds, R1, N). % "The Craft of Prolog", p. 127 (adapted) answer(Solution) :- Solution = [D1,D2,D3,D4,D5,D6,D7,D8,D9], R0 = [1,2,3,4,5,6,7,8,9], select(D1, R0, R1), divisible(1, [D1]), select(D2, R1, R2), divisible(2, [D1,D2]), select(D3, R2, R3), divisible(3, [D1,D2,D3]), select(D4, R3, R4), divisible(4, [D1,D2,D3,D4]), select(D5, R4, R5), divisible(5, [D1,D2,D3,D4,D5]), select(D6, R5, R6), divisible(6, [D1,D2,D3,D4,D5,D6]), select(D7, R6, R7), divisible(7, [D1,D2,D3,D4,D5,D6,D7]), select(D8, R7, R8), divisible(8, [D1,D2,D3,D4,D5,D6,D7,D8]), select(D9, R8, R9), divisible(9, [D1,D2,D3,D4,D5,D6,D7,D8,D9]). If you study the remainder of the book it is not at all difficult to see what is wrong with this program: why is the partial solution represented as a list? By the time answer/1 gets to the last sub-goal it will have considered D1 8 times, D2 7 times (etc.). Applying the principle of not wasting space and time I arrived at: % Anjo Anjewierden, University of Amsterdam, 02/10/90 % d(+N, +Value, +Digit, -NewValue) % % Is true if appending Digit to Value is divisble by N % (all base 10). Example: d(3, 12, 3, 123) is true % because 123 is divisible by 3. divisible(N, Value, Digit, NewValue) :- NewValue is (10 * Value) + Digit, 0 is NewValue mod N. answer([D1,D2,D3,D4,D5,D6,D7,D8,D9]) :- R0 = [1,2,3,4,5,6,7,8,9], select(D1, R0, R1), divisible(1, 0, D1, V1), select(D2, R1, R2), divisible(2, V1, D2, V2), select(D3, R2, R3), divisible(3, V2, D3, V3), select(D4, R3, R4), divisible(4, V3, D4, V4), select(D5, R4, R5), divisible(5, V4, D5, V5), select(D6, R5, R6), divisible(6, V5, D6, V6), select(D7, R6, R7), divisible(7, V6, D7, V7), select(D8, R7, R8), divisible(8, V7, D8, V8), select(D9, R8, []), divisible(9, V8, D9, _). In Quintus Prolog 2.4 the O'Keefe version takes 0.9 seconds and my version takes 0.5 seconds. If you want you can apply the same problem specific optimisations that O'Keefe uses and make it a lot faster still. I would greatly appreciate any comments on the above as I'm currently writing a review of the book. :- Anjo, !. %-------------------------------------------------------------------------- % Anjo Anjewierden NET: anjo@swi.psy.uva.nl % % Department of Social Science Informatics % University of Amsterdam, Herengracht 196 TEL: +31 20 525 2337 % 1016 BS Amsterdam, The Netherlands FAX: +31 20 525 2347 %---------------------------------------------------------------------------
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (11/05/90)
In article <4473@swi.swi.psy.uva.nl>, anjo@swi.psy.uva.nl (Anjo Anjewierden) writes: > If you study the remainder of the book it is not at all difficult > to see what is wrong with this program: why is the partial solution > represented as a list? Answer: we have a number with 9 decimal digits. I am aware of Prolog systems with 14-bit, 16-bit, 17-bit, 18-bit, 20-bit, 24-bit, 28-bit, 29-bit, and 32-bit integer arithmetic, as well as logical arithmetic (by which I mean arithmetic with no stupid bit bound). How large can an integer with 9 distinct decimal digits get? 987654321 How many bits does this need? 30 Will that _work_ in the Prolog systems I was using at the time? a certain Prolog interpreter on a Sun-3/50 : NO a certain Prolog compiler on a Sun-3/50 : NO a certain Prolog compiler on a PC : NO another Prolog compiler on a PC : NO So _could_ I have used Anjewierden's method? No. Recite after me: "not every Prolog system provides 32-bit integers". -- The problem about real life is that moving one's knight to QB3 may always be replied to with a lob across the net. --Alasdair Macintyre.
brady@swift.cs.tcd.ie (11/05/90)
In article <4473@swi.swi.psy.uva.nl>, anjo@swi.psy.uva.nl (Anjo Anjewierden) writes: > I read: > > Richard A. O'Keefe, "The Craft of Prolog", MIT Press 1990. > > with great interest. There is at least one section that may be > inconsistent with statements made elsewhere in the book. Section 4.4 > gives the following problem (the section is about reducing the > search space): > > The problem is as follows: > > "D1, D2, ..., D9 are distinct decimal digits, none of them > zero, such that for each 1 <= n <= 9 the n digits D1 ... Dn > form a number which is divisible by n." [p. 126] > > A Prolog program solving this problem is the following (I have paired > the select/3 and divisible/2 calls inside answer/1): > I've been trying to run this to examine it. It's missing the select/3 clauses, & I don't have the book. Could you post them please? Mike Brady
ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) (11/06/90)
In article <7299.273583de@swift.cs.tcd.ie>, brady@swift.cs.tcd.ie writes: > I've been trying to run this to examine it. It's missing the select/3 > clauses, & I don't have the book. Could you post them please? select/3 remains as it has been for the past 11+ years: select(X, [X|L], L). select(X, [H|T], [H|R]) :- select(X, T, R). (If you have the DEC-10 Prolog, C Prolog, or QP libraries, you already have it.) The point is that the example starts out as answer(Solution) :- Solution = [D1,D2,D3,D4,D5,D6,D7,D8,D9], perm([1,2,3,4,5,6,7,8,9], Solution), forall(append(D1_to_N, _, Solution), ( length(D1_to_N, N), divisible(N, D1_to_N) )). The first step is to open up the call to perm/2 (producing 9 calls to select/3) and expand the forall/2 (producing 9 calls to divisible/2). Then we start shuffling things around, reducing ranges, eliminating redundant tests, and so on. The final version in the book can be improved (following Anjo's observation) to answer([D1,D2,D3,D4, 5, D6,D7,D8,D9]) :- select(D1, [1,3,7,9], R1), select(D2, [2,4,6,8], R2), select(D3, R1, R3), ((D1*10+D2)*10+D3) mod 3 =:= 0, select(D4, R2, R4), (D3*10+D4) mod 4 =:= 0, select(D6, R4, [D8]), (D4*100+50+D6) mod 6 =:= 0, select(D7, R3, [D9]), ((D6*10+D7)*10+D8) mod 8 =:= 0, divisible(7, [D1,D2,D3,D4,5,D6,D7]). But that can't be improved any further, because while it is reasonable to expect a Prolog system to handle integers in < 1000, the seven decimal digits we need in the last test are more than some otherwise ok Prologs can provide. (Actually, DEC-10 Prolog _could_ provide the necessary 24 bits, but only within a single expression; Anjo's code would not have worked.) -- The problem about real life is that moving one's knight to QB3 may always be replied to with a lob across the net. --Alasdair Macintyre.