[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