[CLN-list] Questions?

1 Jun 2006

      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,