Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Topic: cube root of a given number
Replies: 112   Last Post: Jan 10, 2013 1:39 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
r3769@aol.com

Posts: 352
Registered: 12/12/04
Re: cube root of a given number
Posted: Aug 11, 2007 7:56 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Aug 11, 4:11?pm, "sttscitr...@tesco.net" <sttscitr...@tesco.net>
wrote:
>
> I'm not familiar with Pari/gp, but there are methods using
> the regulator and cycles of ideals that always find
> fundametal units. Aren't they decribed in Cohen's book ?


Yes.

> What's the basic idea ?

Can't really say.

>Isn't this a long way from (vector)
> continued fraction algorithms ?


I suppose.

>
> > I also have a homebrewed method for finding solutions that is pretty
> > fast (it finds a 30000+ digit solution for k=1000700 in less than a
> > minute) but comes without any guarantees about the solution being
> > fundamental.

>
> Yes, you have mentioned this before, but were not specific.
> Didn't you say it was a probabilistic version of Jacobi -erron ?
>


I am not real sure how to describe the method. It does work as
advertised, however. Below is the script. There is clearly room for
improvement.

Rich


\\
\\
\\ This script finds a solution to
P_3(k;x,y,z)=x^3+ky^3+k^2z^3-3kxyz=1 for k=1000700. Here k,x,y,z are
\\ positive integers.
\\

nm1(k,x)=
{
\\
\\ k is k. x is an integer triple, where x[3]/x[1] and x[2]/x[1] are
the reduced approximations
\\ to k^(2/3) and k^(1/3) found below.
\\
return((x[3]^3+k*x[2]^3+k^2*x[1]^3-3*k*x[1]*x[2]*x[3])%modk); \\
return the norm mod k^6
\\
}



lessthan(A,B)=
\\
\\ This routine determines which of the two sets of column norms
corresponding to the reduced approximation
\\ matricies A and B is 'smallest'. Returns true iff A <* B.
\\
\\ The idea here is this: given two matricies, A and B, the columns of
which are reduced approximation
\\ vectors, determine which one has the smallest maximum column norm.
In the case where the largest column
\\ norms are equal, compare the second largest, ect.
\\
{
local(i);

\\(re)compute the norms of the columns of A and B
for(i=1,3,nms_A[i]=nm1(k,A[,i]~);nms_B[i]=nm1(k,B[,i]~)); \\ only 2
of these are new!!!

\\sortem,
nms_A_srt=vecsort(nms_A);
nms_B_srt=vecsort(nms_B);

\\ sort through the ties,
i=3;
while((i>1)&&nms_A_srt[i]==nms_B_srt[i],i=i-1);

\\and return the smallest one.
return(nms_A_srt[i]<nms_B_srt[i])
}


iter()=
\\
\\ This routine acts on D and A. D[1,] is initially an integer
approximation vector to (1,k^(1/3),k^(2/3)). A is
\\ the identity matrix. Given D, two reduction matricies B_s and B
are computed, along with the two possible
\\ new values of A. lessthan is used to select the correct new A and
B then D is reduced.
\\
\\ The entries of A, if not controlled, grow rapidly and result in an
increasing execution time. I.e if a large
\\ number of iterations are needed to find a solution the process of
determining what swap to make is painfully slow.
\\ Note, however, that lessthan(A,B)=lessthan(A mod k^6,B mod k^6),
given each column norm is bounded by k^6.
\\ So the computational effort required to make the swap decision is
bounded.
\\

{
B_s=[1,-(D[1,1]\D[1,2]),0;0,-(D[1,3]\D[1,2]),1;0,1,0];
A_s=(A*(B_s)^(-1))%modk;
\\
B=[-(D[1,2]\D[1,1]),1,0;-(D[1,3]\D[1,1]),0,1;1,0,0];
A=(A*B^(-1))%modk;
\\
\\ this is the key: directed swaps
\\
if(lessthan(A_s,A),A=A_s;B=B_s);
\\
\\ now reduce D accordingly
\\
D=D*B~;
\\
\\ Every fifteenth iteration, add some more precision. 15 is a
guess!!
\\
if(itercnt%15==0,D=C10*D);
\\
\\ Keep the unreduced values in A_act
\\
A_act=A_act*B^(-1);
\\
\\ (Re)compute the norm and stop if = 1, printing z where
x=round(z*k^(2/3)) and y=round(z*k^(1/3)).
\\
tmp=nm1(k,A[,3]~);
if((tmp==1)&&(A_act[1,3]>10),print(vecmin(A_act[,
3]));return(0),return(1));


}

