大量的乘法，如何捕捉溢出。-multiplicationoflargenumbers,howtocatchoverflow

8  

A version that also works when a == 0:

当A == 0时也可以使用的版本:

    x = a * b;
    if (a != 0 && x / a != b) {
        // overflow handling
    }

6  

If you need not just to detect overflow but also to capture the carry, you're best off breaking your numbers down into 32-bit parts. The code is a nightmare; what follows is just a sketch:

如果您不仅需要检测溢出，还需要捕捉进位，那么最好将您的数据分解为32位的部分。代码是一场噩梦;接下来的只是一个草图:

#include 

uint64_t mul(uint64_t a, uint64_t b) {
  uint32_t ah = a >> 32;
  uint32_t al = a;  // truncates: now a = al + 2**32 * ah
  uint32_t bh = b >> 32;
  uint32_t bl = b;  // truncates: now b = bl + 2**32 * bh
  // a * b = 2**64 * ah * bh + 2**32 * (ah * bl + bh * al) + al * bl
  uint64_t partial = (uint64_t) al * (uint64_t) bl;
  uint64_t mid1    = (uint64_t) ah * (uint64_t) bl;
  uint64_t mid2    = (uint64_t) al * (uint64_t) bh;
  uint64_t carry   = (uint64_t) ah * (uint64_t) bh;
  // add high parts of mid1 and mid2 to carry
  // add low parts of mid1 and mid2 to partial, carrying
  //    any carry bits into carry...
}

The problem is not just the partial products but the fact that any of the sums can overflow.

问题不只是部分产品，而是任何一个和都可以溢出。

If I had to do this for real, I would write an extended-multiply routine in the local assembly language. That is, for example, multiply two 64-bit integers to get a 128-bit result, which is stored in two 64-bit registers. All reasonable hardware provides this functionality in a single native multiply instruction—it's not just accessible from C.

如果我必须这样做，我将在本地汇编语言中编写一个扩展乘法例程。例如，将两个64位整数相乘得到一个128位的结果，该结果存储在两个64位寄存器中。所有合理的硬件都以单一的本地乘法指令来提供此功能——它不仅可以从C访问。

