Алгоритм умножения целых чисел с абсолютной точностью - PullRequest
Новая
       38

Алгоритм умножения целых чисел с абсолютной точностью

3 голосов
/ 03 мая 2010

Я пишу небольшую библиотеку bignum для домашнего проекта. Я должен реализовать умножение Карацубы, но перед этим я хотел бы написать простую процедуру умножения.

Я следую руководству Пола Циммермана под названием «Современная компьютерная арифметика», которое свободно доступно в сети .

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

Я понимаю шаг 2, 3, где B ^ j - сдвиг цифр 1, j раз. Но я не понимаю шаг 1 и 3, где у нас есть A * b_j. Как это умножение должно быть выполнено, если умножение Бигнума еще не было определено?

Будет ли операция "*" в этом алгоритме просто методом повторного сложения?

Вот части, которые я написал до сих пор. Я проверил их юнит-тесты, поэтому они выглядят правильными по большей части:

Структура, которую я использую для моего bignum, выглядит следующим образом: 

#define BIGNUM_DIGITS 2048
typedef uint32_t u_hw; // halfword
typedef uint64_t u_w; // word

typedef struct {
    unsigned int sign; // 0 or 1
    unsigned int n_digits;
    u_hw digits[BIGNUM_DIGITS];
} bn;

В настоящее время доступны процедуры: 

bn *bn_add(bn *a, bn *b); // returns a+b as a newly allocated bn
void bn_lshift(bn *b, int d); // shifts d digits to the left, retains sign
int bn_cmp(bn *a, bn *b); // returns 1 if a>b, 0 if a=b, -1 if a<b

Ответы [ 2 ]

2 голосов
/ 03 мая 2010

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

Начиная справа, n0 равно x0 * y0, и вы избавляетесь от переполнения. Теперь n1 ​​- это сумма x1 * y0 и y1 * x0 и предыдущего переполнения, смещенного на размер вашей цифры. Если вы используете 32-разрядные цифры в 64-разрядной математике, это означает, что n0 = low32 (x0 * y0), и вы несете high32 (x0 * y0) в качестве переполнения. Вы можете видеть, что если вы действительно использовали 32-битные цифры, вы не могли бы добавить центральные столбцы, не превышая 64-битные, поэтому вы, вероятно, используете 30- или 31-битные цифры.

Если у вас есть 30 бит на цифру, это означает, что вы можете умножить два 8-значных числа вместе. Сначала напишите этот алгоритм, чтобы принять два небольших буфера с n_digits до 8 и использовать собственную арифметику для арифметики. Затем реализуйте его снова, взяв n_digits произвольного размера и используя первую версию вместе с вашим методом shift и add, чтобы умножать 8x8 порций цифр за раз. 

/*
    X*Y = N

                          x0     y3
                            \   /  
                             \ /   
                              X    
                      x1     /|\     y2
                        \   / | \   /  
                         \ /  |  \ /   
                          X   |   X    
                  x2     /|\  |  /|\     y1
                    \   / | \ | / | \   /  
                     \ /  |  \|/  |  \ /   
                      X   |   X   |   X    
              x3     /|\  |  /|\  |  /|\     y0
                \   / | \ | / | \ | / | \   /
                 \ /  |  \|/  |  \|/  |  \ /
                  V   |   X   |   X   |   V
                  |\  |  /|\  |  /|\  |  /|
                  | \ | / | \ | / | \ | / |
                  |  \|/  |  \|/  |  \|/  |
                  |   V   |   X   |   V   |
                  |   |\  |  /|\  |  /|   |
                  |   | \ | / | \ | / |   |
                  |   |  \|/  |  \|/  |   |
                  |   |   V   |   V   |   |
                  |   |   |\  |  /|   |   |
                  |   |   | \ | / |   |   |
                  |   |   |  \|/  |   |   |
                  |   |   |   V   |   |   |
                  |   |   |   |   |   |   |
              n7  n6  n5  n4  n3  n2  n1  n0
*/
1 голос
/ 03 мая 2010

Чтобы выполнить A * b_j, вам нужно выполнить умножение начальной школы умножения на одну цифру. В итоге вам нужно добавить кучу двузначных продуктов: 

bn *R = ZERO;
for(int i = 0; i < n; i++) {
  bn S = {0, 2};
  S.digits[0] = a[i] * b_j;
  S.digits[1] = (((u_w)a[i]) * b_j) >> 32;  // order depends on endianness
  bn_lshift(S, i);
  R = bn_add(R, S);
}

Конечно, это очень неэффективно.

...