find_p3()=
{
default(timer,1);
k=1000700;
modk=k^6;
A=matid(3);
A_act=A;
nms_A=vector(3);
nms_B=nms_A;
\\ C is the matrix used to approximate [1,k^(1/3),k^(2/3)]
\\ The entries are derived from the small rational solution
[900630049/49,9004200/49,90021/49] to
\\ P_3(k,x,y,z)=1. These small rational solutions are fairly easy to
find.
\\
C=[900630049,9004200,90021;
k*90021,900630049,9004200;
k*9004200,k*90021,900630049]~;
C10=C;
D=C;
itercnt=0;
while(iter(),itercnt=itercnt+1);
print();
}

find_p3;

\\ end script



Date Subject Author
4/20/04
Read cube root of a given number
vsvasan
4/20/04
Read Re: cube root of a given number
A N Niel
4/20/04
Read Re: cube root of a given number
Richard Mathar
7/14/07
Read Re: cube root of a given number
Sheila
7/14/07
Read Re: cube root of a given number
amzoti
7/14/07
Read Re: cube root of a given number
quasi
7/14/07
Read Re: cube root of a given number
arithmeticae
7/16/07
Read Re: cube root of a given number
Gottfried Helms
7/16/07
Read Re: cube root of a given number
Iain Davidson
7/21/07
Read Re: cube root of a given number
arithmetic
7/21/07
Read Re: cube root of a given number
arithmetic
7/21/07
Read Re: cube root of a given number
Iain Davidson
7/21/07
Read Re: cube root of a given number
arithmetic
7/22/07
Read Re: cube root of a given number
Iain Davidson
7/22/07
Read Re: cube root of a given number
arithmetic
7/22/07
Read Re: cube root of a given number
Iain Davidson
7/23/07
Read Re: cube root of a given number
arithmetic
7/24/07
Read Re: cube root of a given number
Iain Davidson
7/24/07
Read Re: cube root of a given number
arithmetic
7/24/07
Read Re: cube root of a given number
arithmetic
7/24/07
Read Re: cube root of a given number
Iain Davidson
7/25/07
Read Re: cube root of a given number
arithmetic
7/24/07
Read Re: cube root of a given number
gwh
7/25/07
Read Re: cube root of a given number
arithmetic
7/25/07
Read Re: cube root of a given number
Iain Davidson
7/25/07
Read Re: cube root of a given number
arithmetic
7/25/07
Read Re: cube root of a given number
Iain Davidson
7/25/07
Read Re: cube root of a given number
arithmetic
7/25/07
Read Re: cube root of a given number
arithmetic
7/25/07
Read Re: cube root of a given number
Iain Davidson
7/25/07
Read Re: cube root of a given number
arithmetic
7/26/07
Read Re: cube root of a given number
Iain Davidson
7/26/07
Read Re: cube root of a given number
arithmetic
7/26/07
Read Re: cube root of a given number
Iain Davidson
7/26/07
Read Re: cube root of a given number
arithmetic
8/6/07
Read Re: cube root of a given number
arithmetic
7/26/07
Read Re: cube root of a given number
semiopen
7/26/07
Read Re: cube root of a given number
Iain Davidson
7/26/07
Read Re: cube root of a given number
semiopen
7/26/07
Read Re: cube root of a given number
arithmetic
7/26/07
Read Re: cube root of a given number
semiopen
7/26/07
Read Re: cube root of a given number
arithmetic
7/26/07
Read Re: cube root of a given number
Iain Davidson
7/27/07
Read Re: cube root of a given number
arithmetic
7/27/07
Read Re: cube root of a given number
Iain Davidson
7/27/07
Read Re: cube root of a given number
Iain Davidson
7/27/07
Read Re: cube root of a given number
arithmetic
7/27/07
Read Re: cube root of a given number
arithmetic
7/27/07
Read Re: cube root of a given number
arithmetic
7/27/07
Read Re: cube root of a given number
Iain Davidson
7/27/07
Read Re: cube root of a given number
arithmetic
7/27/07
Read Re: cube root of a given number
Iain Davidson
7/27/07
Read Re: cube root of a given number
arithmetic
7/27/07
Read Re: cube root of a given number
Iain Davidson
7/27/07
Read Re: cube root of a given number
arithmetic
7/27/07
Read Re: cube root of a given number
arithmetic
7/27/07
Read Re: cube root of a given number
Iain Davidson
7/27/07
Read Re: cube root of a given number
arithmetic
7/27/07
Read Re: cube root of a given number
Iain Davidson
7/28/07
Read Re: cube root of a given number
arithmetic
7/28/07
Read Re: cube root of a given number
Iain Davidson
8/5/07
Read Re: cube root of a given number
arithmeticae
8/5/07
Read Re: cube root of a given number
Iain Davidson
8/6/07
Read Re: cube root of a given number
arithmetic
8/6/07
Read Re: cube root of a given number
Iain Davidson
8/6/07
Read Re: cube root of a given number
arithmeticae
8/7/07
Read Re: cube root of a given number
Iain Davidson
8/7/07
Read Re: cube root of a given number
mike3
8/10/07
Read Re: cube root of a given number
arithmetic
8/10/07
Read Re: cube root of a given number
Iain Davidson
8/11/07
Read Re: cube root of a given number
r3769@aol.com
8/11/07
Read Re: cube root of a given number
Iain Davidson
8/11/07
Read Re: cube root of a given number
r3769@aol.com
8/11/07
Read Re: cube root of a given number
Iain Davidson
8/11/07
Read Re: cube root of a given number
r3769@aol.com
8/12/07
Read Re: cube root of a given number
Iain Davidson
8/17/07
Read Re: cube root of a given number
r3769@aol.com
8/12/07
Read Re: cube root of a given number
arithmetic
8/13/07
Read Re: cube root of a given number
Iain Davidson
8/24/07
Read Re: cube root of a given number
arithmetic
8/28/07
Read Re: cube root of a given number
narasimham
1/10/13
Read Re: cube root of a given number ...
Milo Gardner
8/28/07
Read Re: cube root of a given number
arithmetic
8/28/07
Read Re: cube root of a given number
Iain Davidson
8/7/07
Read Re: cube root of a given number
mike3
8/7/07
Read Re: cube root of a given number
Iain Davidson
8/10/07
Read Re: cube root of a given number
arithmetic
8/10/07
Read Re: cube root of a given number
arithmetic
7/28/07
Read Re: cube root of a given number
arithmetic
7/27/07
Read Re: cube root of a given number
arithmetic
7/27/07
Read Re: cube root of a given number
arithmetic
7/27/07
Read Re: cube root of a given number
arithmetic
7/26/07
Read Re: cube root of a given number
Iain Davidson
7/26/07
Read Re: cube root of a given number
arithmetic
7/25/07
Read Re: cube root of a given number
Iain Davidson
7/26/07
Read Re: cube root of a given number
arithmetic
7/22/07
Read Re: cube root of a given number
arithmetic
7/21/07
Read Re: cube root of a given number
arithmetic
7/16/07
Read Re: cube root of a given number
Proginoskes
7/21/07
Read Re: cube root of a given number
arithmetic
7/22/07
Read Re: cube root of a given number
Proginoskes
7/22/07
Read Re: cube root of a given number
Virgil
7/22/07
Read Re: cube root of a given number
Proginoskes
7/23/07
Read Re: cube root of a given number
arithmetic
7/23/07
Read Re: cube root of a given number
arithmetic
7/24/07
Read Re: cube root of a given number
Proginoskes
7/16/07
Read Re: cube root of a given number
gwh
7/17/07
Read Re: cube root of a given number
Iain Davidson
7/21/07
Read Re: cube root of a given number
arithmetic
7/21/07
Read Re: cube root of a given number
arithmetic
7/21/07
Read Re: cube root of a given number
arithmetic
7/24/07
Read Re: cube root of a given number
pomerado@hotmail.com
7/25/07
Read Re: cube root of a given number
orangatang1@googlemail.com

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.