Объяснение функции BigInteger 'multiplyToLen' - PullRequest
Новая
       11

Объяснение функции BigInteger 'multiplyToLen'

1 голос
/ 21 апреля 2019

Работая над своей собственной целочисленной реализацией, я просмотрел исходный код Java BigInteger для более глубокого понимания алгоритмов умножения и сосредоточился в основном на multiplyToLen().

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

Сначала алгоритм проходит этот первый цикл, где x и y - умножаемые два числа, а z - произведение: 

int xstart = xlen - 1;
int ystart = ylen - 1;

...

for (int j=ystart, k=ystart+1+xstart; j >= 0; j--, k--) {
    long product = (y[j] & LONG_MASK) * (x[xstart] & LONG_MASK) + carry;
    z[k] = (int)product;
    carry = product >>> 32;
}

z[xstart] = (int)carry;

Затем он переходит к следующему циклу.Это кажется намного ближе к алгоритму школьной школы. 

for (int i = xstart-1; i >= 0; i--) {
    carry = 0;
    for (int j=ystart, k=ystart+1+i; j >= 0; j--, k--) {
        long product = (y[j] & LONG_MASK) * (x[i] & LONG_MASK) +
                               (z[k] & LONG_MASK) + carry;
        z[k] = (int)product;
        carry = product >>> 32;
    }

    z[i] = (int)carry;
}

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

Какая часть алгоритма умножения выполняется в первом цикле?

1 Ответ

0 голосов
/ 21 апреля 2019

Первый цикл умножает два целых числа (по одному от каждого BigInteger x и y соответственно), а затем сохраняет младшие 32 бита результатов в массиве результатов z.Старшие 32 бита используются в качестве переноса для следующей старшей пары целых чисел из x и y соответственно

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

Бит, который нужно перемешать с long s и LONG_MASK, предназначен только для обработкицелые числа в виде беззнаковых 32-битных значений (Java обычно не знает целых чисел без знака), переводя их в 64-битные целые числа и затем маскируя младшие 32 бита, чтобы получить 32-битные значения без знака.Результаты 64-битного умножения игнорируют любое переполнение в бите 63. Младшие биты сохраняются ( цикл 1 ) или добавляются ( другие циклы ) к уже вычисленным результатам из предыдущих циклов, найденных вz.Старшие 32 бита используются в качестве переноса для следующей итерации.

Вот как это обычно делается.Мой код Delphi для BigIntegers делает то же самое, и IIRC, который также является алгоритмом, который Кнут показывает в своем «Искусстве компьютерного программирования» (том II).

...