13

在阅读了这篇论文和这篇论文之后，我最近遇到了精确实数算术这个主题。

我发现许多论文讨论了使用有符号数字流实现精确算术。对任意精度使用无限流可以在函数式语言（如 Haskell）中使用惰性列表实现很好的实际实现。然而，在函数式语言中讨论此类实现的论文似乎得出的结论是性能非常差。

现在，我意识到与标准浮点表示相比，精确的非硬件实现通常具有相对较差的性能，但我有兴趣以命令式语言（特别是 C++）和一组操作提供更有效的实现/functions（算术运算、三角函数、exp、log 等）。

我的问题：有符号数字/惰性流表示是否存在固有的缓慢导致性能不佳的问题，或者是 Haskell？是什么让它变慢？是否有可能在 C++ 中使用惰性流实现有符号数字流表示，从而实现（显着）比其 Haskell 对应物更好的性能，或者这是徒劳的练习？也许重建为迭代？

我知道有两个 C++ 库 RealLib 和 iRRAM 可以实现高效的实数计算。但是，这些似乎使用区间算术，将实数表示为缩小的嵌套区间，这似乎不像无限流那样“纯”一种方法（如果您不同意，请纠正我！）。但也许这些是实现良好效率的唯一方法？

任何输入表示赞赏！

4

2 回答 2

8

有符号数字/惰性流表示是否存在固有的缓慢导致性能不佳的问题，或者是 Haskell？是什么让它变慢？是否有可能在 C++ 中使用惰性流实现有符号数字流表示，从而实现（显着）比其 Haskell 对应物更好的性能，或者这是徒劳的练习？也许重建为迭代？

惰性流最有效地表示为具有延迟函数组件的数据。这就是 GHC 中相当高效的 Haskell 实现所使用的表示形式，无论如何您都需要在 C++ 中使用它。没有可以用 C++ 编写的特殊“快速”版本的懒惰，在 20 年的 Haskell 编译器研究中还没有尝试过，更多的可以追溯到 Algol。

有关如何最有效地实现惰性数据结构的研究的更多详细信息，请参阅关于 GHC 实现的好介绍性文本？

现在，鉴于缺乏有关基准的信息，有几个可能的答案：

  • 代码写得不好（更好的实现可能不会很慢）
  • 将大数字表示为标记的惰性位是空间效率低下的，导致各种硬件瓶颈
  • 数字的惰性流表示只允许某些线性算法。更密集的表示可能会接受具有更好复杂性或绝对性能的算法。

我的猜测是后两点。C++ 版本的惰性只会很难达到 GHC 已经在的同一点，所以为什么不使用文章中的代码，看看你是否可以让它更快。

于 2011-06-04T14:45:48.460 回答
5

我担心“数字是一个懒惰的数字流”方法注定比更直接的方法效率低，即使数字的基数很大（比如 2^64 或更多）：

  • 惰性求值意味着最后，您所认为的数字实际上是代表导致它的计算的 DAG。要求多一位数字可能会重新触发此 DAG 的每个节点中的计算。归根结底，你花在家务上的时间比计算上的时间多得多。

  • 您可能无法使用更复杂的算法进行基本计算。例如，乘法的 FFT 方法显然是没有问题的。

  • 这并不意味着算法会很简单。考虑一下如何处理当前结果 99999 的加法。您需要准备好为所有这 9 个进位。现在尝试考虑如何进行乘法运算。具有惰性表达的语言可能有助于表达它，但是你会因为第一个问题而变得更加困难；我很高兴得知编译器能够针对它进行优化，但我担心它们不是。

于 2011-06-04T13:42:19.377 回答