在哪里可以找到标准数学函数的算法？

Question

我希望向D编程语言标准库提交一个补丁,它将允许在编译时使用该语言的编译时功能评估工具评估大部分std.math.编译时功能评估有几个局限性,最重要的是:

1. 您不能使用汇编语言.
2. 您无法调用源代码不可用的C代码或代码.

有几个std.math函数违反了这些函数,需要编写编译时版本.我在哪里可以获得有关计算诸如对数,指数,幂和三角函数等优良算法的信息？我更喜欢算法的高级描述和实际代码,原因有两个:

1. 为避免法律含糊不清,需要让我的代码看起来与源代码"不同",以确保我拥有版权.

2. 我想要简单,便携的算法.我不关心微优化,只要它们至少是渐近有效的.

编辑:D的编译时函数评估模型允许在编译时计算的浮点结果与运行时计算的浮点结果不同,所以我不在乎我的编译时算法是否提供与运行时版本完全相同的结果只要它们在实际上并不那么准确.

Answer 1

约翰 ·威利计算机近似 1968年由John Wiley&Sons编写.

理想情况下,计算应该与运行时完成的计算完全匹配.这可能很棘手.对于许多函数,没有一个序列在整个域上快速收敛,因此算法将各种方法粘贴在一起.

此外,还有各种浮点格式.大多数平台(我认为)现在都使用IEEE 754.当我编写一个编译器时.1985年,我不得不处理跨平台浮点格式.要把它弄好是非常繁琐的,因为你必须一点一点地将数字拼凑在一起,确保你准确得到在目标机器上计算的值.我不知道你是否必须处理这件事.

Answer 2

让 - 米歇尔穆勒的书是一个很好的推荐,哈特也是.

您是否真的有必要拥有版权？如果你可以避免它,那么进入编写数学库函数的业务通常是一个坏主意(我说那是专业人士).我不知道D是否可以接受BSD许可的代码,但是有一些很好的开源实现可能会有所帮助.例如,您可能想要查看Sun的FDLIBM.斯蒂芬莫希尔的Cephes也有可能,虽然它的授权情况有点奇怪,但我相信他一直愿意让人们在其他许可下重新分配他的代码.

另外,除非你支持任意精度浮点(我不认为D会这样做),否则libm函数通常没有"渐近效率"的概念.

Answer 3

正如您所料，其他语言中也会出现类似的问题：

http://java.sun.com/j2se/1.5.0/docs/api/java/lang/StrictMath.html

为了帮助确保 Java 程序的可移植性，此包中的一些数值函数的定义要求它们产生与某些已发布算法相同的结果。这些算法可以从著名的网络库 netlib 中以“自由分发数学库”fdlibm 包的形式获得。这些用 C 编程语言编写的算法将被理解为按照遵循 Java 浮点算术规则的所有浮点运算执行。

我不知道 D 的数学函数运行时计算规则是什么，但您也许可以使用类似的技巧 - 将 fdlibm 的 C 源重新解释为 D。如果 D 调用特定于平台的 C 库，那么您有问题是在编译时可能无法预测运行时值。

我认为 fdlibm 的许可证非常宽松，您必须自己检查它是否适合在 D 中重新分发。我见过的一个版本需要保留版权声明，仅此而已。

Answer 4

请参阅 Jean-Michel Muller 所著的《基本函数：算法与实现》一书 。