UT_ISqrt.h

Go to the documentation of this file.

/*
 * PROPRIETARY INFORMATION.  This software is proprietary to
 * Side Effects Software Inc., and is not to be reproduced,
 * transmitted, or disclosed in any way without written permission.
 *
 * NAME:        UT library (C++)
 *
 * COMMENTS:    Fast lookup to get integer square roots.  The square roots
 *              will round, thus UTisqrt(3) = 2, UTisqrt(2) = 1
 *              The table is good for positive integers up to 1024
 *
 */

#ifndef __UT_ISqrt_h__
#define __UT_ISqrt_h__

#include "UT_API.h"
#include <SYS/SYS_Types.h>
#include <SYS/SYS_Math.h>

// In its previous life, UTisqrt() used a table lookup for values less than
// 1024, and for the rest, fell back to algorithms from:
//    http://www.azillionmonkeys.com/qed/sqroot.html
// However modern hardware has better and more consistent performance computing
// floating point double precision.  The double precision sqrt() is on par in
// performance with the table lookup and considerably faster than the integer
// based algorithms.
//
// One major difference (and flaw with the previous algorithm) was that the LUT
// was built using rounding, while the fall back algorithm rounded to zero.
// The current algorithm uses round to zero for all values.
static inline int
UTisqrt(uint val)
{
    // Use double precision so that the uint precision is fully represented in
    // the mantissa.
    return (int)SYSsqrt(double(val));
}

static inline float
UTinverseSqrt(uint val)
{
    // Use double precision so that the uint precision is fully represented in
    // the mantissa.
    return SYSsaferecip(SYSsqrt(double(val)));
}

#endif