Re: question on diophantine equations in Mathematica
- To: mathgroup at smc.vnet.net
- Subject: [mg115519] Re: question on diophantine equations in Mathematica
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Thu, 13 Jan 2011 03:27:56 -0500 (EST)
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>
> 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>
> > 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
> >
> >
>
>