Estimating the square root

Question

I am writing an iPhone app that needs to calculate the square root of a number about 2000 times every 1/30th of a second. sqrt() works fine on a computer, but the frame rate drops to around 10 FPS on an iPhone or iPad, and I have already optimized the rest of the code. I have heard that this can be sped up dramatically by estimating the square root, but I can not find any code to do this. I only need one or two decimal places of precision. Any suggestions on how to do this, or other ways to speed things up would be appreciated.

Thanks!

Answer 1

Unless you actually need the square root, compare the squared values rather than the raw values and the square root.

Squaring is much faster (and more accurate) than taking a square root, if you only need comparisons. This is the way most games do it.

Answer 2

Do you know the range of values that you are trying to find the square root of? Say you have values ranging from 0 to 10. You can then precalculate an array:

sqrt_val[0] = 0;
sqrt_val[1] = 1;
sqrt_val[2] = // the sqrt of 2
...
sqrt_val[10] = // the sqrt of 10

Then during runtime you take the number that you want the sqrt of, convert that to an integer (so for example 3.123 becomes 3) and use that as an index (3) to look up the precalculated value.

Of course if you want finer resolution you can just increase the number of items in your array.