- Mail actions: [ respond to this message ] [ mail a new topic ]
- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Kish Shen <kisshen_at_...5...>

Date: Wed, 14 Mar 2012 18:23:31 +0000

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_...6...> > A: Matteo Bellotto<matteob8_at_...325...> > Cc: "eclipse-clp-users_at_...105..."<eclipse-clp-users@...105...> > 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_...325...> 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_...6...> >> 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.3.0
: Wed Sep 25 2024 - 15:13:20 CEST
*