小编Sim*_*n32的帖子

编译器: MinGW/GCC
问题:不允许使用GPL/LGPL代码(GMP或任何bignum库,对于这个问题来说太过分了,因为我已经实现了这个类).

我构建了自己的128位固定大小的整数类(用于游戏引擎,但可以推广到任何用例),我发现当前乘法和除法运算的性能非常糟糕(是的,我有时间,见下文),我想改进(或改变)执行低级数字运算的算法.

当涉及乘法和除法运算符时,与几乎所有其他类似的运算符相比,它们是无法忍受的.

这些是相对于我自己的计算机的近似测量:

Raw times as defined by QueryPerformanceFrequency:
1/60sec          31080833u
Addition:              ~8u
Subtraction:           ~8u
Multiplication:      ~546u
Division:           ~4760u (with maximum bit count)

正如您所看到的,只是进行乘法比加或减慢很多倍.除法比乘法慢10倍.

我想提高这两个运算符的速度,因为每帧可能会进行非常多的计算(点积,各种碰撞检测方法等).

结构(方法省略)看起来有点像:

class uint128_t
{
    public:
        unsigned long int dw3, dw2, dw1, dw0;
  //...
}

乘法目前使用典型的长乘法方法(在汇编中使我可以捕获EDX输出)同时忽略超出范围的单词(也就是说,mull与16相比,我只做10次).

除法使用移位 - 减法算法(速度取决于操作数的位数).但是,它不是在装配中完成的.我发现有点太难以集合并决定让编译器优化它.

我已经谷歌了几天看着描述算法的页面,例如Karatsuba乘法,高基数除法和牛顿拉普森分部,但数学符号有点太过分了.我想使用其中一些高级方法来加速我的代码,但我必须首先将"希腊语"翻译成可理解的东西.

对于那些可能认为我的努力"过早优化"的人; 我认为这个代码是一个瓶颈,因为非常基本的数学运算本身变得很慢.我可以在更高级别的代码上忽略这种类型的优化,但是这个代码将被调用/使用到足够重要.

我想建议我应该使用哪种算法来改进乘法和除法(如果可能的话),以及关于建议算法如何工作的基本(希望易于理解)解释将受到高度赞赏.

编辑:乘以改进

我能够通过将代码内联到operator*=来改进乘法运算,并且它似乎尽可能快.

Updated raw times:
1/60sec          31080833u
Addition:              ~8u
Subtraction: …