Re: question on diophantine equations in Mathematica
- To: mathgroup at smc.vnet.net
- Subject: [mg115545] Re: question on diophantine equations in Mathematica
- From: Ivan Smirnov <ivan.e.smirnov at gmail.com>
- Date: Fri, 14 Jan 2011 06:17:49 -0500 (EST)
If so, why then your PC computed it from 1 to 10^10 (in such big interval) with only 269.967 and my is still computing yet, more than 20 minutes? I asked it only from this point. It can be only from hardware difference. What is your CPU&RAM&bitness, Adam? 2011/1/14 Adam Strzebonski <adams at wolfram.com> > For Diophantine equations Solve and Reduce use the same code, so there > should be no speed difference. > > > Best Regards, > > Adam Strzebonski > Wolfram Research > > > Ivan Smirnov wrote: > >> Am I right that with such constraints Reduce now is many faster than >> Solve? >> >> 2011/1/14 Adam Strzebonski <adams at wolfram.com <mailto:adams at wolfram.com>> >> >> >> Reduce does a case-by-case search here, but it chooses the variables >> with smallest ranges of values for the search. >> >> In[1]:= form = x^10 + y^10 + z^10 == t^2 && x >= 0 && y >= 1 && >> x <= y && y <= z && 1 <= t <= 250000; >> >> In[2]:= vars = {x, y, z, t}; >> >> In[3]:= {Ceiling[MinValue[#, form, vars]], >> Floor[MaxValue[#, form, vars]]}&/@vars >> >> Out[3]= {{0, 10}, {1, 11}, {1, 12}, {2, 250000}} >> >> Reduce does case-by-case search for the first 3 variables, >> so the problem reduces to solving >> >> In[4]:= 11 11 12 >> Out[4]= 1452 >> >> univariate quadratic equations. The most time-consuming part >> here is computing the MinValue/MaxValue (8 CAD problems with >> 4 variables). >> >> This method will do exhaustive search on {x, y, z} as long as >> the number of possible {x, y, z} values does not exceed 10000. >> >> If you want it to do larger searches you need to change >> the second value of the system option >> >> In[5]:= "ExhaustiveSearchMaxPoints"/.("ReduceOptions"/.SystemOptions[]) >> Out[5]= {1000, 10000} >> >> This increases the maximum number of search points to 10^6. >> >> In[6]:= >> SetSystemOptions["ReduceOptions"->{"ExhaustiveSearchMaxPoints"-> >> {1000, 10^6}}]; >> >> This proves that the problem has no solutions with t <= 10^10 >> (a search over 828630 cases). >> >> In[7]:= Reduce[x^10 + y^10 + z^10 == t^2 && 0 <= x && 0 < y && >> x <= y && y <= z && 1 <= t <= 10^10, {x, y, z, t}, Integers] // Timing >> >> Out[7]= {269.967, False} >> >> >> Best Regards, >> >> Adam Strzebonski >> Wolfram Research >> >> >> >> Andrzej Kozlowski wrote: >> >> Actually Solve (and Reduce) are remarkably efficient at solving >> this problem. It is better to reformulate it by requiring that >> the two smallest values be larger than 0. This eliminates all >> trivial solutions. Solve (and Reduce) then work remarkably fast >> for very large numbers t, e.g. >> >> Solve[ >> x^10 + y^10 + z^10 == t^2 && 0 <= x && 0 < y && x <= y && y <= >> z && 1 <= t <= 250000, {x, y, z, t}, Integers] // Timing >> >> {1.80372,{}} >> >> Now look at this: >> >> >> In[1]:= Solve[ >> x^10 + y^10 + z^10 == t^2 && 0 <= x && 0 < y && x <= y && y <= >> z && 1 <= t <= 350000, {x, y, z, t}, Integers] // Timing >> >> Out[1]= {1.90608,{}} >> >> This is so fast that it almost excludes the possibility of "case >> by case" verification. Moreover, solving the problem for t= >> 350,000 took only slightly longer than for t= 250,000. >> If this is indeed a valid proof (and I think it is - Reduce >> gives the same answer) then it looks like Solve is really using >> some knowledge of Diophantine equations to solve this. It would >> be really interesting to know what is going on. I almost >> inclined to believe that Solve is able to prove that there are >> no solutions for all t, but running it without a bound on t >> produces a useless (in this context) "conditional" answer: >> >> >> Solve[x^10+y^10+z^10==t^2&&0<=x&&0<y&&x<=y&&y<=z,{x,y,z,t},Integers] >> (Output deleted). >> >> I do hope we get some insight into what Solve is doing. It is >> beginning to look fascinating, although I am probably missing >> something simple... >> >> Andrzej Kozlowski >> >> On 12 Jan 2011, at 19:41, Andrzej Kozlowski wrote: >> >> Yes, but I think I unintentionally deceived you (and >> myself). Mathematica caches its results and recall that I >> tried solving this several times with different numbers >> before I run Timing. mathematica obviously remembered all >> the answers and when I tried measuring the time taken it was >> amazingly fast. I should have found it suspicious but as I >> was busy with other things I did not notice anything. >> >> Now that I tried again with a fresh kernel the results are >> much less impressive: in fact much closer to yours. >> But note that now it is clear that Solve is very much faster >> than PowersRepresentatins (it looked the other way round >> before). In fact Solve deals with this impressively fast: >> >> Timing[ >> Select[Table[ >> PowersRepresentations[t^2, 3, 10], {t, 1, 90000}], #1 != {} >> & ]] >> >> {641.343049, {{{0, 0, 1}}, {{0, 0, 2}}, {{0, 0, 3}}, {{0, 0, >> 4}}, {{0, 0, 5}}, {{0, 0, 6}}, {{0, 0, 7}}, {{0, 0, >> 8}}, {{0, 0, 9}}}} >> >> >> Timing[ >> Solve[x^10 + y^10 + z^10 == t^2 && 0 <= x && x <= y && y <= >> z && 1 <= t <= 90000, {x, y, z, t}, Integers]] >> >> {1.161798, {{x -> 0, y -> 0, z -> 1, t -> 1}, {x -> 0, y >> -> 0, z -> 2, t -> 32}, {x -> 0, y -> 0, z -> 3, t -> >> 243}, {x -> 0, y -> 0, z -> 4, t -> 1024}, {x -> 0, y -> >> 0, z -> 5, t -> 3125}, {x -> 0, y -> 0, z -> 6, t -> >> 7776}, {x -> 0, y -> 0, z -> 7, t -> 16807}, {x -> 0, y >> -> 0, z -> 8, t -> 32768}, {x -> 0, y -> 0, z -> 9, t >> -> 59049}}} >> >> This suggests strongly that you should in fact use Solve. >> However, you should not try to test for too large a group of >> solutions at a time. For example, you can get the next >> 10,000 quickly: >> >> Timing[ >> Solve[x^10 + y^10 + z^10 == t^2 && 0 <= x && x <= y && y <= >> z && 90000 <= t <= 100000, {x, y, z, t}, Integers]] >> >> {1.48964,{{x->0,y->0,z->10,t->100000}}} >> >> But the time for this 10,000 is longer than for the previous >> 90,000! >> >> With best regards >> >> Andrzej >> >> >> >> On 12 Jan 2011, at 16:03, Ivan Smirnov wrote: >> >> Oh, it's very cool computer. What model of CPU, Intel or >> AMD? >> I just thought that time was in seconds, but surprised >> that it took so few time and asked. >> I have only 1.6 Ghz Acer (Intel T5500) with 1 GB Ram, so >> for 1..90000 it took 1034 seconds to compute... >> >> 2011/1/12 Andrzej Kozlowski <akoz at mimuw.edu.pl >> <mailto:akoz at mimuw.edu.pl>> >> >> I am using Mathematica 8 on 2.66 Ghz Mac Book Pro with 8 >> gigabytes of Ram. The time is measured in seconds. With >> Mathematica 8 you can also get the same answer with Solve: >> >> Timing[ >> Solve[x^10 + y^10 + z^10 == t^2 && 0 <= x && x <= y && y >> <= z && >> 1 <= t <= 90000, {x, y, z, t}, Integers]] >> >> >> {1.01969,{{x->0,y->0,z->1,t->1},{x->0,y->0,z->2,t->32},{x->0,y->0,z->3,t->243},{x->0,y->0,z->4,t->1024},{x->0,y->0,z->5,t->3125},{x->0,y->0,z->6,t->7776},{x->0,y->0,z->7,t->16807},{x->0,y->0,z->8,t->32768},{x->0,y->0,z->9,t->59049}}} >> >> I think for very large numbers PowersRepresentations >> will give you more satisfactory answers. For example, >> compare the output >> >> Solve[x^10 + y^10 + z^10 == 10^20 && 0 <= x && x <= y && >> y <= z, {x, >> y, z, t}] >> >> with >> >> PowersRepresentations[10^21, 3, 10^20] >> >> {} >> >> Andrzej Kozlowski >> >> >> >> >> On 12 Jan 2011, at 13:16, Ivan Smirnov wrote: >> >> Hello, Andrzej. >> Many thanks for reply. >> What PC do you use (OS, CPU & RAM) and how many >> minutes did it take to compute, what is 0.872...? >> What is the upper margin for t which can cause >> overflow? >> Do you have any other ideas how to increase >> performance for my task? >> Will be very glad for help >> >> 2011/1/12 Andrzej Kozlowski <akoz at mimuw.edu.pl >> <mailto:akoz at mimuw.edu.pl>> >> >> This seems to show that there are only trivial >> solutions for 1<=t<=90000 >> >> Timing[ >> Select[Table[ >> PowersRepresentations[t^2, 3, 10], {t, 1, 90000}], >> #1 != {} & ]] >> >> {0.8722430000000259, {{{0, 0, 1}}, {{0, 0, 2}}, {{0, 0, >> 3}}, {{0, 0, 4}}, {{0, 0, 5}}, {{0, 0, 6}}, {{0, 0, >> 7}}, >> {{0, 0, 8}}, {{0, 0, 9}}}} >> >> The algorithm basically uses "brute force" so you >> will start getting overflows for very large t. >> >> Andrzej Kozlowski >> >> >> >> On 12 Jan 2011, at 01:25, Ivan Smirnov wrote: >> >> Hi all, >> I've installed trial of Mathematica 8. >> I would like to search for possible solutions of >> diophantine equation >> x^10+y^10+z^10=t^2. >> How to do this efficiently? >> FindInstance seems to be VERY slow! And indeed >> it doesn't always find every >> solution of diophantine equations. For example >> I've tried it with >> x^4+y^4+z^4=t^4 and it didn't find anything (but >> there are solutions!). >> And Solve command just don't want to search! >> With some seconds it gives >> During evaluation of In[1]:= Solve::svars: >> Equations may not give solutions >> for all "solve" variables. >> >> I will be very glad if someone make INDEED FAST >> algorithm for searching. >> >> Ivan >> >> >> >> >> >> >> >> >> >> >