Fast method of calculating square root and power?

Question

C#'s Math class does roots and powers in double only. Various things may go a bit faster if I add float-based square-root and power functions to my Math2 class (Today is a relaxation day and I find optimization relaxing).

So - Fast square-root and power functions that I don't have to worry about licensing for, plskthx. Or a link that'll get me there.

Solution 1

I'm going to take it as axiomatic that no software method will compete with the hardware instruction for square roots. The only difficulty is that .NET doesn't give us direct control of the hardware as in the days of inline assembler for C code.

Let's first discuss a generic x86 hardware prospect.

The floating point x86 instruction FSQRT does come in three precisions: single, double, and extended (the native precision of the 80-bit FP registers), and there is a 25-40% shorter timing for single vs. double precision. See here for 32-bit x86 instructions.

That may sound like a big opportunity, but it's only a dozen clocks or so. That sort of economization will easily get lost in the overhead unless you are able to carefully manage the code from function call to return value. Managed C++ sounds (as Marcelo Cantos suggests) like a more practical base for this than C#.

Note: Timings for FSQRT are identical to those FDIV, with which it shares an execution unit in the Intel architecture, and thus a common latency.

A better opportunity for specialized C# code probably exists in the direction of SSE SIMD instructions, where hardware allows for up to 4 single precision square roots to be done in parallel. JIT compiler support for this has been missing for years, but here are some leads on current development.

Intel has jumped in (Dec. 15,2010), seeing that .NET Framework 4 wasn't doing anything with SIMD:

[Intel Performance Libraries allow... SIMD instructions in C#]

Even before that the Mono project added JIT support for SIMD in Mono 2.2:

[Mono: Release Note Mono 2.2]

The possibility of calling Mono's SIMD support from MS C# was recently raised here:

[Calling mono c# code from Microsoft .net ? -- Stackoverflow]

An earlier question also addresses (though without much love shown!) how to install Mono's SIMD support:

[how to enable Mono.Simd -- Stackoverflow]

Solution 2

Should check out this link:

http://www.codecodex.com/wiki/Calculate_an_integer_square_root

has lots of speedy algorithms in a bunch of different languages.

Ex:

// Finds the integer square root of a positive number  
public static int Isqrt(int num) {  
    if (0 == num) { return 0; }  // Avoid zero divide  
    int n = (num / 2) + 1;       // Initial estimate, never low  
    int n1 = (n + (num / n)) / 2;  
    while (n1 < n) {  
        n = n1;  
        n1 = (n + (num / n)) / 2;  
    } // end while  
    return n;  
} // end Isqrt()  

but there are a lot more, some C/C++ ones are supposed to be the fastest, or so they claim.

for the POW algotrithm check i found this one HERE, along an explanation of how to get to that algorithm, starting from simpler ones.

private double Power(double a, int b) { 
    if (b<0) { 
        throw new ApplicationException("B must be a positive integer or zero"); 
    } 
    if (b==0) return 1; 
    if (a==0) return 0; 
    if (b%2==0) { 
        return Power(a*a, b/2); 
    } else if (b%2==1) { 
        return a*Power(a*a,b/2); 
    } 
    return 0; 
} 

Solution 3

Wikipedia has an extensive article on calculation of square roots: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

Calculating x to the power of y is simpler: http://www.osix.net/modules/article/?id=696

I liked this pocked calculator way of doing it: ... but I honestly have no idea whether it is fast.

Comments

[Narf the Mouse]

Good point. But I won't know that without (an) algorithm(s) to implement and test. :)

[Snowbear]

Those two algorithms have nothing to do with question. He needs floating-based (not integers) square root (which is 0.5 power)

[Alex S]

@Narf: Just call the standard C library functions (sqrtf, powf, sinf, expf, ...).

[Narf the Mouse]

I've looked at that Wikipedia article. It's full of "You can do this, but it's slow" or "You can do that, but it's rather inaccurate".

[Simen S]

I was intrigued by the claim that pocket calculators tend to implement good exponential functions and natural logarithms and will use the function above to calculate a square root

[Francisco Noriega]

Lol, old comment but I just saw it :P, any way, no, his main question was "Fast method of calculating square root and power", in his mind, using floats was a an approach to optimize, but he never said he was forced to use floats, just that he was optimizing. I gave him an answer that offers several really good algorithms for square root and powers.