This is one of those rare cases where the solution that's most elegant and easy to program is actually to use assembly language. But it's certainly not portable :-(

这是一种罕见的情况，其中最优雅、最容易编程的解决方案实际上是使用汇编语言。但它肯定不是便携的:-(

1  

I've been working with this problem this days and I have to say that it has impressed me the number of times I have seen people saying the best way to know if there has been an overflow is to divide the result, thats totally inefficient and unnecessary. The point for this function is that it must be as fast as possible.

我这几天一直在研究这个问题，我不得不说它给我留下了深刻的印象，我看到人们说，最好的方法是知道是否有溢出来划分结果，这是完全没有效率的，没有必要的。这个函数的重点是它必须尽可能快。

There are two options for the overflow detection:

溢出检测有两种选择:

1º- If possible create the result variable twice as big as the multipliers, for example:

1 .如果可能的话，创建一个比乘数大两倍的结果变量，例如:

struct INT32struct {INT16 high, low;};
typedef union
{
  struct INT32struct s;
  INT32 ll;
} INT32union;

INT16 mulFunction(INT16 a, INT16 b)
{
  INT32union result.ll = a * b; //32Bits result
  if(result.s.high > 0) 
      Overflow();
  return (result.s.low)
}

You will know inmediately if there has been an overflow, and the code is the fastest possible without writing it in machine code. Depending on the compiler this code can be improved in machine code.

如果出现溢出，您将立即知道，并且代码是最快的，而不是在机器代码中编写。根据编译器的不同，这段代码可以在机器代码中得到改进。

2º- Is impossible to create a result variable twice as big as the multipliers variable: Then you should play with if conditions to determine the best path. Continuing with the example:

2º-是不可能创建一个结果变量两倍乘数变量:那么你应该玩如果条件来决定最好的路径。继续这个示例:

INT32 mulFunction(INT32 a, INT32 b)
{

  INT32union s_a.ll = abs(a);
  INT32union s_b.ll = abs(b); //32Bits result
  INT32union result;
  if(s_a.s.hi > 0 && s_b.s.hi > 0)
  {
      Overflow();
  }
  else if (s_a.s.hi > 0)
  {
      INT32union res1.ll = s_a.s.hi * s_b.s.lo;
      INT32union res2.ll = s_a.s.lo * s_b.s.lo;
      if (res1.hi == 0)
      {
          result.s.lo = res1.s.lo + res2.s.hi;
          if (result.s.hi == 0)
          {
            result.s.ll = result.s.lo <<16 + res2.s.lo;
            if ((a.s.hi >> 15) ^ (b.s.hi >> 15) == 1)
            {
                result.s.ll = -result.s.ll; 
            }
            return result.s.ll
          }else
          {
             Overflow();
          }
      }else
      {
          Overflow();
      }
  }else if (s_b.s.hi > 0)
{

   //Same code changing a with b

}else 
{
    return (s_a.lo * s_b.lo);
}
}

I hope this code helps you to have a quite efficient program and I hope the code is clear, if not I'll put some coments.

我希望这段代码能帮助您实现一个非常高效的程序，我希望代码是清晰的，如果不是的话，我将会添加一些内容。

best regards.

致以最亲切的问候。

0  

Perhaps the best way to solve this problem is to have a function, which multiplies two UInt64 and results a pair of UInt64, an upper part and a lower part of the UInt128 result. Here is the solution, including a function, which displays the result in hex. I guess you perhaps prefer a C++ solution, but I have a working Swift-Solution which shows, how to manage the problem:

解决这个问题的最好方法也许是拥有一个函数，它可以将两个UInt64相乘，结果是UInt64，一个上半部分和UInt128结果的一个下半部分。这里是解决方案，包括一个函数，它显示了十六进制的结果。我想你可能更喜欢c++的解决方案，但是我有一个工作的快速解决方案，它显示了如何管理这个问题:

func hex128 (_ hi: UInt64, _ lo: UInt64) -> String
{
    var s: String = String(format: "%08X", hi >> 32)
                  + String(format: "%08X", hi & 0xFFFFFFFF)
                  + String(format: "%08X", lo >> 32)
                  + String(format: "%08X", lo & 0xFFFFFFFF)
    return (s)
}

func mul64to128 (_ multiplier: UInt64, _ multiplicand : UInt64)
             -> (result_hi: UInt64, result_lo: UInt64)
{
    let x: UInt64 = multiplier
    let x_lo: UInt64 = (x & 0xffffffff)
    let x_hi: UInt64 = x >> 32

    let y: UInt64 = multiplicand
    let y_lo: UInt64 = (y & 0xffffffff)
    let y_hi: UInt64 = y >> 32

    let mul_lo: UInt64 = (x_lo * y_lo)
    let mul_hi: UInt64 = (x_hi * y_lo) + (mul_lo >> 32)
    let mul_carry: UInt64 = (x_lo * y_hi) + (mul_hi & 0xffffffff)
    let result_hi: UInt64 = (x_hi * y_hi) + (mul_hi >> 32) + (mul_carry >> 32)
    let result_lo: UInt64 = (mul_carry <<32) + (mul_lo & 0xffffffff)

    return (result_hi, result_lo)
}

Here is an example to verify, that the function works:

这里有一个例子来验证，这个函数是工作的:

var c: UInt64 = 0
var d: UInt64 = 0

(c, d) = mul64to128(0x1234567890123456, 0x9876543210987654)
// 0AD77D742CE3C72E45FD10D81D28D038 is the result of the above example
print(hex128(c, d))

(c, d) = mul64to128(0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF)
// FFFFFFFFFFFFFFFE0000000000000001 is the result of the above example
print(hex128(c, d))

0  

Here is a trick for detecting whether multiplication of two unsigned integers overflows.

这里有一个技巧，用来检测两个无符号整数的乘法是否会溢出。

We make the observation that if we multiply an N-bit-wide binary number with an M-bit-wide binary number, the product does not have more than N + M bits.

我们观察到，如果我们将一个N位宽的二进制数乘以一个M-位宽的二进制数，这个乘积就不会有超过N + M位。

For instance, if we are asked to multiply a three-bit number with a twenty-nine bit number, we know that this doesn't overflow thirty-two bits.

例如，如果要求我们将一个3位的数字与一个29位的数字相乘，我们知道这不会溢出32位。

#include 
#include 

int might_be_mul_oflow(unsigned long a, unsigned long b)
{
  if (!a || !b)
    return 0;

  a = a | (a >> 1) | (a >> 2) | (a >> 4) | (a >> 8) | (a >> 16) | (a >> 32);
  b = b | (b >> 1) | (b >> 2) | (b >> 4) | (b >> 8) | (b >> 16) | (b >> 32);

  for (;;) {
    unsigned long na = a <<1;
    if (na <= a)
      break;
    a = na;
  }

  return (a & b) ? 1 : 0;
}

int main(int argc, char **argv)
{
  unsigned long a, b;
  char *endptr;

  if (argc <3) {
    printf("supply two unsigned long integers in C form\n");
    return EXIT_FAILURE;
  }

  a = strtoul(argv[1], &endptr, 0);

  if (*endptr != 0) {
    printf("%s is garbage\n", argv[1]);
    return EXIT_FAILURE;
  }

  b = strtoul(argv[2], &endptr, 0);

  if (*endptr != 0) {
    printf("%s is garbage\n", argv[2]);
    return EXIT_FAILURE;
  }

  if (might_be_mul_oflow(a, b))
    printf("might be multiplication overflow\n");

  {
    unsigned long c = a * b;
    printf("%lu * %lu = %lu\n", a, b, c);
    if (a != 0 && c / a != b)
      printf("confirmed multiplication overflow\n");
  }

  return 0;
}

A smattering of tests: (on 64 bit system):

少量测试:(64位系统):

$ ./uflow 0x3 0x3FFFFFFFFFFFFFFF
3 * 4611686018427387903 = 13835058055282163709

$ ./uflow 0x7 0x3FFFFFFFFFFFFFFF
might be multiplication overflow
7 * 4611686018427387903 = 13835058055282163705
confirmed multiplication overflow

$ ./uflow 0x4 0x3FFFFFFFFFFFFFFF
might be multiplication overflow
4 * 4611686018427387903 = 18446744073709551612

$ ./uflow 0x5 0x3FFFFFFFFFFFFFFF
might be multiplication overflow
5 * 4611686018427387903 = 4611686018427387899
confirmed multiplication overflow

The steps in might_be_mul_oflow are almost certainly slower than just doing the division test, at least on mainstream processors used in desktop workstations, servers and mobile devices. On chips without good division support, it could be useful.

might_be_mul_oflow中的步骤几乎肯定比仅仅进行划分测试要慢，至少在桌面工作站、服务器和移动设备中使用的主流处理器上是如此。在没有良好部门支持的芯片上，它可能是有用的。

It occurs to me that there is another way to do this early rejection test.

我突然想到还有另外一种方法来做这个早期的拒绝测试。

1. We start with a pair of numbers arng and brng which are initialized to 0x7FFF...FFFF and 1.

   我们从一对数字arng和brng开始，它们被初始化为0x7FFF…飞行符和1。

2. If a <= arng and b <= brng we can conclude that there is no overflow.

   如果a <= arng和b <= brng，我们可以得出结论:没有溢出。

3. Otherwise, we shift arng to the right, and shift brng to the left, adding one bit to brng, so that they are 0x3FFF...FFFF and 3.

   否则，我们将arng移到右边，将brng移到左边，向brng中添加一点，以便它们是0x3FFF…飞行符和3。

4. If arng is zero, finish; otherwise repeat at 2.

   如果arng为零，完成;否则重复在2。

The function now looks like:

这个函数现在看起来是这样的:

int might_be_mul_oflow(unsigned long a, unsigned long b)
{
  if (!a || !b)
    return 0;

  {
    unsigned long arng = ULONG_MAX >> 1;
    unsigned long brng = 1;

    while (arng != 0) {
      if (a <= arng && b <= brng)
        return 0;
      arng >>= 1;
      brng <<= 1;
      brng |= 1;
    }

    return 1;
  }
}

0  

If you just want to detect overflow, how about converting to double, doing the multiplication and if

如果你只是想检测溢出，那么转换为double，做乘法和If。

|x| <2^53, convert to int64

| |

|x| <2^63, make the multiplication using int64

| |

otherwise produce whatever error you want?

否则会产生任何你想要的错误?

This seems to work:

这似乎工作:

int64_t safemult(int64_t a, int64_t b) {
  double dx;

  dx = (double)a * (double)b;

  if ( fabs(dx) <(double)9007199254740992 )
    return (int64_t)dx;

  if ( (double)INT64_MAX