进行整数除法的最快方法是什么



使用方案 我需要使用以下函数。(所有参数都是自然数 [0, inf) )

(define safe-div
  (lambda (num denom safe)
    (if (zero? denom)
        safe
        (div num denom))))

但是,此函数经常被调用并且性能不够好(速度明智)。是否有更有效的方法来实现所需的行为(num 和 denom 的整数除法,如果 denom 为零,则返回安全值)?

请注意,我正在使用 Chez 方案,但是它用于仅导入 rnrs 而不是完整 Chez 的库中。

为了获得最佳性能,您需要尽可能靠近硅。添加这样的安全检查是行不通的,除非它们被方案系统及时编译成超高效的机器代码。

我看到两个选项。一种是在C(或汇编)中创建一个本机(即外来)实现并调用它。这可能与将其打包为 lambda 不兼容,但话又说回来,lambda 的动态特性会导致符号效率,但不一定是运行时效率。(除了函数指针之外,lambda 表达式在 C 中不存在是有原因的,尽管它比它早了很多年。如果你走这条路,最好退后一步,看看 safe-div 所属的较大处理是否应该采用本地处理。如果循环中心的一切仍然很慢,那么加快环路中心的除法就没有什么意义了。

假设除以零预计很少见,另一种方法是只使用div并希望其实现速度快。是的,这可能会导致除以零,但是在速度方面,有时乞求原谅比请求许可更好。换句话说,跳过除法前的检查,只做。如果失败,方案运行时应捕获除以零错误,您可以为其安装异常处理程序。这会导致在特殊情况下代码变慢,而在正常情况下会导致代码更快。希望这种权衡能够赢得性能。

最后,根据您要除以的内容,乘以倒数可能比执行实际除法更快。这需要快速的倒数计算或修改早期的计算以直接产生倒数。由于您正在处理整数,因此倒数将存储在定点中,其实质上是 2^32 * 1/denom。将其乘以 num 并向右移动 32 位得到商。这是一场胜利,因为现在越来越多的处理器具有单周期乘法指令,但除法在芯片上的循环中执行,这要慢得多。这对于您的需求来说可能是矫枉过正,但在某些时候可能会有用。

相关内容

  • 没有找到相关文章

最新更新