MathGroup Archive 2011

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: question on diophantine equations in Mathematica


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
> 
> 
> 
> 
> 
> 
> 
> 
> 



  • Prev by Date: Re: question on diophantine equations in Mathematica
  • Next by Date: Re: question on diophantine equations in Mathematica
  • Previous by thread: Re: question on diophantine equations in Mathematica
  • Next by thread: Re: question on diophantine equations in Mathematica