1. Forum
  2. Usenet
  3. COMP.LANG.PROLOG

  • Re: Autum Challenge, 42 is the Answer

    From Mostowski Collapse@21:1/5 to Mostowski Collapse on Wed Aug 31 07:23:52 2022
    Any progress during Corona?

    Can this be solved via ZZD and the axiom of extensionality?
    Or maybe the new CLP(Z) from Scryer Prolog can do it?

    Or are we in the mist of Hilbert’s 10-th problem. Maybe Poincaré
    would have objected we simply need new problem specific rules?

    Mostowski Collapse schrieb am Montag, 16. September 2019 um 21:49:35 UTC+2:
    Find x, y, z such that:

    x^3 + y^3 + z^3 = 42

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mostowski Collapse@21:1/5 to Mostowski Collapse on Fri Sep 9 10:42:51 2022
    Does SWI-Prolog have modpow/4, a function popular in cryptography?
    Isn’t this already in GMP, so that a verify fast implementation
    would be available?

    modpow(B, E, M, R):
    The predicate succeeds in R with B^E mod M.

    I guess we have also:

    (modpow(X,3,M)+modpow(Y,3,M)+42 mod M) mod M =:= modpow(Z,3,M)

    But not sure whether this will lead to anywhere. From Fermats
    Last Theorem we know, whenever 42 mod M is zero, we
    don’t have a non-trivial tripple (X,Y,Z) anyway.

    Mostowski Collapse schrieb am Mittwoch, 31. August 2022 um 16:23:54 UTC+2:
    Any progress during Corona?

    Can this be solved via ZZD and the axiom of extensionality?
    Or maybe the new CLP(Z) from Scryer Prolog can do it?

    Or are we in the mist of Hilbert’s 10-th problem. Maybe Poincaré
    would have objected we simply need new problem specific rules?
    Mostowski Collapse schrieb am Montag, 16. September 2019 um 21:49:35 UTC+2:
    Find x, y, z such that:

    x^3 + y^3 + z^3 = 42

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mostowski Collapse@21:1/5 to Mostowski Collapse on Fri Sep 9 11:30:23 2022
    No was talking nonsense, FLT doesn’t exclude non-trivial solutions. For example we have this solution modulo 6, where it is 42 module 6 = 0:

    1^3 + 1^3 + 42 = 2^3 (mod 6)

    Mostowski Collapse schrieb am Freitag, 9. September 2022 um 19:42:52 UTC+2:
    Does SWI-Prolog have modpow/4, a function popular in cryptography?
    Isn’t this already in GMP, so that a verify fast implementation
    would be available?

    modpow(B, E, M, R):
    The predicate succeeds in R with B^E mod M.

    I guess we have also:

    (modpow(X,3,M)+modpow(Y,3,M)+42 mod M) mod M =:= modpow(Z,3,M)

    But not sure whether this will lead to anywhere. From Fermats
    Last Theorem we know, whenever 42 mod M is zero, we
    don’t have a non-trivial tripple (X,Y,Z) anyway.
    Mostowski Collapse schrieb am Mittwoch, 31. August 2022 um 16:23:54 UTC+2:
    Any progress during Corona?

    Can this be solved via ZZD and the axiom of extensionality?
    Or maybe the new CLP(Z) from Scryer Prolog can do it?

    Or are we in the mist of Hilbert’s 10-th problem. Maybe Poincaré
    would have objected we simply need new problem specific rules?
    Mostowski Collapse schrieb am Montag, 16. September 2019 um 21:49:35 UTC+2:
    Find x, y, z such that:

    x^3 + y^3 + z^3 = 42

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mostowski Collapse@21:1/5 to All on Tue Sep 20 05:07:46 2022
    Furtther question, does SWI-Prolog have modinv/3, also a function popular
    in cryptography? It can be used for a Chinese Remainder algorithm.

    But currently banging my head on a slow (^)/2 for smallints. In modular algorithms the arguments for (^)/2 are small. So I now get:

    /* SWI-Prolog 8.5.17 */
    ?- time((modular([11,7,5], X, Y, Z), fail; true)).
    % 15,388,917 inferences, 3.969 CPU in 3.963 seconds (100% CPU, 3877522 Lips) true.

    /* Jekejeke Prolog 1.5.4 */
    ?- time((modular([11,7,5], X, Y, Z), fail; true)).
    % Threads 2,078 ms, GC 10 ms, Up 2,122 ms (Current 09/20/22 11:03:10)
    true.

    But I only solved this k=9 equation, not yet the k=42 problem:

    /* x^3 + y^3 + 9 = z^3 */
    ?- modular([11,7,5], X, Y, Z).
    X = 216,
    Y = 52,
    Z = 217 ;
    X = 52,
    Y = 216,
    Z = 217 ;
    false.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mostowski Collapse@21:1/5 to Mostowski Collapse on Tue Sep 20 11:28:32 2022
    Using modular operations again, you can make it a tick faster by using
    only two modules instead of three modules. But it still depends
    heavily on the performance of ar_pow():

    /* SWI-Prolog 8.5.17 */
    ?- time((modular([15,16], X, Y, Z), fail; true)).
    % 3,816,486 inferences, 1.766 CPU in 1.762 seconds (100% CPU, 2161550 Lips) true.

    /* Jekejeke Prolog 1.5.4 */
    ?- modular([15,16], X, Y, Z).
    X = 216, Y = 52, Z = 217;
    X = 52, Y = 216, Z = 217;
    fail.

    ?- time((modular([15,16], X, Y, Z), fail; true)).
    % Threads 594 ms, GC 5 ms, Up 591 ms (Current 09/20/22 20:21:30)
    true.

    Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 14:07:47 UTC+2:
    Furtther question, does SWI-Prolog have modinv/3, also a function popular
    in cryptography? It can be used for a Chinese Remainder algorithm.

    But currently banging my head on a slow (^)/2 for smallints. In modular algorithms the arguments for (^)/2 are small. So I now get:

    /* SWI-Prolog 8.5.17 */
    ?- time((modular([11,7,5], X, Y, Z), fail; true)).
    % 15,388,917 inferences, 3.969 CPU in 3.963 seconds (100% CPU, 3877522 Lips) true.

    /* Jekejeke Prolog 1.5.4 */
    ?- time((modular([11,7,5], X, Y, Z), fail; true)).
    % Threads 2,078 ms, GC 10 ms, Up 2,122 ms (Current 09/20/22 11:03:10)
    true.

    But I only solved this k=9 equation, not yet the k=42 problem:

    /* x^3 + y^3 + 9 = z^3 */
    ?- modular([11,7,5], X, Y, Z).
    X = 216,
    Y = 52,
    Z = 217 ;
    X = 52,
    Y = 216,
    Z = 217 ;
    false.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mostowski Collapse@21:1/5 to Mostowski Collapse on Tue Sep 20 12:13:19 2022
    Thats the performance of traditional CLP(FD) and CLP(Z)
    for this kind of problem:

    /* SWI-Prolog CLP(FD) */
    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]), fail; true)).
    % 36,572,338 inferences, 5.109 CPU in 5.117 seconds (100% CPU, 7157889 Lips) true.

    /* Scryer Prolog CLP(Z) */
    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]), fail; true)).
    % CPU time: 75.667s
    true.

    Wasnt using any bisection or somesuch option. Just the
    defaults of CLP(FD) and CLP(Z).

    Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 20:58:47 UTC+2:
    (Credits for the acronym cra for Chinese Remainder Algorithm in the
    context of Prolog go to Amzi! Prolog, I found the acronym here: https://amzi.com/manuals/amzi/pro/ref_math.htm )
    Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 20:30:40 UTC+2:
    Thats the source code, it is ultimately intended to beat CLP(Z)
    from Scryer Prolog some time in the future into dust, it also uses ar_pow(), maybe better would be ar_modpow(), but for the small

    values ar_modpow() wouldn't give some bang:

    modular([P|L], X, Y, Z) :-
    find(P, A, B, C),
    many(L, A-P, B-P, C-P, X-_, Y-_, Z-_),
    X^3+Y^3+9-Z^3 =:= 0.

    many([], A, B, C, A, B, C).
    many([P|L], U, V, W, A, B, C) :-
    find(P, X, Y, Z),
    cra_combine(X-P, U, S),
    cra_combine(Y-P, V, T),
    cra_combine(Z-P, W, R),
    many(L, S, T, R, A, B, C).

    find(M, X, Y, Z) :-
    N is M-1,
    between(0, N, X), A is X^3,
    between(0, N, Y), B is Y^3,
    between(0, N, Z),
    (A+B+9-Z^3) mod M =:= 0.

    /**
    * Chinese Remainder Algorithm
    * https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Existence_%28constructive_proof%29
    */
    % cra_combine(+Pair, +Pair, -Pair)
    cra_combine(A-N, B-M, C-P) :-
    cra_egcd(N, M, X, Y),
    P is N*M,
    C is (A*M*Y+B*N*X) mod P.

    % cra_egcd(+Integer, +Integer, -Integer, -Integer)
    cra_egcd(_, 0, 1, 0) :- !.
    cra_egcd(A, B, X, Y) :-
    divmod(A, B, Q, R),
    cra_egcd(B, R, S, X),
    Y is S - Q*X.
    Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 20:28:33 UTC+2:
    Using modular operations again, you can make it a tick faster by using only two modules instead of three modules. But it still depends
    heavily on the performance of ar_pow():

    /* SWI-Prolog 8.5.17 */
    ?- time((modular([15,16], X, Y, Z), fail; true)).
    % 3,816,486 inferences, 1.766 CPU in 1.762 seconds (100% CPU, 2161550 Lips)
    true.

    /* Jekejeke Prolog 1.5.4 */
    ?- modular([15,16], X, Y, Z).
    X = 216, Y = 52, Z = 217;
    X = 52, Y = 216, Z = 217;
    fail.

    ?- time((modular([15,16], X, Y, Z), fail; true)).
    % Threads 594 ms, GC 5 ms, Up 591 ms (Current 09/20/22 20:21:30)
    true.
    Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 14:07:47 UTC+2:
    Furtther question, does SWI-Prolog have modinv/3, also a function popular
    in cryptography? It can be used for a Chinese Remainder algorithm.

    But currently banging my head on a slow (^)/2 for smallints. In modular algorithms the arguments for (^)/2 are small. So I now get:

    /* SWI-Prolog 8.5.17 */
    ?- time((modular([11,7,5], X, Y, Z), fail; true)).
    % 15,388,917 inferences, 3.969 CPU in 3.963 seconds (100% CPU, 3877522 Lips)
    true.

    /* Jekejeke Prolog 1.5.4 */
    ?- time((modular([11,7,5], X, Y, Z), fail; true)).
    % Threads 2,078 ms, GC 10 ms, Up 2,122 ms (Current 09/20/22 11:03:10) true.

    But I only solved this k=9 equation, not yet the k=42 problem:

    /* x^3 + y^3 + 9 = z^3 */
    ?- modular([11,7,5], X, Y, Z).
    X = 216,
    Y = 52,
    Z = 217 ;
    X = 52,
    Y = 216,
    Z = 217 ;
    false.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mostowski Collapse@21:1/5 to Mostowski Collapse on Tue Sep 20 11:58:44 2022
    (Credits for the acronym cra for Chinese Remainder Algorithm in the
    context of Prolog go to Amzi! Prolog, I found the acronym here: https://amzi.com/manuals/amzi/pro/ref_math.htm )

    Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 20:30:40 UTC+2:
    Thats the source code, it is ultimately intended to beat CLP(Z)
    from Scryer Prolog some time in the future into dust, it also uses
    ar_pow(), maybe better would be ar_modpow(), but for the small

    values ar_modpow() wouldn't give some bang:

    modular([P|L], X, Y, Z) :-
    find(P, A, B, C),
    many(L, A-P, B-P, C-P, X-_, Y-_, Z-_),
    X^3+Y^3+9-Z^3 =:= 0.

    many([], A, B, C, A, B, C).
    many([P|L], U, V, W, A, B, C) :-
    find(P, X, Y, Z),
    cra_combine(X-P, U, S),
    cra_combine(Y-P, V, T),
    cra_combine(Z-P, W, R),
    many(L, S, T, R, A, B, C).

    find(M, X, Y, Z) :-
    N is M-1,
    between(0, N, X), A is X^3,
    between(0, N, Y), B is Y^3,
    between(0, N, Z),
    (A+B+9-Z^3) mod M =:= 0.

    /**
    * Chinese Remainder Algorithm
    * https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Existence_%28constructive_proof%29
    */
    % cra_combine(+Pair, +Pair, -Pair)
    cra_combine(A-N, B-M, C-P) :-
    cra_egcd(N, M, X, Y),
    P is N*M,
    C is (A*M*Y+B*N*X) mod P.

    % cra_egcd(+Integer, +Integer, -Integer, -Integer)
    cra_egcd(_, 0, 1, 0) :- !.
    cra_egcd(A, B, X, Y) :-
    divmod(A, B, Q, R),
    cra_egcd(B, R, S, X),
    Y is S - Q*X.
    Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 20:28:33 UTC+2:
    Using modular operations again, you can make it a tick faster by using
    only two modules instead of three modules. But it still depends
    heavily on the performance of ar_pow():

    /* SWI-Prolog 8.5.17 */
    ?- time((modular([15,16], X, Y, Z), fail; true)).
    % 3,816,486 inferences, 1.766 CPU in 1.762 seconds (100% CPU, 2161550 Lips) true.

    /* Jekejeke Prolog 1.5.4 */
    ?- modular([15,16], X, Y, Z).
    X = 216, Y = 52, Z = 217;
    X = 52, Y = 216, Z = 217;
    fail.

    ?- time((modular([15,16], X, Y, Z), fail; true)).
    % Threads 594 ms, GC 5 ms, Up 591 ms (Current 09/20/22 20:21:30)
    true.
    Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 14:07:47 UTC+2:
    Furtther question, does SWI-Prolog have modinv/3, also a function popular in cryptography? It can be used for a Chinese Remainder algorithm.

    But currently banging my head on a slow (^)/2 for smallints. In modular algorithms the arguments for (^)/2 are small. So I now get:

    /* SWI-Prolog 8.5.17 */
    ?- time((modular([11,7,5], X, Y, Z), fail; true)).
    % 15,388,917 inferences, 3.969 CPU in 3.963 seconds (100% CPU, 3877522 Lips)
    true.

    /* Jekejeke Prolog 1.5.4 */
    ?- time((modular([11,7,5], X, Y, Z), fail; true)).
    % Threads 2,078 ms, GC 10 ms, Up 2,122 ms (Current 09/20/22 11:03:10) true.

    But I only solved this k=9 equation, not yet the k=42 problem:

    /* x^3 + y^3 + 9 = z^3 */
    ?- modular([11,7,5], X, Y, Z).
    X = 216,
    Y = 52,
    Z = 217 ;
    X = 52,
    Y = 216,
    Z = 217 ;
    false.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mostowski Collapse@21:1/5 to Mostowski Collapse on Tue Sep 20 11:30:38 2022
    Thats the source code, it is ultimately intended to beat CLP(Z)
    from Scryer Prolog some time in the future into dust, it also uses
    ar_pow(), maybe better would be ar_modpow(), but for the small

    values ar_modpow() wouldn't give some bang:

    modular([P|L], X, Y, Z) :-
    find(P, A, B, C),
    many(L, A-P, B-P, C-P, X-_, Y-_, Z-_),
    X^3+Y^3+9-Z^3 =:= 0.

    many([], A, B, C, A, B, C).
    many([P|L], U, V, W, A, B, C) :-
    find(P, X, Y, Z),
    cra_combine(X-P, U, S),
    cra_combine(Y-P, V, T),
    cra_combine(Z-P, W, R),
    many(L, S, T, R, A, B, C).

    find(M, X, Y, Z) :-
    N is M-1,
    between(0, N, X), A is X^3,
    between(0, N, Y), B is Y^3,
    between(0, N, Z),
    (A+B+9-Z^3) mod M =:= 0.

    /**
    * Chinese Remainder Algorithm
    * https://en.wikipedia.org/wiki/Chinese_remainder_theorem#Existence_%28constructive_proof%29
    */
    % cra_combine(+Pair, +Pair, -Pair)
    cra_combine(A-N, B-M, C-P) :-
    cra_egcd(N, M, X, Y),
    P is N*M,
    C is (A*M*Y+B*N*X) mod P.

    % cra_egcd(+Integer, +Integer, -Integer, -Integer)
    cra_egcd(_, 0, 1, 0) :- !.
    cra_egcd(A, B, X, Y) :-
    divmod(A, B, Q, R),
    cra_egcd(B, R, S, X),
    Y is S - Q*X.

    Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 20:28:33 UTC+2:
    Using modular operations again, you can make it a tick faster by using
    only two modules instead of three modules. But it still depends
    heavily on the performance of ar_pow():

    /* SWI-Prolog 8.5.17 */
    ?- time((modular([15,16], X, Y, Z), fail; true)).
    % 3,816,486 inferences, 1.766 CPU in 1.762 seconds (100% CPU, 2161550 Lips) true.

    /* Jekejeke Prolog 1.5.4 */
    ?- modular([15,16], X, Y, Z).
    X = 216, Y = 52, Z = 217;
    X = 52, Y = 216, Z = 217;
    fail.

    ?- time((modular([15,16], X, Y, Z), fail; true)).
    % Threads 594 ms, GC 5 ms, Up 591 ms (Current 09/20/22 20:21:30)
    true.
    Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 14:07:47 UTC+2:
    Furtther question, does SWI-Prolog have modinv/3, also a function popular in cryptography? It can be used for a Chinese Remainder algorithm.

    But currently banging my head on a slow (^)/2 for smallints. In modular algorithms the arguments for (^)/2 are small. So I now get:

    /* SWI-Prolog 8.5.17 */
    ?- time((modular([11,7,5], X, Y, Z), fail; true)).
    % 15,388,917 inferences, 3.969 CPU in 3.963 seconds (100% CPU, 3877522 Lips)
    true.

    /* Jekejeke Prolog 1.5.4 */
    ?- time((modular([11,7,5], X, Y, Z), fail; true)).
    % Threads 2,078 ms, GC 10 ms, Up 2,122 ms (Current 09/20/22 11:03:10)
    true.

    But I only solved this k=9 equation, not yet the k=42 problem:

    /* x^3 + y^3 + 9 = z^3 */
    ?- modular([11,7,5], X, Y, Z).
    X = 216,
    Y = 52,
    Z = 217 ;
    X = 52,
    Y = 216,
    Z = 217 ;
    false.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mostowski Collapse@21:1/5 to Mostowski Collapse on Tue Sep 20 17:49:54 2022
    Even Dogelog player is speedier than CLP(FD) and CLP(Z),
    using the modular approach. I find:

    ?- modular([15,16], X, Y, Z).
    X = 216, Y = 52, Z = 217;
    X = 52, Y = 216, Z = 217;
    fail.

    ?- time((modular([15,16], X, Y, Z), fail; true)).
    % Wall 3925 ms, gc 7 ms, 1544404 lips
    true.

    https://jsfiddle.net/Jean_Luc_Picard_2021/d2njehtp/3/

    I don't have divmod/4 yet, so one needs to use the
    following variant of Extended GCD:

    cra_egcd(A, B, X, Y) :-
    Q is A div B,
    R is A mod B,
    % divmod(A, B, Q, R),
    cra_egcd(B, R, S, X),
    Y is S - Q*X.

    Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 21:13:20 UTC+2:
    Thats the performance of traditional CLP(FD) and CLP(Z)
    for this kind of problem:

    /* SWI-Prolog CLP(FD) */
    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]), fail; true)). % 36,572,338 inferences, 5.109 CPU in 5.117 seconds (100% CPU, 7157889 Lips) true.

    /* Scryer Prolog CLP(Z) */
    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]), fail; true)). % CPU time: 75.667s
    true.

    Wasnt using any bisection or somesuch option. Just the
    defaults of CLP(FD) and CLP(Z).

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Markus Triska@21:1/5 to Mostowski Collapse on Thu Aug 31 21:26:55 2023
    Mostowski Collapse <bursejan@gmail.com> writes:

    /* Scryer Prolog CLP(Z) */
    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]), fail; true)).
    % CPU time: 75.667s
    true.

    With the newly release Scryer Prolog version 0.9.2, I now get:

    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]), fail; true)).
    % CPU time: 41.658s
    true.

    On my machine, that's within a factor of 6 of SWI. That's quite
    comparable to many other applications when it comes to time performance:
    At the current state of Scryer Prolog development, its performance tends
    to be within an order of magnitude of SWI's.

    One neat feature of the Scryer Prolog toplevel is that we can press "a"
    to obtain *all* solutions, one after the other. In this case:

    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]))).
    % CPU time: 16.080s
    X = 52, Y = 216, Z = 217
    ; % CPU time: 25.942s
    X = 216, Y = 52, Z = 217
    ; % CPU time: 0.250s
    false.

    It's often nice to get the Prolog system to enumerate all solutions automatically. The GNU Prolog toplevel also has this feature, and I
    highly recommend adding it in system where it is not yet available.

    All the best,
    Markus

    --
    comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
    The Power of Prolog: https://www.metalevel.at/prolog

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mild Shock@21:1/5 to Mostowski Collapse on Fri Sep 1 11:47:04 2023
    One motivation to look at the problem, and to look at the
    easier problem with 9 instead 42, is to elaborate a completely
    new CLP(FD) solver, that is based on Chinese Remainder Theorem.

    Actually I have already a prototype working, the timing was
    also already published around 12 months ago. My system was much
    faster than SWI-Prolog, since SWI-Prolog is slow with smallints and (^)/2:

    Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 20:28:33 UTC+2:
    /* Jekejeke Prolog 1.5.4 */
    ?- modular([15,16], X, Y, Z).
    X = 216, Y = 52, Z = 217;
    X = 52, Y = 216, Z = 217;
    fail.

    ?- time((modular([15,16], X, Y, Z), fail; true)).
    % Threads 594 ms, GC 5 ms, Up 591 ms (Current 09/20/22 20:21:30)
    true.
    https://groups.google.com/g/comp.lang.prolog/c/mjpxkE3xVYk/m/cn0FICAQAAAJ

    So these 594 ms are 10x times faster than the 5.117 seconds from
    SWI-Prolog using ordinary CLP(FD). And around 100x times faster than
    the 41.658s from Scryer Prolog. But I didn't yet publish this new

    CLP(FD) solver, maybe I did some blogging and also some code
    went into comp.lang.prolog here, but its not currently some officially
    released module somewhere. Its also a solver which isn't based on

    attributed variables per se. It requires that the constraint store is re-evaluated with different moduli, so I envision something totally
    new, that drops attributed variables, but nevertheless has a constraint

    store. Attributed variables have become less important. The dis-
    advantage of not having attributed variables would be that the
    constraints cannot be used on ordinary predicates. I have no solution

    for the later problem yet, but the figures in the former testing show,
    that the method can be much much faster than ordinary CLP(FD).

    Markus Triska schrieb am Donnerstag, 31. August 2023 um 21:20:14 UTC+2:
    Mostowski Collapse <burs...@gmail.com> writes:

    /* Scryer Prolog CLP(Z) */
    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]), fail; true)).
    % CPU time: 75.667s
    true.

    With the newly release Scryer Prolog version 0.9.2, I now get:
    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]), fail; true)). % CPU time: 41.658s
    true.

    On my machine, that's within a factor of 6 of SWI. That's quite
    comparable to many other applications when it comes to time performance:
    At the current state of Scryer Prolog development, its performance tends
    to be within an order of magnitude of SWI's.

    One neat feature of the Scryer Prolog toplevel is that we can press "a"
    to obtain *all* solutions, one after the other. In this case:

    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]))).
    % CPU time: 16.080s
    X = 52, Y = 216, Z = 217
    ; % CPU time: 25.942s
    X = 216, Y = 52, Z = 217
    ; % CPU time: 0.250s
    false.

    It's often nice to get the Prolog system to enumerate all solutions automatically. The GNU Prolog toplevel also has this feature, and I
    highly recommend adding it in system where it is not yet available.

    All the best,
    Markus

    --
    comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
    The Power of Prolog: https://www.metalevel.at/prolog

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mild Shock@21:1/5 to Mild Shock on Fri Sep 1 14:38:53 2023
    Actually its not that dim, one could integrate the Chinese
    Reminder Algorithm (CRA) strategy into a CLP(FD) constraint
    solver via a labeling variant. The labeling would

    include not only running through values inside the current
    modulo M, i.e. choosing values in the range 0..M-1, but also
    choosing different moduli M1, .., Mk. But the question is

    whether one should do that. The problem is that the solution
    is obtained by backtracking over all moduli. So when E is the
    equation, then its basically a large conjunction:

    E_M1, ..., E_Mk

    Where each element of the conjunction produces some bits,
    and these bits are then combined via CRA. Currently when
    E_Mj is a predicate, the equation sits in this predicate,

    and each element of the conjunctions runs instances of
    the clauses of the predicate, thus has a copy of the equation
    available. This copying of the equation makes me think

    that attribute variables don't work. But alternatively one
    could also table the results of each E_Mj, and later do the
    CRA combination. My current solution is not like that,

    but this could have more affinity to attributed variables.

    Mild Shock schrieb am Freitag, 1. September 2023 um 20:47:06 UTC+2:
    One motivation to look at the problem, and to look at the
    easier problem with 9 instead 42, is to elaborate a completely
    new CLP(FD) solver, that is based on Chinese Remainder Theorem.

    Actually I have already a prototype working, the timing was
    also already published around 12 months ago. My system was much
    faster than SWI-Prolog, since SWI-Prolog is slow with smallints and (^)/2: Mostowski Collapse schrieb am Dienstag, 20. September 2022 um 20:28:33 UTC+2:
    /* Jekejeke Prolog 1.5.4 */
    ?- modular([15,16], X, Y, Z).
    X = 216, Y = 52, Z = 217;
    X = 52, Y = 216, Z = 217;
    fail.

    ?- time((modular([15,16], X, Y, Z), fail; true)).
    % Threads 594 ms, GC 5 ms, Up 591 ms (Current 09/20/22 20:21:30)
    true.
    https://groups.google.com/g/comp.lang.prolog/c/mjpxkE3xVYk/m/cn0FICAQAAAJ

    So these 594 ms are 10x times faster than the 5.117 seconds from
    SWI-Prolog using ordinary CLP(FD). And around 100x times faster than
    the 41.658s from Scryer Prolog. But I didn't yet publish this new

    CLP(FD) solver, maybe I did some blogging and also some code
    went into comp.lang.prolog here, but its not currently some officially released module somewhere. Its also a solver which isn't based on

    attributed variables per se. It requires that the constraint store is re-evaluated with different moduli, so I envision something totally
    new, that drops attributed variables, but nevertheless has a constraint

    store. Attributed variables have become less important. The dis-
    advantage of not having attributed variables would be that the
    constraints cannot be used on ordinary predicates. I have no solution

    for the later problem yet, but the figures in the former testing show,
    that the method can be much much faster than ordinary CLP(FD).
    Markus Triska schrieb am Donnerstag, 31. August 2023 um 21:20:14 UTC+2:
    Mostowski Collapse <burs...@gmail.com> writes:

    /* Scryer Prolog CLP(Z) */
    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]), fail; true)).
    % CPU time: 75.667s
    true.

    With the newly release Scryer Prolog version 0.9.2, I now get:
    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]), fail; true)).
    % CPU time: 41.658s
    true.

    On my machine, that's within a factor of 6 of SWI. That's quite
    comparable to many other applications when it comes to time performance:
    At the current state of Scryer Prolog development, its performance tends
    to be within an order of magnitude of SWI's.

    One neat feature of the Scryer Prolog toplevel is that we can press "a"
    to obtain *all* solutions, one after the other. In this case:

    ?- time(([X,Y,Z] ins 0..239, X^3+Y^3+9 #= Z^3, label([X,Y,Z]))).
    % CPU time: 16.080s
    X = 52, Y = 216, Z = 217
    ; % CPU time: 25.942s
    X = 216, Y = 52, Z = 217
    ; % CPU time: 0.250s
    false.

    It's often nice to get the Prolog system to enumerate all solutions automatically. The GNU Prolog toplevel also has this feature, and I
    highly recommend adding it in system where it is not yet available.

    All the best,
    Markus

    --
    comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
    The Power of Prolog: https://www.metalevel.at/prolog

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mild Shock@21:1/5 to All on Mon Sep 4 04:31:27 2023
    Whats the Scryer Performance of this Example?

    /* GNU Prolog 1.5.0 */
    ?- between(1,200,N), length(L,N), nth_member(I,L,E), fail; true.
    (94 ms) yes

    /* SWI-Prolog 9.1.14 */
    ?- time((between(1,200,N), length(L,N), nth_member(I,L,E), fail; true)).
    % 94,504,524 inferences, 4.766 CPU in 4.767 seconds (100% CPU, 19830457 Lips) true.

    That was measured on my machine,
    and was a factor ca. 50x slower in SWI-Prolog.

    Source Code:

    nth_member(1, [M|_], M).
    nth_member(N, [_|T], M) :-
    N #> 1, N1 #= N - 1,
    nth_member(N1, T, M).

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Markus Triska@21:1/5 to Mild Shock on Mon Sep 4 19:48:55 2023
    Mild Shock <bursejan@gmail.com> writes:

    Whats the Scryer Performance of this Example?

    /* GNU Prolog 1.5.0 */
    ?- between(1,200,N), length(L,N), nth_member(I,L,E), fail; true.
    (94 ms) yes

    /* SWI-Prolog 9.1.14 */
    ?- time((between(1,200,N), length(L,N), nth_member(I,L,E), fail; true)).
    % 94,504,524 inferences, 4.766 CPU in 4.767 seconds (100% CPU, 19830457 Lips) true.

    With Scryer Prolog 0.9.2 on my machine, I get:

    ?- time((between(1,200,N), length(L,N), nth_member(I,L,E), false; true)).
    % CPU time: 84.182s
    true.

    On my machine, that's ca. 15 times slower than SWI 8.3.15, which is the
    last SWI version I found installed on this machine. Newer versions may
    well be faster! For best performance, I recommend to build Scryer Prolog
    with the optional --release flag, i.e.:

    $ cargo build --release

    All the best,
    Markus

    --
    comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
    The Power of Prolog: https://www.metalevel.at/prolog

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mild Shock@21:1/5 to Markus Triska on Mon Sep 4 12:46:16 2023
    I am also slower than SWI-Prolog with formerly Jekejeke Prolog,
    but sandwhich between Scryer Prolog and SWI-Prolog for this example.
    I never know whether my CLP(FD) still works, so first some sanity checks:

    ?- nth_member(X, [5,4,6], 4).
    X = 2;
    fail.
    ?- nth_member(2, [5,4,6], X).
    X = 4;
    fail.

    Then the benchmark results:

    ?- time((between(1,200,N), length(L,N), nth_member(I,L,E), fail; true)).
    % Time 48513 ms, GC 373 ms, Wall 04/09/2023 21:41
    true.

    But I don't know whether its comparable with Scryer Prolog since
    I didn't test Scryer Prolog, and the Scryer Prolog figures are from
    Markus Triskas machine.

    I am currently phasing out formerly Jekejeke Prolog. It should receive
    the same core as Dogelog Player. And then maybe can also re-add
    CLP(FD) and see what happens. But this might take months. Especially

    since I want to reinvent CLP(FD), adding some CRA Strategy, and I
    don't know yet eactly how to do it. I could optimized the non-labeling behaviour exactly towards this test case, where GNU Prolog performs well.

    Markus Triska schrieb am Montag, 4. September 2023 um 19:42:01 UTC+2:
    Mild Shock <burs...@gmail.com> writes:

    Whats the Scryer Performance of this Example?

    /* GNU Prolog 1.5.0 */
    ?- between(1,200,N), length(L,N), nth_member(I,L,E), fail; true.
    (94 ms) yes

    /* SWI-Prolog 9.1.14 */
    ?- time((between(1,200,N), length(L,N), nth_member(I,L,E), fail; true)).
    % 94,504,524 inferences, 4.766 CPU in 4.767 seconds (100% CPU, 19830457 Lips)
    true.
    With Scryer Prolog 0.9.2 on my machine, I get:

    ?- time((between(1,200,N), length(L,N), nth_member(I,L,E), false; true)).
    % CPU time: 84.182s
    true.

    On my machine, that's ca. 15 times slower than SWI 8.3.15, which is the
    last SWI version I found installed on this machine. Newer versions may
    well be faster! For best performance, I recommend to build Scryer Prolog
    with the optional --release flag, i.e.:

    $ cargo build --release
    All the best,
    Markus

    --
    comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
    The Power of Prolog: https://www.metalevel.at/prolog

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Mild Shock@21:1/5 to Mild Shock on Mon Sep 4 12:51:13 2023
    Actually the test was done with JDK 21 as the Java Virtual
    Machine. The older JDK 8 fares a little bit more favorable:

    /* JDK 8 */
    ?- time((between(1,200,N), length(L,N), nth_member(I,L,E), fail; true)).
    % Time 39146 ms, GC 254 ms, Wall 04/09/2023 21:49
    true.

    /* JDK 21 */
    ?- time((between(1,200,N), length(L,N), nth_member(I,L,E), fail; true)).
    % Time 48513 ms, GC 373 ms, Wall 04/09/2023 21:41
    true.

    The formerly Jekejeke Prolog Minlog Extension, that has the
    CLP(FD), isn't public anymore, because I am phasing it out.

    Mild Shock schrieb am Montag, 4. September 2023 um 21:46:18 UTC+2:
    I am also slower than SWI-Prolog with formerly Jekejeke Prolog,
    but sandwhich between Scryer Prolog and SWI-Prolog for this example.
    I never know whether my CLP(FD) still works, so first some sanity checks:

    ?- nth_member(X, [5,4,6], 4).
    X = 2;
    fail.
    ?- nth_member(2, [5,4,6], X).
    X = 4;
    fail.

    Then the benchmark results:
    ?- time((between(1,200,N), length(L,N), nth_member(I,L,E), fail; true)).
    % Time 48513 ms, GC 373 ms, Wall 04/09/2023 21:41
    true.

    But I don't know whether its comparable with Scryer Prolog since
    I didn't test Scryer Prolog, and the Scryer Prolog figures are from
    Markus Triskas machine.

    I am currently phasing out formerly Jekejeke Prolog. It should receive
    the same core as Dogelog Player. And then maybe can also re-add
    CLP(FD) and see what happens. But this might take months. Especially

    since I want to reinvent CLP(FD), adding some CRA Strategy, and I
    don't know yet eactly how to do it. I could optimized the non-labeling behaviour exactly towards this test case, where GNU Prolog performs well. Markus Triska schrieb am Montag, 4. September 2023 um 19:42:01 UTC+2:
    Mild Shock <burs...@gmail.com> writes:

    Whats the Scryer Performance of this Example?

    /* GNU Prolog 1.5.0 */
    ?- between(1,200,N), length(L,N), nth_member(I,L,E), fail; true.
    (94 ms) yes

    /* SWI-Prolog 9.1.14 */
    ?- time((between(1,200,N), length(L,N), nth_member(I,L,E), fail; true)). % 94,504,524 inferences, 4.766 CPU in 4.767 seconds (100% CPU, 19830457 Lips)
    true.
    With Scryer Prolog 0.9.2 on my machine, I get:

    ?- time((between(1,200,N), length(L,N), nth_member(I,L,E), false; true)).
    % CPU time: 84.182s
    true.

    On my machine, that's ca. 15 times slower than SWI 8.3.15, which is the last SWI version I found installed on this machine. Newer versions may
    well be faster! For best performance, I recommend to build Scryer Prolog with the optional --release flag, i.e.:

    $ cargo build --release
    All the best,
    Markus

    --
    comp.lang.prolog FAQ: http://www.logic.at/prolog/faq/
    The Power of Prolog: https://www.metalevel.at/prolog

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)