Hello CLN list-users,
I want to experiment with ring of the form:
(Z mod r) + (Z mod s)*sqrt( z ).
where r,s > 1 in Z, and z in Z with abs(z) is squarefree.
I have done following little program in order to leave in the root the part of
z that is quadrat free.
// --------------------- Begin ----------------------------------- //
void squarefree_descomposition( cl_I n )
{
bool bNegative;
cl_I raiz;
if( n < 0 )
bNegative = true;
else
bNegative = false;
if( bNegative )
n = -n;
if( cln::isprobprime( n ) )
{
cout << n << " is quadrat frei " << "-- if( cln::isprobprime( n ) ) --
" << endl;
}
else
{
if( cln::sqrtp( n, &raiz) )
{
cout << n << " is a perfect square and the exact square root is "
<< raiz << endl;
}
else
{
cl_I m;
cl_I factor;
cln::isqrt( n , &m);
while( m > 1 )
{
factor = cln::floor1( n, m*m);
if( factor*(m*m) == n )
{
cout << "sqrt( "<< n <<" ) = " << m << "*sqrt( "<< factor
<< " )" << endl;
return ;
}
m = m - 1;
}
cout << n << " is quadrat frei" << endl;
}
}
}
// --------------------- End ----------------------------------- //
when I invoke the function as I show in following main.
// --------------------- Begin main ----------------------------------- //
int main(int argc, char *argv[])
{
cl_I n;
n = "9999999999"; // 10
{ CL_TIMING; squarefree_descomposition(n); }
n = "99999999999"; // 11
{ CL_TIMING; squarefree_descomposition(n); }
n = "999999999999"; // 12
{ CL_TIMING; squarefree_descomposition(n); }
n = "9999999999999"; // 13
{ CL_TIMING; squarefree_descomposition(n); }
n = "99999999999999"; // 14
{ CL_TIMING; squarefree_descomposition(n); }
n = "999999999999999"; // 15
{ CL_TIMING; squarefree_descomposition(n); }
n = "999999999999999"; // 15
{ CL_TIMING; squarefree_descomposition(n); }
return EXIT_SUCCESS;
}
// --------------------- End main ----------------------------------- //
I obtain the following result.
sqrt( 9999999999 ) = 3*sqrt( 1111111111 )
real time: 0.131 s, run time: 0.132 s
sqrt( 99999999999 ) = 3*sqrt( 11111111111 )
real time: 0.493 s, run time: 0.456 s
sqrt( 999999999999 ) = 3*sqrt( 111111111111 )
real time: 1.533 s, run time: 1.500 s
sqrt( 9999999999999 ) = 3*sqrt( 1111111111111 )
real time: 4.798 s, run time: 4.760 s
sqrt( 99999999999999 ) = 3*sqrt( 11111111111111 )
real time: 15.180 s, run time: 15.093 s
sqrt( 999999999999999 ) = 3*sqrt( 111111111111111 )
real time: 47.838 s, run time: 47.623 s
sqrt( 999999999999999 ) = 3*sqrt( 111111111111111 )
real time: 48.248 s, run time: 47.811 s
QUESTIONS:
1. because if the length of the two last calls are equal (length (n) = 15),
the times reported by “CL_TIMING” are different?
it seems to me that the complexity of my approach depends on the primality
test of n.
2. There is some limitation in the length of the algument n in the function
"cl_boolean isprobprime (const cl_I& n)"?
thank you very much,
--
Ms. C. Wilson Castro Rojas
Foundations of Informatics Group,
Department of Informatics,
University of Kaiserslautern, Germany, PO Box: 3049,
Building: 34/423, Phone: ++49 631 205 2155, Fax: ++49 631 205 2156,