相关疑难解决方法(0)

对于在32位和64位程序(在Visual C++中)都能工作的64位整数,我能够进行乘法除法运算的最准确方法是什么？(如果溢出,我需要结果mod 2 ^64.)

(我正在寻找类似MulDiv64的东西,除了这个使用内联汇编,它只适用于32位程序.)

显然,可以投射到double后面,但是我想知道是否有更准确的方法并不太复杂.(即我不是在寻找任意精度的算术库!)

以char字节为单位的整数类型(或任何类型)的大小很容易计算为sizeof(type).一个常见的习惯用法是乘以CHAR_BIT找到该类型占用的位数,但是在使用填充位的实现中,这将不等于值位的宽度.更糟糕的是,代码如下:

x>>CHAR_BIT*sizeof(type)-1

如果CHAR_BIT*sizeof(type)大于实际宽度,实际上可能有未定义的行为type.

为简单起见,我们假设我们的类型是无符号的.那么宽度type是ceil(log2((type)-1).有没有办法将此值计算为常量表达式？

我的程序经常需要执行以下计算：

鉴于：

• N是32位整数
• D是32位整数
• abs（N）<= abs（D）
• D！= 0
• X是任意值的32位整数

找：

• X * N / D为四舍五入的整数，X缩放为N / D（即10 * 2/3 = 7）

显然我可以直接使用r=x*n/d，但经常会从中溢出x*n。如果我改为这样做，r=x*(n/d)则由于整数除法会除去小数部分，因此我只会得到0或x。然后有，r=x*(float(n)/d)但在这种情况下我不能使用浮点数。

精度会很高，但并不像速度和决定性功能那么关键（总是在给定相同输入的情况下返回相同的值）。

N和D当前已签名，但如果有帮助，我可以解决它们始终未签名的问题。

可以使用任何X值（以及N和D，只要N <= D）的泛型函数是理想的，因为此操作以各种不同的方式使用，但是我也有一个特殊的情况，其中X的值是已知的保持2的幂（准确地说是2048），并且加快特定的调用速度将是一个很大的帮助。

目前，我正在使用64位乘法和除法来完成此操作，以避免溢出（本质上是，int multByProperFraction(int x, int n, int d) { return (__int64)x * n / d; }但是有一些断言和多余的位数摆弄而不是舍入）。

不幸的是，我的探查器报告64位除法函数占用了过多的CPU（这是一个32位应用程序）。我尝试减少执行此计算的频率，但用尽了很多方法，因此，即使有可能，我也在尝试找出一种更快的方法。在X的常数为2048的特定情况下，我使用了移位而不是乘法，但这并没有太大帮助。

我需要做以下算术:

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的算法中) .

优化和测试会有更多的迭代,但在这一点上,我认为我必须接受这个答案是最好的.

我的问题仅限于 256 位无符号整数。

我有一个值x，我需要按比率对其进行除垢n / d，其中n < d。

简单的解决方案当然是x * n / d，但问题是x * n可能会溢出。

我正在寻找任何可能有助于获得尽可能准确的结果的算术技巧。

在计算之前将每个 和 除以n并d不能保证成功。gcd(n, d)x * n / d

我可以使用任何流程（迭代或其他）来解决这个问题吗？

请注意，我愿意选择不准确的解决方案，但我需要能够估计错误。

我有一个C函数:

int64_t fn(int64_t a, int32_t b, int32_t c, int32_t d)
{
    /* should return (a * b * c)/d */   
}

a可能接近INT64_MAX,但最终结果不会溢出,例如,如果b = 1,c = d = 40.但是,我无法弄清楚如何计算这个以便我永远不会丢失数据舍入(通过先进行除法)或中间结果溢出.

如果我可以访问足够大的数据类型以适应a,b和c的整个产品,我只会在该类型中进行数学计算然后截断,但有没有一些方法可以在没有大整数的情况下执行此操作？