计算机如何计算平方根？

Question

计算机如何计算平方根？我的意思是那里发生了什么!它是如何处理的!! 它是否使用像牛顿方法那样的数学方法？三角函数怎么样？几乎所有那些数学函数.在每种语言都有自己的方式的情况下,请让我们谈谈c ++.

Answer 1

大多数现代非嵌入式CPU(例如x86和较大的ARM内核)都具有直接计算平方根的硬件指令.支持这些指令的硬件实现各不相同,但通常是教科书逐位算法的变体(尽管不总是在基数为二;也可以使用基数为4或16).这些通常是CPU上最慢的基本算术运算之一; 像16-64周期这样的时序并不罕见,这些指令通常不是流水线的.

在缺乏直接硬件平方根指令(Itanium,PPC,其他)的CPU上,典型的方法是生成初始估计(使用产生估计的指令,或使用查找表),然后使用迭代来优化该估计方法(牛顿或Goldschmidt通常).如果你有兴趣,你可以追踪Peter Markstein或Roger Golliver关于这个主题的一些着作.

更复杂的数学函数(如trig操作)通常通过将参数减少到某个基本域然后用多项式或有理函数逼近来计算.您可以查看在线提供的几个数学库中的任何数据源的更多详细信息(fdlibm是一个很好的起点).

x86指令集提供了许多支持exp,log和sin等数学函数的指令,但这些指令不再常用,因为良好的软件库实现可以提供更好的性能.

Answer 2

关于这个http://www.codeproject.com/Articles/69941/Best-Square-Root-Method-Algorithm-Function-Precisi的好文章,展示了所使用的各种方法的比较.

Answer 3

另一种未提及的可能性是CORDIC方法.CORDIC在软件中没有广泛使用/已知,但在硬件中很常见,并且在不使用大量门的情况下获得不错的性能非常好.

Answer 4

我认为牛顿的迭代收敛方法用于计算平方根