From: Joachim Schimpf <jschimpf_at_coninfer.com>

Date: Sat, 17 Mar 2012 00:29:23 +0100

Date: Sat, 17 Mar 2012 00:29:23 +0100

Sergey Dymchenko wrote: > Hi, > > I want to find positive natural numbers A, B, C, D, such that A^4 + > B^4 + C^4 = D^4. > My program do this: > > A #> 0, B #> 0, C #> 0, D #> 0, > A #=< B, B #=< C, C #=< D, > A*A*A*A + B*B*B*B + C*C*C*C #= D*D*D*D, > labeling([A, B, C, D]) > > But I get incorrect result [1, 1, 9742, 9742] with 10 delayed goals. > As far as I understand, the system finds that the result is imprecise, > but correct enough because 9742^4 is a large number. > Probably floating arithmetic is used, not big integers... > Is there a way to force precise arithmetic for large integers? Hi Sergey, you are right, library(ic) uses floating point arithmetic, which gives you 53 bits of precision. Now, 9742^4 is just above 2^53, that's why you get the first pseudo-result for this magnitude. A simple, brute force way to avoid the pseudo-results is to add a test after search: A #> 0, B #> 0, C #> 0, D #> 0, A #=< B, B #=< C, C #=< D, A^4 + B^4 + C^4 #= D^4, labeling([A, B, C, D]), A^4 + B^4 + C^4 =:= D^4. %%% HERE %%% A somewhat more elegant way is the following: A #> 0, B #> 0, C #> 0, D #> 0, A #=< B, B #=< C, C #=< D, [ic,suspend]:(A^4 + B^4 + C^4 #= D^4), %%% HERE %%% labeling([A, B, C, D]). By annotating the critical constraint with [ic,suspend], we set up two versions of the constraint: the 'ic' version (as before), plus the 'suspend' version (which delays until ground and then tests the equality using integer arithmetic). If you have multiple constraints, you only need to do this for those that are at risk of imprecision due to the large numbers. While this solves the precision problem, I'm afraid I can't help with actually finding solutions - are there any? There is no magic in the propagation that finds [A,B,C] triplets whose 4th powers sum up to a 4th power, so it's mostly search. With your labeling order of A,B,C,D, you get stuck at ?- A #> 0, B #> 0, C #> 0, D #> 0, A #=< B, B #=< C, C #=< D, [ic, suspend] : (A ^ 4 + B ^ 4 + C ^ 4 #= D ^ 4), A = 1, B = 1. A = 1 B = 1 C = C{85 .. 1.0Inf} D = D{85 .. 1.0Inf} There are 9 delayed goals. Yes (0.00s cpu) and then you keep trying values for C from 85 up to infinity. Unless there really is a solution with A=B=1, you will look for larger Cs forever, never going beyond the initial values for A and B. It may be better to label D first, beccause this immediately leads to bounds on the other variables: ?- A #> 0, B #> 0, C #> 0, D #> 0, A #=< B, B #=< C, C #=< D, [ic, suspend] : (A ^ 4 + B ^ 4 + C ^ 4 #= D ^ 4), D = 6. A = A{3 .. 5} B = B{3 .. 5} C = C{3 .. 5} D = 6 There are 11 delayed goals. Yes (0.00s cpu) Now the remaining search space for [A,B,C] is bounded and can be exhausted in finite time. So you can do: ?- A #> 0, B #> 0, C #> 0, D #> 0, A #=< B, B #=< C, C #=< D, [ic, suspend] : (A ^ 4 + B ^ 4 + C ^ 4 #= D ^ 4), labeling([D]), writeln(d = D), labeling([A, B, C]). d = 6 d = 7 d = 8 d = 9 d = 10 ... and at least have the satisfaction of seeing something happening ;) [By the way, I have used X^4 instead of X*X*X*X in all the constraints, because that generally gives better propagation] Cheers, JoachimReceived on Fri Mar 16 2012 - 23:29:31 CET

*
This archive was generated by hypermail 2.2.0
: Sun Mar 18 2012 - 06:18:42 CET
*