对于在32位和64位程序(在Visual C++中)都能工作的64位整数,我能够进行乘法除法运算的最准确方法是什么？(如果溢出,我需要结果mod 2 64.)
(我正在寻找类似MulDiv64的东西,除了这个使用内联汇编,它只适用于32位程序.)
显然,可以投射到double后面,但是我想知道是否有更准确的方法并不太复杂.(即我不是在寻找任意精度的算术库!)
我需要做以下算术:
long a,b,c;
long result = a*b/c;
虽然结果保证适合long,但乘法不是,所以它可以溢出.
我试图一步一步地进行(首先乘法再划分),同时通过将中间结果拆分a*b为最大4的大小的int数组来处理溢出(就像BigInteger使用其int[] mag变量一样).
在这里,我被这个部门困住了.我无法理解进行精确划分所需的按位变换.我需要的只是商(不需要余数).
假设的方法是:
public static long divide(int[] dividend, long divisor)
此外,我不考虑使用,BigInteger因为代码的这部分需要快速(我想坚持使用原语和原始数组).
任何帮助将非常感激!
编辑:我不是要BigInteger自己实现整个.我想要做的是比使用泛型更快地解决特定问题(a*b/c哪里a*b可以溢出)BigInteger.
编辑2:如果它可以以一种聪明的方式完成,完全没有溢出,注释中出现了一些提示,那将是理想的,但我仍在寻找一个正确的方法.
更新: 我尝试将BigInteger代码移植到我的特定需求,没有创建对象,并且在第一次迭代中,与使用BigInteger(在我的开发PC上)相比,我的速度提高了约46%.
然后我尝试了一下修改@大卫Eisenstat的解决方案,这给了我〜56%(我跑100_000_000_000随机输入来自Long.MIN_VALUE于Long.MAX_VALUE减少)运行的时间(超过2倍)比较的BigInteger(即〜18%相比,我的适应BigInteger的算法中) .
优化和测试会有更多的迭代,但在这一点上,我认为我必须接受这个答案是最好的.
假设这uint是我的定点平台上最大的整数类型，我有：
uint func(uint a, uint b, uint c);
这需要返回一个很好的近似值a * b / c。
的值c大于 的值a和 的值b。
所以我们肯定知道 的值a * b / c将适合 a uint。
但是，a * b本身的值会溢出 a 的大小uint。
因此，计算 的值的一种方法a * b / c是：
return a / c * b;
甚至：
if (a > b)
return a / c * b;
return b / c * a;
但是， 的值c …