[CLN-list] Questions?
Wilson Castro
castro at informatik.uni-kl.de
Fri Jun 2 17:15:11 CEST 2006
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,
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://www.cebix.net/pipermail/cln-list/attachments/20060602/1a59d3fc/attachment.pgp
More information about the CLN-list
mailing list