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

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