Реализация умножения BigInteger... с нуля (и убедиться, что это O(n^2))

В качестве домашней работы я реализую алгоритм Карацубы и сравниваю его с алгоритмом умножения O(n^2) в начальной школе для больших целых чисел.

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

Ну, я застрял здесь... при использовании оператора * я не знаю, как бы я обнаружил / исправил, если число переполняет байтовое умножение или добавляет перенос. Есть идеи?

public static BigInteger simpleMultiply(BigInteger x, BigInteger y){

        //BigInteger result = x.multiply(y);

        byte [] xByteArray = x.toByteArray();
        byte [] yByteArray = y.toByteArray();

        int resultSize = xByteArray.length*yByteArray.length;

        byte [][] rowsAndColumns = new byte[resultSize][resultSize];

        for (int i =0; i<xByteArray.length;i++)
           for (int j=0; j<yByteArray.length;j++){


               rowsAndColumns[i][j] = (byte )(xByteArray[i] * yByteArray[j]); 
               // how would I detect/handle carry or overflow here?               
           }

        return null;
    }
Источник

2 ответа

Решение

Результат умножения байтов составляет 2 байта. Вы должны использовать младший байт как результат и старший бит как перенос (переполнение).

Я бы также посоветовал вам быть осторожным со знаком ваших байтов. Поскольку байты в Java подписаны, вам придется либо использовать только младшие 7 битов, либо преобразовать их в целые числа и исправить знак перед их умножением.

Вы будете хотеть петлю как:

        for (int i =0; i<xByteArray.length;i++)
           for (int j=0; j<yByteArray.length;j++){
               // convert bytes to ints
               int xDigit = xByteArray[i], yDigit = yByteArray[j];
               // convert signed to unsigned
               if (xDigit < 0)
                   xDigit += 256;
               if (yDigit < 0)
                   yDigit += 256;
               // compute result of multiplication
               int result = xDigit * yDigit;
               // capture low order byte
               rowsAndColumns[i][j] = (byte)(result & 0xFF);
               // get overflow (high order byte)
               int overflow = result >> 8;
               // handle overflow here
               // ...
           }
Источник

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

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

d1 = (int) digits[i] //convert to a higher-width number
d2 = (int) digits[j]
product = d1*d2  //ints can handle up to around 2^32. Shouldn't overflow w/ 256*256
result = product % 256
carry  = product / 256

Вы могли бы придумать и преобразовать деления по степеням двух в битовые операции, но это на самом деле не нужно.

Источник
Другие вопросы по тегам