C++/Haskell中的精确实算法和延迟列表性能

Question

最近，在阅读了本论文和本论文之后，我发现了精确的实运算这一主题。

我发现了一些论文，讨论了使用有符号数字流实现精确算术的方法。对任意精确性使用无限流导致了在函数语言(如Haskell )中使用惰性列表的实用实现。然而，在功能语言中讨论此类实现的论文似乎得出了这样的结论:性能非常差。

现在，我意识到与标准的浮点表示相比，精确、非硬件实现的性能通常会相对较差，但我感兴趣的是用命令式语言(特别是C++)和操作/函数集合(算术操作、三角函数、exp、日志等)提供更高效的实现。

我的问题：有符号的数字/懒散流表示是否固有地缓慢导致了糟糕的性能，还是Haskell？是什么让它变慢了？是否有可能在C++中使用惰性流实现有符号的数字流表示，从而实现(显著)比Haskell更好的性能，或者这是一个徒劳无益的练习？也许重建为迭代？

我知道有两个C++库，RealLib和iRRAM，它们实现了高效的实数计算。然而，这些方法似乎使用了区间算法，将实数表示为收缩的嵌套区间，而这似乎并不像无限流那样“纯粹”(如果您不同意，请纠正我)。但是，这些也许是实现良好效率的唯一途径吗？

任何输入都是非常感谢的！

Answer 1

有符号的数字/懒惰流表示是否固有的速度慢导致了糟糕的性能，还是Haskell？是什么让它变慢了？是否有可能在C++中使用惰性流实现有符号的数字流表示，从而实现(显著)比Haskell更好的性能，或者这是一个徒劳无益的练习？也许重建为迭代？

延迟流最有效地表示为具有延迟功能组件的数据。这是GHC使用的相当高效的Haskell实现的表示，而且无论如何您都需要在C++中使用它。没有专门的“快速”版本的懒惰，你可以写在C++，这还没有尝试在20年的哈斯克尔编译器研究，更多回到阿尔戈尔。

有关如何最有效地实现惰性数据结构的研究的更多详细信息，请参见关于GHC实施的很好的入门文章？。

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

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

我猜后两点。C++版本的懒惰只会是艰苦的工作才能达到GHC已经达到的水平，那么为什么不使用本文中的代码，看看是否可以使它更快。

Answer 2

我担心“数字是一个懒惰的数字流”的方法注定要比一个更直接的方法效率更低，即使数字在一个大的基础上(例如2^64或更多)：

• 懒惰评估意味着，在最后，您所想到的数字实际上是DAG，表示导致它的计算。在这个DAG的每个节点中，要求再多一个数字可能会重新触发计算。在一天结束时，你花在家务上的时间远远多于在计算上的时间。
• 您可能无法使用更复杂的算法来进行基本计算。例如，用FFT方法进行乘法显然是不可能的。
• 这并不意味着算法会很简单。考虑如何在一个加法中处理当前的99999结果。你需要做好准备，为所有这9点做好准备。现在，试着想想如何做乘法。使用惰性表达式的语言可能有助于表达它，但是第一个问题会使您更加困难；我很乐意了解编译器能够为它进行优化，但我担心他们没有。