Умножение очень длинных целых чисел

В большинстве языков есть функции или библиотеки, которые делают это, обычно называемые библиотекой Bignum (GMP - хороший вариант).

Если вы хотите сделать это сами, я бы сделал это так же, как люди делают длинное умножение на бумаге. Для этого вы можете либо работать со строками, содержащими число, либо делать это в двоичном формате, используя побитовые операции.

Пример:

  45
 x67
 ---
 315
+270
----
 585

Или в двоичном формате:

   101
  x101
  ----
   101
  000
+101
------
 11001

Изменить: сделав это в двоичном формате, я понял, что было бы намного проще (и, конечно, быстрее) кодировать, используя побитовые операции вместо строк, содержащих числа с основанием 10. Я отредактировал свой пример двоичного умножения, чтобы показать шаблон: для каждого 1-битного нижнего числа добавьте верхнее число, сдвинутое влево позицию 1-битного раза к переменной . В конце эта переменная будет содержать продукт.

Чтобы сохранить продукт, вам нужно иметь два 64-битных числа и представить, что одно из них является первыми 64 битами, а другое - вторыми 64 битами продукта. Вам нужно будет написать код, который переносит добавление от бита 63 второго числа к биту 0 первого числа.

Если вы не можете использовать существующую библиотеку bignum, такую ​​как GMP, ознакомьтесь со статьей в Википедии о двоичном умножении на компьютерах . Для этого существует ряд хороших эффективных алгоритмов.

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

Дано A B C D * E F G H (каждый фрагмент 32-битный, всего 128 бит)
Вам нужен выходной массив шириной 9 слов. Установите [0..8] на 0

Вы бы начали с выполнения: H * D + out [8] => 64-битный результат.
Сохраните младшие 32-битные в out [8] и возьмите старшие 32-битные как переносные
Далее: ( H * C) + out [7] + перенос
Опять же, сохраните младшие 32 бита в out [7], используйте старшие 32 бита в качестве переноса
после выполнения H * A + out [4] + переноса , вам нужно продолжать цикл до тех пор, пока не закончится перенос.

Затем повторите с G, F, E.
Для G вы бы начали с out [7] вместо out [8] и так далее.

Наконец, перейдите и преобразуйте большое целое число в цифры (для этого потребуется процедура «разделить большое число на одно слово»)

Да, вы делаете это, используя тип данных, который фактически представляет собой строку цифр (точно так же, как обычная «строка» - это строка символов). Как вы это делаете, сильно зависит от языка. Например, Java использует BigDecimal. На каком языке ты говоришь?

Это часто дают в качестве домашнего задания. Алгоритм, который вы изучили в начальной школе, будет работать. Используйте библиотеку (некоторые из них упоминаются в других сообщениях), если вам это нужно для реального приложения.

Вот мой фрагмент кода на C. Старый добрый метод умножения

char *multiply(char s1[], char s2[]) {
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    int i, j, k = 0, c = 0;
    char *r = (char *) malloc (l1+l2+1); // add one byte for the zero terminating string
    int temp;

    strrev(s1);
    strrev(s2);
    for (i = 0;i <l1+l2; i++) {
        r[i] = 0 + '0';
    }

    for (i = 0; i <l1; i ++) {
        c = 0; k = i;
        for (j = 0; j < l2; j++) {
            temp = get_int(s1[i]) * get_int(s2[j]);
            temp = temp + c + get_int(r[k]);
            c = temp /10;
            r[k] = temp%10 + '0';

            k++;
        }
        if (c!=0) {
            r[k] = c + '0';
            k++;
        }
    }

    r[k] = '\0';
    strrev(r);
    return r;
}