计算平方根和功率的快速方法？

Question

C#的Math类只有double和powers.如果我将基于浮点的平方根和幂函数添加到我的Math2类(今天是放松日,我发现优化放松),各种事情可能会更快一些.

所以 - 快速的平方根和电源功能,我不必担心许可,plskthx.或者是一个让我在那里的链接.

Answer 1

我将把它作为公理,没有任何软件方法可以与平方根的硬件指令竞争.唯一的困难是.NET不会像C代码的内联汇编程序那样直接控制硬件.

我们先来讨论一下通用的x86硬件前景.

浮点x86指令FSQRT确实有三个精度:单精度,双精度和扩展(80位FP寄存器的原始精度),单精度和双精度的时序缩短了25-40%.有关32位x86指令,请参见此处.

这可能听起来像是一个很大的机会,但它只有十几个时钟.除非您能够仔细管理从函数调用到返回值的代码,否则这种节约将很容易在开销中丢失.托管C++声音(正如Marcelo Cantos建议的那样)比C#更实用.

注意:FSQRT的计时与那些在英特尔架构中共享执行单元的FDIV相同,因此是一种常见的延迟.

专用C#代码的更好机会可能存在于SSE SIMD指令的方向,其中硬件允许并行完成最多4个单精度平方根.多年来JIT编译器对此的支持一直缺失,但这里有一些关于当前开发的线索.

英特尔已经跳入(2010年12月15日),看到.NET Framework 4没有对SIMD做任何事情:

[英特尔性能库允许... C#中的SIMD指令]

甚至在此之前,Mono项目在Mono 2.2中添加了对SIMD的JIT支持:

[单声道:发行说明单声道2.2]

最近在这里提出了从MS C#调用Mono的SIMD支持的可能性:

[从Microsoft .net调用单声道c#代码？ - 堆栈溢出]

之前的一个问题也解决了(尽管没有太多的爱!)如何安装Mono的SIMD支持:

[如何启用Mono.Simd - Stackoverflow]

Answer 2

应该看看这个链接:

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

在一堆不同的语言中有很多快速的算法.

例如:

// 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()  

但是还有更多,一些C/C++应该是最快的,或者他们声称.

对于POW algotrithm检查,我在这里找到了这个,以及如何从简单的算法开始解释该算法.

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; 
} 

Answer 3

最简单的方法可能是在托管 C++ 中实现浮点版本。我不能说这是否会比烘焙的双版本更快。