Re: FD with large domains

[Daniel Diaz]

Hi Fred,

you are right, problems occur here with multiplication overflows. There 
is no good solution (except performing a lot of runtime tests which 
would decrease the performance of the solver). Initially FD are thought 
for "small" finite domains and thus this situation should not occur. 
However this requiere all FD var domains are intially and correctly defined.

You suggestion is interesting (a particular mode which, at least, checks 
overflows). I have to see how this impact my code.

Thank you

Daniel

Le 20/01/2012 15:45, Fred Bapst a écrit :
> Hello,
>
> I'd like to point out a couple of questionable situations in GnuProlog 
> when dealing with FD variables with large domains (eg default domain).
>
> - A*B #= C.                           no
> - fd_domain([A,B,C],0,1000000),
>   A*B #= C.                           no
> - fd_domain([A,B,C],0,10000000),
>   A*B #= C.                           yes
> - X#<1000000,  4321 rem X #= 1.       no
> - X#<10000000, 4321 rem X #= 1.       yes
> -   X*X #= Y.                         yes
> - X*X*X #= Y.                         no
> -  X**3 #= Y.                         yes
>
> Some of these issues might be due to integer overflow. My "numerical 
> problem sniffer" tool suggested for instance to double-check this code 
> snippet from BipsFD/fd_math_fd.fd:
>
> pl_xy_eq_z(fdv X, fdv Y, fdv Z) {
>  ...
>  start Z in min(X)*min(Y)..max(X)*max(Y)
> }
>
> Depending how it gets translated, the integer multiplication might 
> overflow.
>
> Am I off-topic? If not, do you think it is desirable to provide a 
> "mode" where it is ensured that propagation rules avoids overflows 
> that could crash a domain? Could it be proposed as a student project 
> (for how many hours of work)?
>
> Best regards.
>
> _______________________________________________
> Users-prolog mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/users-prolog


--
Ce message a ete verifie par MailScanner
pour des virus ou des polluriels et rien de
suspect n'a ete trouve.