Picat中的配分函数P

Question

我得到了分区函数P的如下实现

在Prolog中，它是从rosetta 这里那里得到的

/* 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.

人们将如何在Picat中实现同样的目标？是吗

真的aggregate_all+sum可以被foreach+:=取代吗？

皮卡特的大教堂呢？

Answer 1

Bignum在Picat是没有问题的。这里是我的Picat版本(受枫树方法的启发)：

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.

您的(整洁的)SWI版本对于我的计算机上的p(6666)大约需要1,9s。

?- 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.

我的Picat版本大约需要0.2s

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

CPU time 0.206 seconds.

Update这里有一个在Picat中使用findall的版本，类似于您的方法：

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.

但速度要慢得多(2.6s对0.2s)：

p(6666) = 193655306161707661080005073394486091998480950338405932486880600467114423441282418165863

CPU time 2.619 seconds. Backtracks: 0

我还测试了实现相同的方法，即在SWI中使用findall/3：

:- 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).

它比Picat的findall方法更快，并且和您的版本差不多(稍微快一些，但有更多的推论)。

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

Answer 2

我尝试了一个自动的Picat风格的转换成一些更高的循环结构。然后是一个高级循环构造的手动内联。自动Picat风格翻译的输入如下：

:- 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)).

在这个答案的末尾找到了一个到翻译代码的链接。自动翻译给我：

?- 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, _]).

它采用算术函数求值p(C)和p(R).在我的Prolog系统中，算术函数计算使用本机Java堆栈，我无法计算6666：

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

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

同时，while/4元谓词的使用也有点慢。因此，我修改了代码，消除了算术函数的求值，并在/4中内联了。

:- 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).

现在一切都好起来了。2.743秒下降到：

/* 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

开放来源：

Picat风格脚本转换器II

https://gist.github.com/jburse/8a24fe5668960c8889770f40c65cdf35#file-picat2-pl

Picat样式脚本示例II

https://gist.github.com/jburse/8a24fe5668960c8889770f40c65cdf35#file-example2-pl

Picat样式脚本内联

https://gist.github.com/jburse/8a24fe5668960c8889770f40c65cdf35#file-tune-pl