Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #14788

Monte Carlo sampling the frontier version (Was: Yeah, we have another name!)

Show all headers | View raw

You can also test what was posted 06.08.2025
on comp.lang.prolog and then adopted by @kuniaki.mukai .
Here are the benchmark resuts, I find now.
Using again the Monte Carlo method:

?- time((between(1,100,_), mercio2, fail; true)).
% 4,404,670 inferences, 0.375 CPU in 0.375 seconds
true.

Practically no difference between mercio2/3
and mercio/2. The problem is that mercio2 doesn’t
add much smarts to the algorithm. Whereas for
example SWI-Prolog compare/3

has the smarts of Union Find. So a little break
through in Mercio’s Idea needs more than only
recasting the truncation sequences as a frontier list:

mercio2(C, X, Y) :- X == Y, !, C = (=).
mercio2(C, X, Y) :- mercio2_iter(C, [X-Y]).

mercio2_iter(C, L) :-
     compare_truncs(D, L),
     D \== (=), !, C = D.
mercio2_iter(C, L) :-
     next_truncs(L, R),
     mercio2_iter(C, R).

compare_truncs(C, []) :- !, C = (=).
compare_truncs(C, [X-Y|_]) :-
     trunc(X, A),
     trunc(Y, B),
     compare(D, A, B),
     D \== (=), !, C = D.
compare_truncs(C, [_|L]) :-
     compare_truncs(C, L).

trunc(X, A) :- var(X), !, X = A.
trunc(X, F/N) :- functor(X, F, N).

next_truncs([], []).
next_truncs([X-_|L], R) :-  var(X), !,
     next_truncs(L, R).
next_truncs([X-Y|L], R) :-
     next_truncs(L, H),
     X =.. [_|A],
     Y =.. [_|B],
     zip(A, B, J),
     append(J, H, R).

zip([], [], []).
zip([X|L], [Y|R], [X-Y|H]) :-
     zip(L, R, H).

Mild Shock schrieb:
> 
> I like the vibe, clearing the mind of everything
> existing has a touch of a mystic human being living
> an eremitic solitary vocation on a far out mountain
> top. Using the internet only to emit his wisdom,
> 
> but not to ingest the outer world, just as in
> Thus Spoke Zarathustra (*). Another name for Fuzzy Testing,
> if the outcome is not finding the needle in the haystack,
> but rather producing quantitative outcomes is,
> 
> unless of course you were living in a submerged pineapple (**):
> 
> Monte Carlo methods
> or Monte Carlo experiments, are a broad class of
> computational algorithms that rely on repeated random
> sampling to obtain numerical results
> https://en.wikipedia.org/wiki/Monte_Carlo_method
> 
> (*)
> Also Sprach Zarathustra, Op. 30 - Strauss
> https://www.youtube.com/watch?v=dfe8tCcHnKY
> 
> (**)
> Every Time Patrick Was Actually Smart
> https://www.youtube.com/watch?v=siBRUuDxU1E

Back to comp.lang.prolog | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Mercio’s Algorithm for Rational Tree Compare in Prolog Mild Shock <janburse@fastmail.fm> - 2025-08-04 02:52 +0200
  The Original Ganster (OG) of Gameification: IEEE 1044.1-1995 (Was: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-04 13:48 +0200
    The Bitrot called Math Stack Exchange (Re: The Original Ganster (OG) of Gameification: IEEE 1044.1-1995) Mild Shock <janburse@fastmail.fm> - 2025-08-04 14:00 +0200
      I guess its back to Hopcroft and Karp.Re: The Bitrot called Math Stack Exchange) Mild Shock <janburse@fastmail.fm> - 2025-08-04 14:11 +0200
  Szpilrajn Theorem and Suzumura Consistency (Was: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-06 01:50 +0200
    The good thing is we have at least Mercio’s Algorithm (Re: Szpilrajn Theorem and Suzumura Consistency) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:10 +0200
      Hopcroft and Karp’s is just Contraction (Was: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:13 +0200
        Re: Hopcroft and Karp’s is just Contraction (Was: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-06 08:23 +0200
      Should we use minimum_coa/3 ? (Was: The good thing is we have at least Mercio’s Algorithm) Mild Shock <janburse@fastmail.fm> - 2025-08-08 23:45 +0200
        Perfectly balanced , as all things should be! (Was: Should we use minimum_coa/3 ?) Mild Shock <janburse@fastmail.fm> - 2025-08-08 23:49 +0200
  Mercios decidability was already attested in 2012 (Was: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-14 20:26 +0200
    Performance of Mercio’s Total Order (Was: Mercios decidability was already attested in 2012) Mild Shock <janburse@fastmail.fm> - 2025-08-15 23:49 +0200
      Fuzzy Testing is your Swiss Knife (Re: Performance of Mercio’s Total Order) Mild Shock <janburse@fastmail.fm> - 2025-08-15 23:55 +0200
        Yeah, we have another name! (Was: Fuzzy Testing is your Swiss Knife) Mild Shock <janburse@fastmail.fm> - 2025-08-16 12:38 +0200
        Monte Carlo sampling the frontier version (Was: Yeah, we have another name!) Mild Shock <janburse@fastmail.fm> - 2025-08-16 12:42 +0200
        AI most hated by formal verification (Was: Fuzzy Testing is your Swiss Knife) Mild Shock <janburse@fastmail.fm> - 2025-11-26 17:02 +0100
  An NPU could give 1000x more LIPS (Was: Mercio’s Algorithm for Rational Tree Compare in Prolog) Mild Shock <janburse@fastmail.fm> - 2025-11-27 14:19 +0100
    Neural Network based dif/2 respectively (#\=)/2 (Re: An NPU could give 1000x more LIPS) Mild Shock <janburse@fastmail.fm> - 2025-11-27 14:51 +0100
      Zeus: A Language for Expressing Algorithms in Hardware (Re: Neural Network based dif/2 respectively (#\=)/2) Mild Shock <janburse@fastmail.fm> - 2025-11-27 15:03 +0100
        Googles TPU muscle in 2017 [Prolog Community is Sleepy Joe] (Re: Zeus: A Language for Expressing Algorithms in Hardware) Mild Shock <janburse@fastmail.fm> - 2025-11-27 15:23 +0100
    100% serious Giga Logical Inferences per Second (GLIPS) (Was: An NPU could give 1000x more LIPS) Mild Shock <janburse@fastmail.fm> - 2025-11-28 14:50 +0100
      The tables have turned: GigaLIP on the Laptop? (Re: 100% serious Giga Logical Inferences per Second (GLIPS) Mild Shock <janburse@fastmail.fm> - 2025-11-28 15:12 +0100

csiph-web