相关疑难解决方法(0)

我正在寻找一种有效(可选的标准,优雅且易于实现)的解决方案来乘以相对较大的数字,并将结果存储为一个或多个整数:

假设我有两个64位整数,如下所示:

uint64_t a = xxx, b = yyy; 

当我这样做时a * b,如何检测操作是否导致溢出,并且在这种情况下将进位存储在某处？

请注意,我不想使用任何大号库,因为我对存储数字的方式有限制.

在C++中,说:

uint64_t i;
uint64_t j;

然后i * j将产生一个uint64_t值为i和之间的乘法的下半部分j,即(i * j) mod 2^64.现在,如果我想要乘法的较高部分怎么办？我知道在使用32位整数时,存在一个汇编指令做类似的事情,但我对汇编并不熟悉,所以我希望得到帮助.

制作以下内容的最有效方法是:

uint64_t k = mulhi(i, j);

对于x64,我可以使用这个:

 {
   uint64_t hi, lo;
  // hi,lo = 64bit x 64bit multiply of c[0] and b[0]

   __asm__("mulq %3\n\t"
    : "=d" (hi),
  "=a" (lo)
    : "%a" (c[0]),
  "rm" (b[0])
    : "cc" );

   a[0] += hi;
   a[1] += lo;
 }

但我想以可移植的方式执行相同的计算.例如,在x86上工作.

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

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

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

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

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

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

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

我需要乘两个符号的64位整数a和b在一起,然后转移(128位)的结果到一个符号的64位整数.最快的方法是什么？

我的64位整数实际上代表具有fmt小数位的定点数.fmt被选择为使得a * b >> fmt不应溢出,例如abs(a) < 64<<fmt和abs(b) < 2<<fmt与fmt==56永远不会溢出64位作为最终结果将是< 128<<fmt,因此适合在一个Int64.

我想这样做的原因是为了快速准确地评估((((c5*x + c4)*x + c3)*x + c2)*x + c1)*x + c0定点格式的形式的五次多项式,每个数字都是带有fmt小数位的带符号的64位定点数.我正在寻找实现这一目标的最有效方法.