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,
Hi! Wilson Castro wrote:
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;
You mean to print " is prime ", here. [...]
QUESTIONS:
1. because if the length of the two last calls are equal (length (n) = 15), the times reported by “CL_TIMING” are different?
That is a measurement error. By repeating the computation you may evolve a feeling for its magnitude.
it seems to me that the complexity of my approach depends on the primality test of n.
Well, it certainly depends on the outcome of the primality test because if isprobprime(n) returns true, the rest of the loop is cut short. :) But, seriously: The time spent inside isprobprime(n) is negligible compared with the time that goes into your loop running all the way from isqrt(n) down to two.
2. There is some limitation in the length of the algument n in the function "cl_boolean isprobprime (const cl_I& n)"?
Well, sure, but its very much larger that what you can trigger in that experiment. Regards -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>
Wilson Castro wrote:
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; }
Oh, it just occured to me: In order to speed up that program *without* changing the algorithm, you may wish to read about the functions square() and floor2() in the CLN manual. -richy. -- Richard B. Kreckel <http://www.ginac.de/~kreckel/>
Am Freitag, 2. Juni 2006 00:50 schrieb Richard B. Kreckel:
Wilson Castro wrote:
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; }
Oh, it just occured to me: In order to speed up that program *without* changing the algorithm, you may wish to read about the functions square() and floor2() in the CLN manual.
-richy.
Hallo richy, First that everything thank you very much by your commentaries. This would be a solution improved to the problem whose acceptable run time for my intentions. /* ========= Begin ======== */ bool divide(const cl_I a, const cl_I b, cl_I & q) { bool bDivide; q = cln::floor1(a , b); if( q*b == a ) { q = cln::exquo(a , b); bDivide = true; } else { bDivide = false; } return bDivide; } void squarefree_factor(const cl_I n, const cl_I p, cl_I & factor, cl_I & radical) { cl_I prim_quadrat, q; prim_quadrat = p*p; radical = n; factor = 1; while( divide( radical, prim_quadrat, q ) ) { radical = q; factor = factor*p; } } void squarefree_descomposition( cl_I n ) { bool bNegative; if( n < 0 ) bNegative = true; else bNegative = false; if( bNegative ) n = -n; cl_I radical, factor; cl_I p; p = 2; cl_I current_radical, current_factor; current_radical = n; current_factor = 1; factor = 1; cl_I prim_zerlegung; prim_zerlegung = 1; while( prim_zerlegung < n ) { squarefree_factor( current_radical, p, current_factor, radical); factor = factor*current_factor; current_radical = radical; prim_zerlegung = prim_zerlegung*current_factor*p; p = cln::nextprobprime( p + 1); } if( bNegative ) { cout << "sqrt( "<< n <<" ) = " << factor << "*sqrt( "<< radical << " )i" << endl; } else { cout << "sqrt( "<< n <<" ) = " << factor << "*sqrt( "<< radical << " )" << endl; } } int main(int argc, char *argv[]) { if (argc != 2) { std::cerr << "inpunt error" << std::endl; return(1); } cl_I n; //n = "-34054345"; // n = "324523452345234523452345234523523455554054345"; //n = "36058161371692724828038359391502606172672705"; n = (cln::cl_I)argv[1]; { CL_TIMING; squarefree_descomposition(n); } return EXIT_SUCCESS; } /* ========= End ======== */ 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,
participants (2)
-
Richard B. Kreckel
-
Wilson Castro