c - 就地整数乘法

我正在编写一个程序(用 C 语言)，我尝试在尽可能短的时间内计算大数的幂。我将数字表示为数字 vector ，因此所有操作都必须手工编写。

如果没有中间结果的所有分配和解除分配，程序会快得多。是否有任何算法可以就地进行整数乘法？例如，函数

void BigInt_Times(BigInt *a, const BigInt *b);

将 a 和 b 相乘的结果放在 a 内，而不使用中间值。

最佳答案

这里，muln() 是 2n (really, n) 乘 n = 2n 无符号整数的原位乘法。您可以调整它以使用 32 位或 64 位“数字”而不是 8 位进行操作。为清楚起见，保留了模运算符。
muln2() 是 n × n = n 就地乘法(如 here 所暗示的)，也对 8 位“数字”进行运算。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>

typedef unsigned char uint8;
typedef unsigned short uint16;
#if UINT_MAX >= 0xFFFFFFFF
typedef unsigned uint32;
#else
typedef unsigned long uint32;
#endif
typedef unsigned uint;

void muln(uint8* dst/* n bytes + n extra bytes for product */,
          const uint8* src/* n bytes */,
          uint n)
{
  uint c1, c2;

  memset(dst + n, 0, n);

  for (c1 = 0; c1 < n; c1++)
  {
    uint8 carry = 0;

    for (c2 = 0; c2 < n; c2++)
    {
      uint16 p = dst[c1] * src[c2] + carry + dst[(c1 + n + c2) % (2 * n)];
      dst[(c1 + n + c2) % (2 * n)] = (uint8)(p & 0xFF);
      carry = (uint8)(p >> 8);
    }

    dst[c1] = carry;
  }

  for (c1 = 0; c1 < n; c1++)
  {
    uint8 t = dst[c1];
    dst[c1] = dst[n + c1];
    dst[n + c1] = t;
  }
}

void muln2(uint8* dst/* n bytes */,
           const uint8* src/* n bytes */,
           uint n)
{
  uint c1, c2;

  if (n >= 0xFFFF) abort();

  for (c1 = n - 1; c1 != ~0u; c1--)
  {
    uint16 s = 0;
    uint32 p = 0; // p must be able to store ceil(log2(n))+2*8 bits

    for (c2 = c1; c2 != ~0u; c2--)
    {
      p += dst[c2] * src[c1 - c2];
    }

    dst[c1] = (uint8)(p & 0xFF);

    for (c2 = c1 + 1; c2 < n; c2++)
    {
      p >>= 8;
      s += dst[c2] + (uint8)(p & 0xFF);
      dst[c2] = (uint8)(s & 0xFF);
      s >>= 8;
    }
  }
}

int main(void)
{
  uint8 a[4] = { 0xFF, 0xFF, 0x00, 0x00 };
  uint8 b[2] = { 0xFF, 0xFF };

  printf("0x%02X%02X * 0x%02X%02X = ", a[1], a[0], b[1], b[0]);
  muln(a, b, 2);
  printf("0x%02X%02X%02X%02X\n", a[3], a[2], a[1], a[0]);

  a[0] = -2; a[1] = -1;
  b[0] = -3; b[1] = -1;
  printf("0x%02X%02X * 0x%02X%02X = ", a[1], a[0], b[1], b[0]);
  muln2(a, b, 2);
  printf("0x%02X%02X\n", a[1], a[0]);

  return 0;
}

输出:

0xFFFF * 0xFFFF = 0xFFFE0001
0xFFFE * 0xFFFD = 0x0006

我认为这是我们可以就地做的最好的事情。我不喜欢 muln2() 的一件事是它必须积累更大的中间产品，然后传播更大的进位。

关于c - 就地整数乘法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/8408139/