#include "Util/Assert.H"#include "Util/Promotions.H"#include "rutz/compat_cmath.h"
Go to the source code of this file.
Fast Square Root Methods | |
These are several methods for computing a quick square root approximation. The order is by decreasing speed / increasing accuracy Name : opperation time relative to sqrt() fastSqrt_2 : 1/5 fastSqrt_Bab : 1/2 fastSqrt_Q3 : 2/3 fastSqrt_Bab_2 : 2/3 Details: fastSqrt_2 - This is a simple log base 2 approximation using a union to int and an 4 simple arith operations. fastSqrt_Bab - This is the fastSqrt_2 with a Babylonian step added to give it a quadratic improvement. fastSqrt_Q3 - This uses the Quake 3 InvRoot function with a quick estimation and a single Newton step. This will call invSqrt listed below. fastSqrt_Bab_2 - This is the fastSqrt_Bab with two Babylonian Steps instead of just one. | |
| #define | SQRT_MAGIC_F 0x5f3759df |
| #define | SQRT_MAGIC_D 0x5fe6ec85e7de30da |
| #define | KIMS_CONST_F 0x4C000 |
| #define | KIMS_CONST_D (KIMS_CONST_F << 29) |
| #define | ACOS_TABLE_SIZE 513 |
| float | fastSqrt_2 (const float x) |
| Fast and dirty Log Base 2 appoximiation for square root. | |
| double | fastSqrt_2 (const double x) |
| Fast and dirty Log Base 2 appoximiation for square root. | |
| float | fastSqrt_Bab (const float x) |
| Fast and dirty Log Base 2 appoximiation with a Babylonian Step Clean up. | |
| double | fastSqrt_Bab (const double x) |
| Fast and dirty Log Base 2 appoximiation with a Babylonian Step Clean up. | |
| float | invSqrt (const float x) |
| Quake 3 Fast Square Root Approximation. | |
| float | fastSqrt_Q3 (const float x) |
| Fast Square Root Approximation. | |
| double | invSqrt (const double x) |
| Quake 3 Fast Square Root Approximation. | |
| double | fastSqrt_Q3 (const double x) |
| Fast Square Root Approximation. | |
| float | fastSqrt_Bab_2 (const float x) |
| Fast and dirty Log Base 2 appoximiation with two Babylonian Steps. | |
| double | fastSqrt_Bab_2 (const double x) |
| Fast and dirty Log Base 2 appoximiation with two Babylonian Steps. | |
| char | fastSqrt (const char x) |
| This just creates a default function call. | |
| int | fastSqrt (const int x) |
| This just creates a default function call. | |
| float | fastSqrt (const float x) |
| This just creates a default function call. | |
| double | fastSqrt (const double x) |
| This just creates a default function call. | |
| float | fastacos (int x) |
|
| |
| #define | ONE TBL_LOG_P[0] |
| #define | TWO52 TBL_LOG_P[1] |
| #define | LN2HI TBL_LOG_P[2] |
| #define | LN2LO TBL_LOG_P[3] |
| #define | A1 TBL_LOG_P[4] |
| #define | A2 TBL_LOG_P[5] |
| #define | A3 TBL_LOG_P[6] |
| #define | A4 TBL_LOG_P[7] |
| #define | A5 TBL_LOG_P[8] |
| #define | A6 TBL_LOG_P[9] |
| #define | A7 TBL_LOG_P[10] |
| #define | A8 TBL_LOG_P[11] |
| #define | A9 TBL_LOG_P[12] |
| #define | A10 TBL_LOG_P[13] |
| #define | A11 TBL_LOG_P[14] |
| #define | A12 TBL_LOG_P[15] |
| #define | B1 TBL_LOG_P[16] |
| #define | B2 TBL_LOG_P[17] |
| #define | B3 TBL_LOG_P[18] |
| #define | B4 TBL_LOG_P[19] |
| #define | B5 TBL_LOG_P[20] |
| #define | B6 TBL_LOG_P[21] |
| #define | B7 TBL_LOG_P[22] |
| #define | B8 TBL_LOG_P[23] |
| #define | HIWORD 1 |
| #define | LOWORD 0 |
| static const double | TBL_LOG_P [] |
| static const double | _TBL_log [] |
| double | fastLog (const double x) |
| Fast Log - Stripped version of libm's Log(x). | |
Miscellaneous math functions
Definition in file FastMathFunctions.H.
| double fastLog | ( | const double | x | ) | [inline] |
Fast Log - Stripped version of libm's Log(x).
This is the libm log stripped down with slightly less precision and no handling for inf, 0 etc.
For an idea of how this works see:
http://www.informatik.uni-trier.de/Reports/TR-08-2004/rnc6_07_dinechin.pdf
This is about 15% faster than the standard log()
Definition at line 888 of file FastMathFunctions.H.
References log().
| double fastSqrt | ( | const double | x | ) | [inline] |
This just creates a default function call.
Definition at line 407 of file FastMathFunctions.H.
References sqrt().
| float fastSqrt | ( | const float | x | ) | [inline] |
This just creates a default function call.
Definition at line 401 of file FastMathFunctions.H.
References sqrt().
| int fastSqrt | ( | const int | x | ) | [inline] |
This just creates a default function call.
Definition at line 395 of file FastMathFunctions.H.
References sqrt().
| char fastSqrt | ( | const char | x | ) | [inline] |
This just creates a default function call.
This just creates a default function call
Definition at line 389 of file FastMathFunctions.H.
References sqrt().
Referenced by gauss(), junctionFilterPartial(), and MSTFilterPartial().
| double fastSqrt_2 | ( | const double | x | ) | [inline] |
Fast and dirty Log Base 2 appoximiation for square root.
Definition at line 130 of file FastMathFunctions.H.
References fastSqrt_2().
| float fastSqrt_2 | ( | const float | x | ) | [inline] |
Fast and dirty Log Base 2 appoximiation for square root.
This method is most useful if the number is a power of 2. In this case, the results are accurate. The largest error tends to be with numbers half way between two powers of 2. So as an example:
fastSqrt_2(2) and fastSqrt_2(4) will give exact answers while fastSqrt_2(3) will give 1.5 when the answer should be 1.414
See: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
Time savings using this is approx 1/5 the time of a normal square root.
Definition at line 108 of file FastMathFunctions.H.
Referenced by fastSqrt_2().
| double fastSqrt_Bab | ( | const double | x | ) | [inline] |
Fast and dirty Log Base 2 appoximiation with a Babylonian Step Clean up.
Definition at line 184 of file FastMathFunctions.H.
References fastSqrt_Bab().
| float fastSqrt_Bab | ( | const float | x | ) | [inline] |
Fast and dirty Log Base 2 appoximiation with a Babylonian Step Clean up.
Time savings using this is approx 1/2 the time of a normal square root.
Definition at line 169 of file FastMathFunctions.H.
Referenced by fastSqrt_Bab().
| double fastSqrt_Bab_2 | ( | const double | x | ) | [inline] |
Fast and dirty Log Base 2 appoximiation with two Babylonian Steps.
Definition at line 315 of file FastMathFunctions.H.
References fastSqrt_Bab_2().
| float fastSqrt_Bab_2 | ( | const float | x | ) | [inline] |
Fast and dirty Log Base 2 appoximiation with two Babylonian Steps.
Time savings using this is approx 2/3 the time of a normal square root.
This one gives fairly good estimates with a 50% speed up:
| sqrt(x) | Result | Actual Answer using libm
0 | 1.000000 | 1.000000 | 1.000000 1 | 2.000000 | 1.414216 | 1.414214 2 | 8.000000 | 2.828431 | 2.828427 3 | 100.000000 | 10.000000 | 10.000000 4 | 3.141593 | 1.772454 | 1.772454 5 | 100000.000000 | 316.227783 | 316.227753 6 | 0.333333 | 0.577350 | 0.577350
Definition at line 295 of file FastMathFunctions.H.
Referenced by fastSqrt_Bab_2().
| double fastSqrt_Q3 | ( | const double | x | ) | [inline] |
Fast Square Root Approximation.
Time savings using this is approx 2/3 the time of a normal square root.
Definition at line 273 of file FastMathFunctions.H.
References invSqrt().
| float fastSqrt_Q3 | ( | const float | x | ) | [inline] |
Fast Square Root Approximation.
Time savings using this is approx 2/3 the time of a normal square root.
Definition at line 241 of file FastMathFunctions.H.
References invSqrt().
| double invSqrt | ( | const double | x | ) | [inline] |
Quake 3 Fast Square Root Approximation.
Definition at line 248 of file FastMathFunctions.H.
References invSqrt().
| float invSqrt | ( | const float | x | ) | [inline] |
Quake 3 Fast Square Root Approximation.
The integer-shift approximation produced a relative error of less than 4%, and the error dropped further to 0.15% with one iteration of Newton's method on the following line. In computer graphics it is a very efficient way to normalize a vector.
Note: This must be a floating point due to the IEEE method for approx. of sqrt. See the double method below which uses a different magic constant.
To get the square root, divide 1 by the final x. See: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots
Definition at line 225 of file FastMathFunctions.H.
Referenced by fastSqrt_Q3(), and invSqrt().
const double TBL_LOG_P[] [static] |
{
1.0,
4503599627370496.0,
6.93147180369123816490e-01,
1.90821492927058770002e-10,
-6.88821452420390473170286327331268694251775741577e-0002,
1.97493380704769294631262255279580131173133850098e+0000,
2.24963218866067560242072431719861924648284912109e+0000,
-9.02975906958474405783476868236903101205825805664e-0001,
-1.47391630715542865104339398385491222143173217773e+0000,
1.86846544648220058704168877738993614912033081055e+0000,
1.82277370459347465292410106485476717352867126465e+0000,
1.25295479915214102994980294170090928673744201660e+0000,
1.96709676945198275177517643896862864494323730469e+0000,
-4.00127989749189894030934055990655906498432159424e-0001,
3.01675528558798333733648178167641162872314453125e+0000,
-9.52325445049240770778453679668018594384193420410e-0001,
-1.25041641589283658575482149899471551179885864258e-0001,
1.87161713283355151891381127914642725337613123482e+0000,
-1.89082956295731507978530316904652863740921020508e+0000,
-2.50562891673640253387134180229622870683670043945e+0000,
1.64822828085258366037635369139024987816810607910e+0000,
-1.24409107065868340669112512841820716857910156250e+0000,
1.70534231658220414296067701798165217041969299316e+0000,
1.99196833784655646937267192697618156671524047852e+0000,
}
Log Function
Definition at line 520 of file FastMathFunctions.H.
1.6.3