就地整数乘法 [英] In-place integer multiplication

问题描述

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

I'm writing a program (in C) in which I try to calculate powers of big numbers in an as short of a period as possible. The numbers I represent as vectors of digits, so all operations have to be written by hand.

如果没有中间结果的所有分配和释放，该程序将更快.是否有用于进行整数乘法的算法，就地?例如，功能

The program would be much faster without all the allocations and deallocations of intermediary results. Is there any algorithm for doing integer multiplication, in-place? For example, the function

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

将a和b的乘积结果放在a内的中，而无需使用中间值.

would place the result of the multiplication of a and b inside of a, without using an intermediary value.

推荐答案

在这里，muln()是 2n (确实是n)，是n = 2n 无符号整数的乘法.您可以将其调整为使用32位或64位数字"而不是8位.为了清楚起见，将模运算符保留下来.

Here, muln() is 2n (really, n) by n = 2n in-place multiplication for unsigned integers. You can adjust it to operate with 32-bit or 64-bit "digits" instead of 8-bit. The modulo operator is left in for clarity.

muln2()通过n = n 就地乘法 n(如此处)，也可以使用8位数字".

muln2() is n by n = n in-place multiplication (as hinted here), also operating on 8-bit "digits".

#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()的一件事是它必须积累更大的中间产品，然后传播更大的进位.

I think this is the best we can do in-place. One thing I don't like about muln2() is that it has to accumulate bigger intermediate products and then propagate a bigger carry.

这篇关于就地整数乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！