implement sqrt without using math libray

Question

Herve Thu Timone · Accepted Answer

This is the way to go. Fast inverse square root as used in Quake III.

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;
 
        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed
 
        return y;
}

Ehsan · Answer

I wouldn't know about this algorithm, but I can think of a (definitely slower than this one) bisection algorithm to find the root of x^2 = number.

IT · Answer

e^((ln(x))/2)

fkl · Answer

Often what they are looking for is a programming data structures oriented solution. Such as using binary search to find sq root etc.

Raymond Phan · Answer

I would have implemented either Taylor or MacLaurin series, centered at an integer number that is closest to the number that you want to find the square root for, such that the square root of this integer is clean.

So if you wanted to find the square root of 8.5, I would centre the series at 9 (sqrt(9) = 3), then compute the series at that point.  I'd probably choose between 8 and 10 terms, as that is what is used in any scientific calculator.

Afsheen Ghorashy · Answer

I think exp and ln still require a Math library.  

How about using Newton's method to find the root of f(x) = x^2 - a, where x is the solution (the sought square root) and where a is the number for which you want to find the square root?

Anónimo · Answer

poop

Raymond Phan · Answer

Actually, to add to that, I wouldn't be able to include 8 - 10 terms, as that would rely on the square root operation itself.... so I'd have to rely on a linear approximation.

Herve Thu Timone · Answer

For detailed explanation of the algorithm, see http://en.wikipedia.org/wiki/Fast_inverse_square_root

Meta

Pregunta de entrevista de Meta

Respuestas de entrevistas

Empresas seguidas

Búsquedas de empleo