From Newsgroup: comp.lang.prolog


Lets say you don't trust what a quantum computer
finds as a tripple for (x,y,z) to satisfy:

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

You could then view it as a candidate triple
only, and still feed it into a normal computer

and see whether it is a solution. Kind of combining
approximate search with exact verification.
Mild Shock schrieb am Freitag, 5. Januar 2024 um 23:07:44 UTC+1:

What speed-up could a N-qubit quantum computer give
to this problem, find a positive integer tripple (x,y,z) such that:

x^3 + y^3 + 42 = z^3
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

--- Synchronet 3.20a-Linux NewsLink 1.114