计算机如何计算平方根?我的意思是那里发生了什么!它是如何处理的!!它是否使用了一些数学方法,如牛顿法?三角函数呢?几乎所有的数学函数。在每种语言都有自己的方式的情况下,那么让我们谈谈c ++。
4 回答
大多数现代非嵌入式 CPU(例如 x86 和更大的 ARM 内核)具有直接计算平方根的硬件指令。支持这些指令的硬件实现各不相同,但通常是教科书逐位算法的变体(尽管并不总是以 2 为底;也可以使用以 4 或 16 为底的算法)。这些通常是 CPU 上最慢的基本算术运算。像 16-64 个周期这样的时序并不少见,而且这些指令通常不是流水线的。
在缺乏直接硬件平方根指令(Itanium、PPC 等)的 CPU 上,典型的方法是生成初始估计(使用产生估计的指令或使用查找表),然后使用迭代优化该估计方法(通常是牛顿法或戈德施密特法)。如果你有兴趣,你可以找到一些 Peter Markstein 或 Roger Golliver 关于这个主题的著作。
更复杂的数学函数(如三角运算)通常通过将参数减少到一些基本域然后用多项式或有理函数逼近来计算。您可以查看在线提供的几个数学库中的任何一个的源以获取更多详细信息(fdlibm 是一个很好的起点)。
x86 指令集提供了许多支持数学函数的指令,如 exp、log 和 sin,但这些不再常用,因为好的软件库实现可以提供更好的性能。
Another possibility that hasn't been mentioned, is the CORDIC method. CORDIC isn't widely used/known in software, but is pretty common in hardware, and does pretty well at getting decent performance without using a lot of gates.
我认为牛顿的迭代收敛方法用于计算平方根
正如其他人所指出的那样,这是一个非常广泛的问题 - 对软件有效的方法可能对硬件实现来说是一个糟糕的选择;然后是 IEEE-754、硬件查找表等的正确舍入问题。有很多开源 C 库,也有libm
实现。可以在这里找到经典和现代方法的一个很好的概述。