PAL Square root (in-) accuracy

[mmasten]

I realize there is a tradeoff between accuracy and speed when computing square roots, and that you're never going to get a super-accurate result with a float type anyway. But, if I were a user of the library, I would expect the results to be as close to correct as what a float can store (or just about). Here are some sample outputs I feel are unacceptably inaccurrate (I selected perfect squares to make it more obvious what the error is):

1 -> 0.9999957
4 -> 1.999991
16 -> 3.999983
400 -> 19.99993
676 -> 25.99988
2500 -> 49.9998
10000 -> 99.9996
410881 -> 640.9977
1000000 -> 999.9957

Note that the output for 410881 corresponds to what would be a reasonable output for a number 3 smaller, and that the output for a million corresponds to what it should be for a number 8.6 smaller.

It looks like the algorithm is based on Newton's method, but using only two iterations. That's not quite as bad as it might sound, since it uses the kludgey Quake III hack (including use of a magic number and manipulating the bits of a float as if it were an integer) to generate the initial value, which actually works surprisingly well. Still, I think there should be at least one more iteration in order to get reasonably acceptable output values.

Also, I think it might be nice to provide an inverse square root function, which would require almost no additional code, and would avoid the need for an unnecessary multiplication and division when computing this value.

Best Regards

[jar]

[mmasten]

Thanks for your reply. You make a lot of good points, and I agree that 2 iterations may be good enough for many applications (in fact, Quake III only needed one iteration).

I think a 3rd iteration, while still not perfect, takes the accuracy into the "good enough" range, although others might not think even that's sufficient. As you brought up, it would be helpful to have more guidance about what "sufficiently accurate" means. To me, especially for a math function, given the choice between a reasonably fast function that yields very accurate results, and a very fast function that yields only reasonable results, I would use the more accurate function just about every time. The only time I would use the less accurate version would be when I had reason to suspect that the function calls were getting repeated enough times to significantly slow execution, and when I also felt that the accuracy wasn't too important (both). In other words, I would almost never use the library version as it is currently implemented. I can live with that, but it should really be the other way around (that you would normally use the library version except in unusual circumstances).