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

Re: question on diophantine equations in Mathematica

• To: mathgroup at smc.vnet.net
• Subject: [mg115544] Re: question on diophantine equations in Mathematica
• From: Adam Strzebonski <adams at wolfram.com>
• Date: Fri, 14 Jan 2011 06:17:38 -0500 (EST)

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