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

Question

使用方案我需要使用以下功能.(所有args都是自然数[0,inf))

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

但是,此功能经常被调用,并且表现不佳(速度快).是否有更有效的方法来实现所需的行为(num和denom的整数除法,如果denom为零则返回安全值)？

注意,我正在使用Chez Scheme,但是这个用于只导入rnrs的库,而不是完整的Chez.

Answer 1

为获得最佳性能,您需要尽可能接近硅片.添加这样的安全检查不会这样做,除非他们通过方案系统及时编译成超高效的机器代码.

我看到两个选择.一种是在C(或程序集)中创建本机(即外部)实现并调用它.这可能与将其打包为lambda无法兼容,但同样,lambdas的动态特性导致符号效率,但不一定是运行时效率.(除了函数指针之外,有一个原因是在C中不存在lambda表达式,尽管它已经存在很多年了.)如果你走这条路线,最好退后一步,看看更大的处理是哪个safe-div是一部分应该是原生的.如果围绕它的所有东西仍然很慢,那么加速循环中心的分割是没有意义的.

假设预计零除零很少,另一种方法是使用div并希望它的实现很快.是的,这可以导致除以零,但是当谈到速度时,有时候请求宽恕比要求许可更好.换句话说,跳过分割前的检查,然后就可以了.如果失败,方案运行时应该捕获除零错误,并且可以为它安装异常处理程序.这导致异常情况下的代码更慢,而正常情况下代码更快.希望这种权衡取得成功.

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