Re: [eclipse-clp-users] Large integers and delayed goals

From: Kish Shen <kisshen_at_cisco.com>
Date: Wed, 14 Mar 2012 18:23:31 +0000
Hi Sergey (and others),

Several comments:

ic does not handle large integers, i.e. it does not use the bignum 
representation of integers that ECLiPSe supports (implemented with GNU's 
GMP).

I don't think any integer finite domain solver will handle a large 
finite domain well, both because reasoning and propagating over large 
domains is expensive (e.g. many constraints have a very heavy dependency 
on the domain size(s) of its variabes (particularly if they are domain 
consistent); and also labelling variables with large domain is expensive 
(unless propagation is able to very significantly reduce the domain 
size).  In the case of ic, where a finite domain is represented as a 
bitmap (1 bit per domain value) as soon as a hole appears in the domain, 
this is particularly inefficient if you have a large domain.

Sergrey, you used labeling/1 in the code you showed, but I assume you 
must have given a finite integer interval to the variables, because you 
get an error when you try to label IC variables that do not have a 
finite integer range.

The running of the example with lib(fd) is not "correct" in the sense 
that fd correctly handles large integers in the constraint, as fd 
variables are given a default range (-10,000,000 to 10,000,000), and the 
constraint limits the range of integer range for A,B,C,D accordingly, 
and it is only these values that will be tried. If you try to give a 
variable in a constraint a value that will result in a  value that is 
outside this default range, the constraint will fail, e.g.:

:- lib(fd).

:- A*A #= B*B + C*C, A = 50000.

fails. [this is incorrect in the sense that with large enough range, the 
above does have a solution]

Thorsten: I think gfd is much slower in this example because for the 
constraint A*A*A*A + B*B*B*B +C*C*C*C #= D*D*D*D does not seem to take 
into account the default interval given to the variable, and seem to be 
reasoning assuming the variables have the full (32 bit) range  (it 
assigns a domain of 1..46340 to the variables after posting of this 
constraint, compared to 1..3162 for lib(fd)). [lib(gfd) does give a 
default interval (currently -1,000,000..1,000,000) to variables whose 
domain are not explicitly specified]

Cheers,

Kish


On 14/03/2012 07:33, Matteo Bellotto wrote:
> Dear Sergey,
>      the way numbers are managed depend on the particular solver used.
>      In your email there's a generic reference to ECLiPSe and this isn't sufficient. The only clue you gave is the use of integer constraints. So I supposed you're talking about the "IC" solver.
>
>   In this case you could read the documentation below:
>
>        http://eclipseclp.org/doc/libman/libman017.html
>
>   and
>
>        http://eclipseclp.org/doc/libman/libman019.html
>
> In general, despite the particular solver you are referring to, I think that RTFM it's a good starting point.
>
> Have a nice reading,
> Matteo.
>
>
> ________________________________
> Da: Sergey Dymchenko<kit1980_at_gmail.com>
> A: Matteo Bellotto<matteob8_at_yahoo.it>
> Cc: "eclipse-clp-users_at_lists.sf.net"<eclipse-clp-users_at_lists.sf.net>
> Inviato: Marted́ 13 Marzo 2012 14:03
> Oggetto: Re: [eclipse-clp-users] Large integers and delayed goals
>
> Hi Matteo,
>
> My question was more about how ECLiPSe works with large integers, not
> about this particular problem.
> And it's clear that if we constrain our variables to be at most 100 we
> will not get rounding errors.
>
> Sergey.
>
> On Tue, Mar 13, 2012 at 2:31 PM, Matteo Bellotto<matteob8_at_yahoo.it>  wrote:
>> Hi Sergey,
>>   using your code I obtained the same, wrong, result.
>> I've sligtly modified your code, defining explicitly the domain of the
>> variables, and this update has improved the search, i.e. I didn't get any
>> "wrong answer".
>> Here there the modified code:
>>
>>   :-lib(ic).
>>   test(Result):-
>>    Result=[A,B,C,D],
>>    Result:: 1..100,
>>
>>    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]).
>>
>>   ?- test(R).
>>   No (22.43s cpu)
>>
>> Please note that, increasing the domains bounds, the search will take a
>> (really) longer time.
>>
>> Bye,
>> Matteo.
>>
>> Da: Sergey Dymchenko<kit1980_at_gmail.com>
>> A: eclipse-clp-users_at_lists.sourceforge.net
>> Inviato: Venerd́ 9 Marzo 2012 18:24
>> Oggetto: [eclipse-clp-users] Large integers and delayed goals
>>
>> 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?
>>
>> Sergey.
>>
>> ------------------------------------------------------------------------------
>> Virtualization&  Cloud Management Using Capacity Planning
>> Cloud computing makes use of virtualization - but cloud computing
>> also focuses on allowing computing to be delivered as a service.
>> http://www.accelacomm.com/jaw/sfnl/114/51521223/
>> _______________________________________________
>> ECLiPSe-CLP-Users mailing list
>> ECLiPSe-CLP-Users_at_lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>>
>>
>>
>> ------------------------------------------------------------------------------
>> Keep Your Developer Skills Current with LearnDevNow!
>> The most comprehensive online learning library for Microsoft developers
>> is just $99.99! Visual Studio, SharePoint, SQL - plus HTML5, CSS3, MVC3,
>> Metro Style Apps, more. Free future releases when you subscribe now!
>> http://p.sf.net/sfu/learndevnow-d2d
>> _______________________________________________
>> ECLiPSe-CLP-Users mailing list
>> ECLiPSe-CLP-Users_at_lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>>
>
> ------------------------------------------------------------------------------
> Virtualization&  Cloud Management Using Capacity Planning
> Cloud computing makes use of virtualization - but cloud computing
> also focuses on allowing computing to be delivered as a service.
> http://www.accelacomm.com/jaw/sfnl/114/51521223/
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users


-- 
This e-mail may contain confidential and privileged material for the
sole use of the intended recipient. Any review, use, distribution or
disclosure by others is strictly prohibited. If you are not the intended
recipient (or authorized to receive for the recipient), please contact
the sender by reply e-mail and delete all copies of this message.
Cisco Systems Limited (Company Number: 02558939), is registered in
England and Wales with its registered office at 1 Callaghan Square,
Cardiff, South Glamorgan CF10 5BT.
Received on Wed Mar 14 2012 - 18:23:40 CET

This archive was generated by hypermail 2.2.0 : Thu Mar 15 2012 - 06:15:49 CET