Status of mode directed tabling, especially min/max

Help!
24

As version 8.1.14 has arrived, I can now confirm that all the examples above - except euler14 - works as expected.

Thanks for the fix @jan .

1 Like
25

Looking at euler14.pl, we see

:- table max_chain(-,-,max).
max_chain(N,Chain,Len) :-
        between(2,999999,N),  % checking all numbers        
        % between(3,2,999999,N),  % just checking the odd numbers
        gen(N,Chain,Len).

Now, my docs tell me that - means keep the first answer and max keep the largest answer, which makes SWI-Prolog’s answer [2,525] correct. If you want to keep the witness that belongs to the max, the values must be combined. The following works:

euler14 :-
    max_chain(Max),
    Max = ch(N,_Chain,Len),
    writeln([n=N,len=Len]).

:- table max_chain(lattice(max)).
max_chain(ch(N,Chain,Len)) :-
        between(2,999999,N),
%       between(2,9,N),
        gen(N,Chain,Len).

max(Current, New, Max) :-
        arg(3, Current, Len1),
        arg(3, New, Len2),
        (   Len2 > Len1
        ->  Max = New
        ;   Max = Current
        ).

It is slow though (55 sec) and uses a lot of memory (13Gb), for a large part to store all the chains in the gen/3 tables. If you change that to gen/2 you get the result in 15 sec with 2,5Gb mem usage.

1 Like
26

Thanks @jan for the suggestions.

The version you copied in the reply give correct result now (and is slow: 33s on my fastest machine). That’s great.

However, you indicated that skipping the Chain argument was faster. It’s surely faster (~20s), but don’t give the correct result: it yield [n=3,len=8] instead of [n=837799,len=525]. Here’s my version of it. It’s kind of strange since Chain should be relevant, it’s only N and Len that is needed. Probably I’ve missed some important change…

euler14xxx :-
        abolish_all_tables,
        max_chain(Max),
        Max = ch(N,Len),
        writeln([n=N,len=Len]).

:- table max_chain(lattice(max)).
max_chain(ch(N,Len)) :-
        % between(3,2,999999,N),  % checking the odd numbers
        between(2,999999,N),  % checking all numbers
        gen(N,Len).

max(Current, New, Max) :-
        arg(3, Current, Len1),
        arg(3, New, Len2),
        (   Len2 > Len1
        ->  Max = New
        ;   Max = Current
        ).

:- table gen(+,-).
gen(1,Len) :-
        !, 
        Len = 1.
gen(N,Len) :-
        N > 1,
        N mod 2 =:= 0, %% !,
        Ndiv2 is N div 2,
        gen(Ndiv2,Len1),
        Len is Len1+1.
gen(N,Len) :-
        N > 1,
        N mod 2 =:= 1, %%  !,
        T3N1 is 3*N+1,
        gen(T3N1,Len1),
        Len is Len1+1.

It give the following result:

[n=3,len=8]
% 80,777,613 inferences, 18.757 CPU in 20.154 seconds (93% CPU, 4306438 Lips)

Do you have an idea where I did wrong?

(An aside: Skipping the Chain argument in my Picat version shaved the time from 1.2s to 0.7s which is quite significant. Thanks for the idea!)

27

This should (now) be arg(2, ... :slight_smile:

What I do not like about this is that if you want to get the chain you need to write both versions of gen, one to find the N with the longest chain and gen/3 to find the actual chain (I guess that is fine without tabling).

I also start to understand the discussion between what is called answer subsumption in XSB and mode directed tabling in B/Yap :slight_smile:

28

@jan Thanks! (And: Of course! :slight_smile:

This now takes 11.3s (from 34s),

For this specific problem we don’t really need the Chain itself, but I do see your point.

It will be interesting to follow further development of tabling.