Partition function P in Picat

Question

I got the following realization of the Partition function P
in Prolog, took it from rosetta here:

/* SWI-Prolog 8.3.21 */
:- table p/2.
p(0, 1) :- !.
p(N, X) :-
    aggregate_all(sum(Z), (between(1,inf,K), M is K*(3*K-1)//2,
           (M>N, !, fail; L is N-M, p(L,Y), Z is (-1)^K*Y)), A),
    aggregate_all(sum(Z), (between(1,inf,K), M is K*(3*K+1)//2,
           (M>N, !, fail; L is N-M, p(L,Y), Z is (-1)^K*Y)), B),
    X is -A-B.
 
?- time(p(6666,X)).
% 13,962,294 inferences, 2.610 CPU in 2.743 seconds (95% CPU, 5350059 Lips)
X = 1936553061617076610800050733944860919984809503384
05932486880600467114423441282418165863.

How would one go about an implementation of the same in Picat? Is it
true that aggregate_all+sum can be replaced by foreach+:= ?
What about bignums in Picat?

hakank · Accepted Answer · 2021-04-13T21:00:37.417

Bignums is no problem in Picat. Here's my Picat version (inspired by the Maple approach):

table
partition1(0) = 1.
partition1(N) = P =>
  S = 0,
  K = 1,
  M = (K*(3*K-1)) // 2,  
  while (M <= N)
     M := (K*(3*K-1)) // 2,  
     S := S - ((-1)**K)*partition1(N-M),
     K := K + 1
  end,
  K := 1,
  M := (K*(3*K+1)) // 2,
  while (M <= N)
     M := (K*(3*K+1)) // 2,  
     S := S - ((-1)**K)*partition1(N-M),
     K := K + 1
  end,
  P = S.

Your (neat) SWI-Prolog version takes about 1,9s for p(6666) on my machine.

?- time(p(6666,X)), write(X), nl.
% 13,959,720 inferences, 1.916 CPU in 1.916 seconds (100% CPU, 7285567 Lips)
193655306161707661080005073394486091998480950338405932486880600467114423441282418165863
X = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863.

My Picat version takes about 0.2s

