Re: [CLN-list] Questions?

2 Jun 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,