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

Question

Существует ли алгоритм для точного умножения двух произвольно длинных целых чисел? Язык, с которым я работаю, ограничен длиной 64-разрядного целого числа без знака (максимальный размер целого числа 18446744073709551615). На самом деле, я хотел бы иметь возможность сделать это, разбив каждое число, обрабатывая их каким-либо образом, используя 64-разрядные целые числа без знака, и затем собирая их обратно в строку (что решит проблему умножения результата хранение).

Есть идеи?

Answer 1

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

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

Пример:

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

Или в двоичном виде:

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

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

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

Answer 2

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

Answer 3

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

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

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

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

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

Answer 4

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

Answer 5

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

Answer 6

    //Here is a JavaScript version of an Karatsuba Algorithm running with less time than the usual multiplication method
    
    function range(start, stop, step) {
        if (typeof stop == 'undefined') {
            // one param defined
            stop = start;
            start = 0;
        }
        if (typeof step == 'undefined') {
            step = 1;
        }
        if ((step > 0 && start >= stop) || (step < 0 && start <= stop)) {
            return [];
        }
        var result = [];
        for (var i = start; step > 0 ? i < stop : i > stop; i += step) {
            result.push(i);
        }
        return result;
    };
    function zeroPad(numberString, zeros, left = true) {
        //Return the string with zeros added to the left or right.
        for (var i in range(zeros)) {
            if (left)
                numberString = '0' + numberString
            else
                numberString = numberString + '0'
        }
    
        return numberString
    }
    function largeMultiplication(x, y) {
        x = x.toString();
        y = y.toString();
    
        if (x.length == 1 && y.length == 1)
            return parseInt(x) * parseInt(y)
    
        if (x.length < y.length)
            x = zeroPad(x, y.length - x.length);
    
        else
            y = zeroPad(y, x.length - y.length);
    
        n = x.length
        j = Math.floor(n/2);
    
        //for odd digit integers
        if ( n % 2 != 0)
            j += 1    
        var BZeroPadding = n - j
        var AZeroPadding = BZeroPadding * 2
    
        a = parseInt(x.substring(0,j));
        b = parseInt(x.substring(j));
        c = parseInt(y.substring(0,j));
        d = parseInt(y.substring(j));
    
        //recursively calculate
        ac = largeMultiplication(a, c)
        bd = largeMultiplication(b, d)
        k = largeMultiplication(a + b, c + d)
        A = parseInt(zeroPad(ac.toString(), AZeroPadding, false))
        B = parseInt(zeroPad((k - ac - bd).toString(), BZeroPadding, false))
        return A + B + bd
    }
    //testing the function here
    example = largeMultiplication(12, 34)
    console.log(example)

Answer 7

Вот мой фрагмент кода на 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;
}