Целочисленное умножение на месте

Question

Я пишу программу (на языке C), в которой я пытаюсь вычислить степени больших чисел за максимально короткий промежуток времени. Числа, которые я представляю как векторы цифр, поэтому все операции должны быть написаны от руки.

Программа была бы намного быстрее без всех распределений промежуточных результатов. Есть ли алгоритм для целочисленного умножения, на месте ? Например, функция

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

поместит результат умножения a и b в a, без использования промежуточного значения .

Answer 1

Здесь muln() равно 2n (действительно, n) на n = 2n умножение на месте для целых чисел без знака.Вы можете настроить его для работы с 32-разрядными или 64-разрядными «цифрами» вместо 8-разрядных.Оператор по модулю оставлен для ясности.

muln2() - это n на n = n умножение на месте (как намекнул здесь ), также работающее на 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(), так это то, что он должен накапливать большие промежуточные продукты, а затем распространять больший перенос.

Answer 2

Ну, стандартный алгоритм состоит из умножения каждой цифры (слова) «а» на каждую цифру «б» и суммирования их в соответствующих местах в результате.Таким образом, i-я цифра a входит в каждую цифру от i до i + n результата.Таким образом, чтобы сделать это «на месте», вам нужно вычислить выходные цифры от самых значимых к наименьшим.Это немного сложнее, чем делать это от малейшего к большинству, но не намного ...

Answer 3

Как правило, представления big-int различаются по длине в зависимости от представленного значения; в общем случае результат будет длиннее, чем любой из операндов. В частности, для умножения размер полученного представления примерно равен сумме размеров аргументов.

Если вы уверены, что управление памятью действительно является узким местом для вашей конкретной платформы, вы можете рассмотреть возможность реализации функции умножения, которая обновляет третье значение. С точки зрения вашего прототипа функции в стиле C выше:

void BigInt_Times_Update(const BigInt* a, const BigInt* b, BigInt* target);

Таким образом, вы можете обрабатывать управление памятью точно так же, как это делают контейнеры C ++ std :: vector <>: ваша цель обновления должна перераспределять свои данные кучи только тогда, когда существующий размер слишком мал.

Answer 4

Не похоже, что вам действительно нужен алгоритм. Скорее вам нужно лучше использовать возможности языка.

Почему бы просто не создать ту функцию, которую вы указали в своем ответе? Используйте это и наслаждайтесь! (Скорее всего, функция вернет ссылку на a в качестве результата.)