计算平方根和幂的快速方法？

Question

计算平方根和幂的快速方法？

c#mathexponent

5

C#的Math类只支持双精度数的平方根和幂运算。如果我在我的Math2类中添加基于单精度数的平方根和幂函数，可能会使某些事情更快（今天是放松的一天，我觉得优化很放松）。

所以 - 快速的平方根和幂函数，我不需要担心许可证问题，请给我提供一个链接。

- Narf the Mouse

2

如果内置函数已经编译成每个x86指令，那么你不可能做得比内置函数更好。 - user395760

2

"plskthx"? 这是一个打错了吗？（这里的人不全是基于美国短信的。） - aaaa bbbb

2

@aaaa bbbb: “请了解，好的，谢谢”。我只是在幽默。 - Narf the Mouse

在不同的时候，我大多数时候会得到一些在纸上计算出来后实施起来变慢的方法。其他的则是代码最终运行变慢。但是我的发现能力...嘿，我的屏幕去哪了！呵呵。 - Narf the Mouse

1

检查这个反平方根的链接：http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/ - eulerfx

显示剩余2条评论

5个回答

6

你应该查看这个链接：

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算法的检查，我发现了这个链接，以及如何从简单的算法开始到达该算法的解释。

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

- Francisco Noriega

这两个算法与问题无关。他需要浮点数（而不是整数）的平方根（即0.5次幂）。 - Snowbear

哈哈，旧留言但我刚看到：P，话说，不，他的主要问题是“快速计算平方根和幂”的方法，在他的心中，使用浮点数是一种优化方法，但他从未说过他被迫使用浮点数，只是他在进行优化。我给了他一个答案，提供了几个非常好的平方根和幂算法。 - Francisco Noriega

1

维基百科有一篇关于计算平方根的广泛文章： http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

计算x的y次幂更简单： http://www.osix.net/modules/article/?id=696

我喜欢这种口袋计算器的做法： enter image description here ...但是我真的不知道它是否快速。

- Simen S

我已经看过那篇维基百科文章了。里面充斥着“你可以这样做，但是会很慢”或“你可以那样做，但结果相对不准确”的内容。 - Narf the Mouse

我被口袋计算器实现良好的指数函数和自然对数的说法所吸引，并将使用上述函数来计算平方根。 - Simen S

0

可能最简单的方法是在托管C++中实现浮点版本。它是否比内置的双精度版本更快，我无法确定。

- Marcelo Cantos

好观点。但是如果没有算法来实现和测试，我就不会知道这一点。 :) - Narf the Mouse

2

@Narf: 只需调用标准C库函数(sqrtf, powf, sinf, expf, …)。 - Marcelo Cantos

0

如果你想要找到一种非迭代、盲目、单行方程的方法（不是算法），那么在这里。由于该方程是一个纯数学的、也是一个数学常数/普遍真理，产生一个数学客观结果（平方根），你不能对该方程进行专利或版权保护。它是供所有人免费使用的。

N = ;

root=(a=(ceil((floor((N/2/(d = (floor((N/8)+4)/2)))))+(d/2))))+((N-(aa))(1/(a*2+1)));

请记住，目前这个方程只能粗略估计无理数的平方根。但我将在将来修复这个问题。

我不会发布源代码。但你可以用scanf读取N，然后将root作为浮点数，最后用printf输出root。

- BetterDaysAhead

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hardmath · Accepted Answer

我将把这个看作公理，即没有软件方法能与硬件指令竞争求平方根。唯一的困难是，在.NET中我们无法像C代码内联汇编语言那样直接控制硬件。
让我们先讨论一下通用x86硬件前景。
浮点x86指令FSQRT确实有三种精度：单精度、双精度和扩展精度（80位FP寄存器的本地精度），而单精度比双精度快25-40%。请参见here以获取32位x86指令。
这听起来可能是一个很大的机会，但只有大约十几个时钟周期。这种经济效益很容易在开销中丢失，除非您能够从函数调用到返回值仔细管理代码。如Marcelo Cantos所建议的，Managed C++似乎比C#更实用。
注意：FSQRT的时间与FDIV相同，它们共享Intel架构中的执行单元，因此具有共同的延迟。

更好的专业化C#代码机会可能存在于SSE SIMD指令的方向，其中硬件允许同时执行最多4个单精度平方根运算。JIT编译器对此的支持已经缺失了多年，但以下是关于当前开发的一些线索。

英特尔公司已经加入其中（2010年12月15日），看到.NET Framework 4没有对SIMD进行任何处理： [英特尔性能库允许在C#中使用SIMD指令] 甚至早在此之前，Mono项目就在Mono 2.2中添加了对SIMD的JIT支持： [Mono：发布说明Mono 2.2] 最近提出了从MS C#调用Mono的SIMD支持的可能性： [从Microsoft .net调用mono c#代码？-- Stackoverflow]

之前的一个问题也提到了如何安装Mono的SIMD支持（虽然没有得到太多关注）：

[如何启用Mono.Simd -- Stackoverflow]