Given r^2, is there an efficient way to compute r^3?

Question

double r2 = dx * dx + dy * dy;
double r3 = r2 * sqrt(r2);

Can the second line be replaced by something faster? Something that does not involve sqrt?

Answer 1

I think another way to look at your question would be "how to calculate (or approximate) sqrt(n)". From there your question would be trivial (n * sqrt(n)). Of course, you'd have to define how much error you could live with. Wikipedia gives you many options:

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

Answer 2

How about

double r3 = pow(r2,1.5);

If sqrt is implemented as a special case of pow, that will save you a multiplication. Not much in the grand scheme of things mind!

If you are really looking for greater efficiency, consider whether you really need r^3. If, for example, you are only testing it (or something derived from it) to see whether it exceeds a certain threshold, then test r2 instead e.g.

const double r3_threshold = 9;

//don't do this
if (r3 > r3_threshold)
    ....

//do do this
const double r2_threshold = pow(r3_threshold,2./3.); 
if (r2 > r2_threshold)
    ....

That way pow will be called only once, maybe even at compile time.

EDIT If you do need to recompute the threshold each time, I think the answer concerning Q_rsqrt is worth a look and probably deserves to outrank this one

Answer 3

Use fast inverse sqrt (take the Q_rsqrt function).

You have:

float r2;
// ... r2 gets a value
float invsqrt = Q_rsqrt(r2);
float r3 = r2*r2*invsqrt; // x*x/sqrt(x) = x*sqrt(x)

NOTE: For double types there is a constant like 0x5f3759df which can help you write a function that handles also double data types.

LATER EDIT: Seems like the method has been already discussed here.

LATER EDIT2: The constant for double was in the wikipedia link:

Lomont pointed out that the "magic number" for 64 bit IEEE754 size type double is 0x5fe6ec85e7de30da, but in fact it is close to 0x5fe6eb50c7aa19f9.