0

我想找到一个计算 1/d 的快速算法，其中 d 是双倍的（尽管它可以转换为整数）许多算法（SRT、goldschmidt、newton raphson、...）中最好的算法是什么？我是用c语言编写我的程序。

提前致谢。

4

3 回答 3

5

最快的程序是double result = 1 / d：

于 2013-06-22T16:26:23.720 回答
2

CPU：s已经使用像您描述的那样的求根迭代算法来找到倒数1 / d。因此，您应该会发现使用相同算法的软件实现很难击败它。

如果您的分母很少/已知，请尝试查找表。这是用于更慢的函数（例如三角函数）的常用方法。

否则：只计算 1/d。这将是你能做的最快的。如果必须的话，你可以做无数的事情来加速算术

  • 使用 32 位（单）而不是 64 位（双）精度。FP 除法上的周期数与位数成正比。
  • 向量化操作。例如，我相信您可以与 SSE2 并行计算四个 32 位浮点除法，或者通过在 GPU 上并行计算更多。
于 2013-06-22T17:41:53.850 回答
1

我已经从某人那里问过了，我得到了答案：

那么，您不能在FPGA中添加硬件分频器吗？还是快速互惠支持？

无论如何，这取决于。它有快速乘法吗？如果不是，那是个问题，你只能实现慢速方法。

如果您有快速乘法和 IEEE 浮点数，您可以使用我在上一篇文章中链接到的奇怪技巧，并通过几个细化步骤。这实际上只是 Newton-Raphson 除法，对初始近似值进行了更简单的计算（但 afaik 仍然只需要对单精度浮点数进行 3 次改进，就像常规的初始近似值一样）。快速互惠支持也以这种方式工作 - 给出一个快速的初始近似值（处理正确的指数并从查找表中获取有效位，如果您以这种方式获得 12 个有效位，则您只需要一个细化步骤来实现单精度，或者 13 个就足够了获得 2 个双精度步骤）并可选地具有帮助实现细化步骤的指令（如 AMD 的 PFRCPIT1 和 PFRCPIT2），例如计算 Y = (1 - D*X) 并计算 X + X * Y。

即使没有这些技巧，牛顿-拉夫森除法仍然不错，使用线性近似，双精度浮点数只需要 4 次改进，但也需要一些烦人的指数调整才能首先进入正确的范围（在硬件中不会烦人的一半）。

Goldschmidt 部门，afaik，在性能上大致相当，并且可能有一个稍微不那么复杂的实现。这实际上是同一类交易 - 将指数置于正确范围内的技巧，“2 - 某事”估计技巧（在 Newton-Raphson 分区中重新排列，但实际上是同一件事），并进行细化步骤直到所有位都正确。它只是看起来有点不同。

于 2014-01-29T13:27:42.267 回答