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

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

5 голосов
/ 15 мая 2011

В качестве домашнего задания я реализую алгоритм Карацубы и сравниваю его с алгоритмом умножения 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 голосов
/ 15 мая 2011

Результат умножения байта составляет 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
               // ...
           }
1 голос
/ 15 мая 2011

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

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

...