Fixing a square to a root
6, May, 2019I am implementing a small math library for my new game. It is fixed precision based (8.8 bit), as target processor (apollo-core 68080) has some SSE-like extensions for it. I encountered a problem - I need to normalize a vector. So, the length shall be computed
len = sqrt(a.x*a.x + ...)
and then each component needs to be divided by it a.x /= len. So my trivial approach was to get sqrt() function from the math.c. So, the fixed number is converted to the float, the square root is computed and the result is converted back to fixed number. This approach has some drawback through:
- The conversions are expensive.
- The processor has floating point unit but it does not have sqrt function - it is ~250 CPU cycles long procedure!
- Each component need to be divided, but the processor does not have vector division (only multiplication in vector mode, the division is only scalar).
So, let’s go with some research. Quite good summary of these methods is available on wikipedia http://en.wikipedia. … mputing_square_roots. The easiest one is Newton-Raphson method (Babylonian) - it is iterative method where each step is an average of current guess x and a geometric grow rate of the guess and input number s, that is 0.5 (x + s/x) or in code:
short fixsqrt(short a) {
int s = a;
int x = 1 << 8;
for (int i = 0; i < N; ++i) {
x = (x + (s << 8) / x) >> 1;
}
return x;
}
It is very stable and robust method. But there is a (slow) division. The other method is to compute the inverse square root directly - also with Newton’s method. The next step is calculated from x = 0.5*x*(3-s*x*x). And here is problem, the method is not so stable. Sources, which I have found seemed even to demonize that instability - that we need to make a very good guess, make some Babylonian iteration first, that it is totally unstable using a fixed precision. I couldn’t find a good material on the subject. But, we only need to look at the equation. Let’s see, the RHS of the equation shall be positive (as the result shall be). The 1.0 seemed to be quite good starting point previously. So, maybe we only need to assume that 3 > s > 0? Few computations, and looks good. But, I have range up to s = 8F.FF. Few seconds later and solution found - sqrt(s) == sqrt(4 * s’) == 2 sqrt(s’). We may divide s by 4 and then the resultant 1/sqrt(s) divide by 2. Of course using shifts, not divisions. Let’s see:
short fixisqrt(short a) {
int s = a;
int x = 1 << 8;
int n = 0;
while (s >= 0x300) {
s = s >> 2;
++n;
}
for (int i = 0; i < N; ++i) {
x = (0x300 - ((((s * x) >> 8) * x) >> 8)) * x >> 9;
}
return x >> n;
}
This seems to work, the process converges smoothly, errors are small and there is no single division. Tested on all possible (8.8 bit) numbers, the relative error was less than 0.01 for whole range. As the result is the inverse of square root now each component of the vector may multiplied by it (not divided) to be normalized. This implementation is now ready to be handcrafted with AMMX vector unit.
- Posted by michal in
- Add a comment