Re: Prime Sums In A Grid



LudovicoVan <julio@xxxxxxxxxxxxx> writes:

My attempted Prolog code is below, and I wouldn't know how to make it
any faster, considering also that the test for primality here is not
the significant bottleneck.

First a few general points: Some of the !/0 are unnecessary due to first
argument indexing. Second, there is a nice way to write transpose/2 such
that you can use first argument indexing there as well and need no !/0,
left as an exercise. Further, get_row/4 and get_rows/4 seem unnecessary:
You can use lists of lists in the first place and use append/2 (!) to
get the right representation for the CLP(FD) predicates. Instead of
fail/0, there is of recent the much nicer false/0 in SWI. Instead of
label([X]), you can use indomain(X).

Now how to make it run faster? In the previous solution, the constraint
solver is not used to its fullest advantage: Instead, it is essentially
a generate-and-test approach, where sums are generated and then tested
for primality. The final label/1 call in matrix/2 is not even needed in
that approach: All elements are already instantiated.

Suppose we have the following simplistic sieve:

primes_upto(N, Ps) :-
numlist(2, N, Ps0),
sieve(Ps0, Ps).

sieve([], []).
sieve([P|Ns0], [P|Rest]) :-
sublist(no_multiple(P), Ns0, Ns),
sieve(Ns, Rest).

no_multiple(P, N) :- N mod P =\= 0.

And in matrix/2 use:

...
MaxSum is Square * Side,
primes_upto(MaxSum, Primes),
list_to_domain(Primes, PD),
constraint_tuples(Rows, PD),
constraint_tuples(Cols, PD),
...

where the auxiliary predicate list_to_domain/2 is defined like:

list_to_domain([], 1..0).
list_to_domain([L|Ls], L \/ D) :-
list_to_domain(Ls, D).


And rewrite constraint_tuples/2 as:

constraint_tuples([], _).
constraint_tuples([Tuple| Tuples], Primes) :-
sum(Tuple, #=, Sum),
Sum in Primes,
constraint_tuples(Tuples, Primes).


You get a faster version:

%?- time(matrix_output(4)).
%@ 1, 2, 3, 5,
%@ 4, 6, 7, 12,
%@ 8, 9, 15, 11,
%@ 10, 14, 16, 13,
%@ % 47,966 inferences, 0.01 CPU in 0.01 seconds (67% CPU, 4796600 Lips)
%@ true.

%?- time(matrix_output(12)).
%@ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13,
%@ 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 26,
%@ 24, 25, 27, 28, 29, 30, 31, 32, 33, 34, 35, 39,
%@ 36, 37, 38, 40, 41, 42, 43, 44, 45, 46, 47, 50,
%@ 48, 49, 51, 52, 53, 54, 55, 56, 57, 58, 59, 61,
%@ 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72,
%@ 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 89,
%@ 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95,102,
%@ 96, 97, 98, 99,100,101,103,104,105,106,107,113,
%@ 108,109,110,111,112,114,115,116,117,118,119,124,
%@ 120,121,122,123,125,126,127,129,140,143,131,142,
%@ 135,134,133,139,141,132,144,138,137,128,130,136,
%@ % 5,068,426 inferences, 1.24 CPU in 1.27 seconds (97% CPU, 4087440 Lips)
%@ true.

And then it also makes sense to try different labeling options.

--
comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
.



Relevant Pages

  • Re: Prime Sums In A Grid
    ... considering also that the test for primality here is not ... You can use lists of lists in the first place and use append/2 to ... a generate-and-test approach, where sums are generated and then tested ... And in matrix/2 use: ...
    (comp.lang.prolog)
  • Re: Algorithms & work & testing for primality
    ... >of primality than the brute force approach of testing for divisibility ... >by all the primes smaller or equal to the square root of the number. ... If you have a candidate, c, that you're testing for primality, ...
    (sci.math)
  • Re: performance for testing n prime
    ... it is ever possible that PRIMES ... Most "efficient" tests for primality (not deciding what the factors are, ... So if you have an efficient program that can decide primality for all ... like that) then the basic methods are best. ...
    (comp.theory)
  • Re: 1.75 PRIMALITY DIVISOR , IS DESIGNED TO SELECT PRIME FROM NON PRIME IN THE 36SET SIEVE POSTED EA
    ... seems that this differentiates and we can build up the sets of primes ... primary sieve for primality, which may come. ... so why not use 7 as a primality divisor? ... a thorough primality test might consist ...
    (sci.math)
  • Re: Question
    ... Dik T. Winter wrote: ... one of your primes is quite small, did you try counting up from small ... I have a primality testing program here. ...
    (sci.math)