Picat> time(println('p(6666)'=partition1(6666))) 
p(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863

CPU time 0.206 seconds.

Update Here's a version using findall in Picat instead, sort of mimicking your approach:

table
p(0, 1) :- !.
p(N, X) :-
    A = sum(findall(Z, (between(1,N,K), M is K*(3*K-1)//2,
           (M>N, !, fail; p(N-M,Y), Z is (-1)**K*Y)))),
    B = sum(findall(Z, (between(1,N,K), M is K*(3*K+1)//2,
           (M>N, !, fail; p(N-M,Y), Z is (-1)**K*Y)))),
    X is -A-B.

But it's much slower (2.6s vs 0.2s):

p(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863

CPU time 2.619 seconds. Backtracks: 0

I also tested to implement the same approach, i.e. using findall/3 in SWI-Prolog:

:- table p2/2.
p2(0, 1) :- !.
p2(N, X) :-
        findall(Z, (between(1,N,K), M is K*(3*K-1)//2,
                    (M>N, !, fail; L is N-M, p2(L,Y), Z is (-1)**K*Y)), AA),
        sum(AA,A),
        findall(Z, (between(1,N,K), M is K*(3*K+1)//2,
                    (M>N, !, fail; L is N-M, p2(L,Y), Z is (-1)**K*Y)), BB),
        sum(BB,B),
        X is - A - B.

sum(L,Sum) :-
        sum(L,0,Sum).
sum([],Sum,Sum).
sum([H|T],Sum0,Sum) :-
        Sum1 is Sum0 + H,
        sum(T,Sum1,Sum).

It's faster than Picat's findall approach, and about the same time as your version (slightly faster but with more inferences).

?- time(p2(6666,X)).
% 14,636,851 inferences, 1.814 CPU in 1.814 seconds (100% CPU, 8070412 Lips)
X = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863.

Yes, while is better for this algorithm instead of a foreach loop. I'll see if I can mirror your algorithm with foreach/1 or list comprehensions, — hakank, Apr 13 '21 at 18:49
Do you mean re-assignment in the while condition (i.e. `while (M := .... <= N)`? Nope, this is verboten, which is unfortunately since it would be neater here. — hakank, Apr 13 '21 at 18:56
Added your solution to rosetta, hope you're fine with that: https://rosettacode.org/wiki/Partition_function_P#Picat — , Apr 14 '21 at 10:14

score -1 · Answer 2 · 2021-04-14T00:57:02.157

I tried an automatic Picat style translation into some higher order loop construct. And then a manual inlining of the higher order loop construct. The input to the automatic Picat style translation was:

:- table p/2.
p(0)=1 => !.
p(N)=Z =>
    Z=0, K=1,
    M is K*(3*K-1)//2,
    while(M=<N,
        (Z:=Z-(-1)^K*p(N-M),
        K:=K+1,
        M:=K*(3*K-1)//2)),
    K:=1,
    M:=K*(3*K+1)//2,
    while(M=<N,
        (Z:=Z-(-1)^K*p(N-M),
         K:=K+1,
         M:=K*(3*K+1)//2)).

A link to the code of the translator is found at the end of this answer. The automatic translator gave me:

?- listing(p_a/2).
% example2.pl

:- sys_notrace p_a/2.
p_a(0, 1) :-
   !.
p_a(N, A) :-
   Z = 0,
   K = 1,
   M is K*(3*K-1)//2,
   while([B, C, D, E]\[F, C, G, H]\(G is D- -1^E*p(C-B),
      H is E+1,
      F is H*(3*H-1)//2), [I, J, _, _]\(I =< J), [M, N, Z,
      K], [_, N, L, _]),
   O is 1,
   P is O*(3*O+1)//2,
   while([Q, R, S, T]\[U, R, V, W]\(V is S- -1^T*p(R-Q),
      W is T+1,
      U is W*(3*W+1)//2), [X, Y, _, _]\(X =< Y), [P, N, L,
      O], [_, N, A, _]).

It uses arithmetic function evaluation p(C-B) and p(R-Q). In my Prolog system arithmetic function evaluation uses the native Java stack, and I cannot evaluate 6666:

% ?- p(100,X).
% X = 190569292

% ?- p(6666,X).
% java.lang.StackOverflowError
%   at jekpro.reference.arithmetic.EvaluableElem.moniEvaluate(EvaluableElem.java:207)

Also the use of while/4 meta predicate is a little slow. So I massaged the code, eliminate the arithmetic function evaluation and inlined while/4. I also used a poor mans tabling, which is a little faster:

:- thread_local p_cache/2.

p_manual(N, X) :- p_cache(N, X), !.
p_manual(0, 1) :-
   !, assertz(p_cache(0, 1)).
p_manual(N, A) :-
   Z = 0,
   K = 1,
   M is K*(3*K-1)//2,
   p21([M, N, Z, K], [_, N, L, _]),
   O is 1,
   P is O*(3*O+1)//2,
   p22([P, N, L, O], [_, N, A, _]),
   assertz(p_cache(N, A)).

p21([B, C, D, E], O1) :- B =< C, !,
   L is C-B,
   p_manual(L, M),
   G is D- -1^E*M,
   H is E+1,
   F is H*(3*H-1)//2,
   p21([F, C, G, H], O1).
p21(I1, I1).

p22([Q, R, S, T], O2) :- Q =< R, !,
   L is R-Q,
   p_manual(L, M),
   V is S- -1^T*M,
   W is T+1,
   U is W*(3*W+1)//2,
   p22([U, R, V, W], O2).
p22(I2, I2).

Now things started looking good. The 2.743 seconds went down to:

/* SWI-Prolog 8.3.21 */
?- time(p_manual(6666,X)).
% 4,155,198 inferences, 0.879 CPU in 0.896 seconds (98% CPU, 4729254 Lips)
X = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863.

/* Jekejeke Prolog 1.5.0 */
?- time(p_manual(6666,X)).
% Up 736 ms, GC 20 ms, Threads 714 ms (Current 04/14/21 02:16:45)
X = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863

Open source:

Picat Style Scripting Translator II
https://gist.github.com/jburse/8a24fe5668960c8889770f40c65cdf35#file-picat2-pl

Picat Style Scripting Examples II
https://gist.github.com/jburse/8a24fe5668960c8889770f40c65cdf35#file-example2-pl

Picat Style Scripting Inlined
https://gist.github.com/jburse/8a24fe5668960c8889770f40c65cdf35#file-tune-pl

Partition function P in Picat

2 Answers2