//  ============================================================
//
//  sqrt.h
//
//  Copyright 2002, Dennis Meilicke and Rene Peralta
//
//  ============================================================
//
//  Description:
//
//  NTTL Implementation of:
//      Sqrt
//
//  ============================================================
#ifndef __nttl_sqrt__
#define __nttl_sqrt__


#include <nttl/traits.h>


template < class T >
T
Sqrt( const T &S )
//
//  Description
//
//  Calculate the floor of the square root of S.
//
//  Algorithm
//
//  I believe this is Newton's method.  Verification?
//
{
    nttlTraits<T> t;

    if( S == 0 )
        return 0;
        
    if( S < 0 )
    {
        //
        //  This should really throw an exception...
        //
        cerr << "nttl:Sqrt: Can't take Sqrt of negative number" << endl;
        exit( 0 );
    }

    T old = -1;
    T xi = 1;
    while( t.Abs( old - xi ) > 1 )
    { 
        old = xi;
        xi = ( xi + S / xi ) / 2;
    }

    T y;
    y = t.Square( xi );
    if ( y > S ) 
        while( y > S )
        {
            xi--;
            y = t.Square( xi );
        }
    else
        while ( t.Square( xi + 1 ) <= S )
            xi++;

    return xi;
}


#endif // __nttl_sqrt__