Implementing BigInteger's multiply...from scratch (and making sure it's O(n^2))

Question

As homework, I'm implementing Karatsuba's algorithm and benchmarking it against a primary-school-style O(n^2) multiplication algorithm on large integers.

I guessed my only choice here was to bring the numbers to their byte array representations and then work them from there.

Well, I'm stuck here... when using the * operator, I don't know how would I detect/correct if the number overflows a byte multiplication or adds a carry. Any ideas?

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;
    }

Two months ago I've written up a [big-number tutorial](http://stackoverflow.com/questions/5318068/very-large-numbers-in-java-without-using-java-math-biginteger/5318896#5318896) here, which also includes a multiplication. It does not use bytes but `int` values (in the range 0 ... 1000000000), which are multiplicated as `long` to avoid overflow. — Paŭlo Ebermann, May 15 '11 at 15:23

Gabe · Accepted Answer · 2011-05-15T04:29:45.617

2

The result of a byte multiplication is 2 bytes. You have to use the low order byte as the result and the high order byte as the carry (overflow).

I would also advise you to be careful of the sign of your bytes. Since bytes in Java are signed, you'll have to either use only the low 7 bits of them or convert them to ints and correct the sign before multiplying them.

You'll want a loop like:

        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
               // ...
           }

edited May 15 '11 at 04:29

answered May 15 '11 at 04:18

Gabe

84,912
12
139
238

What's a low order/high order byte? The low 7 bits of each byte is the low order byte? – andandandand May 15 '11 at 04:30
1

When you multiply 2 individual digits (say, 9 * 9) you get a 2-digit result (81). In this example, the 8 would be the high order digit and the 1 would be the low order digit. If you multiply 2 individual bytes (say, 0xFF * 0xFF), you get a 2-byte result (0xFE01). In this example the 0xFE would be the high order byte and the 0x01 would be the low order byte. – Gabe May 15 '11 at 04:34
could you explain the lines rowsAndColumns[i][j] = (byte)(result & 0xFF); and int overflow = result >> 8;? I'm not familiar with byte arithmetic/shifting and I'd like to understand the logic. – andandandand May 15 '11 at 04:35
If you're unfamiliar with bit arithmetic, I recommend a quick tutorial, such as http://www.cprogramming.com/tutorial/bitwise_operators.html. – Gabe May 15 '11 at 04:43
I don't get how you're handling overflow after assigning the result value to rows and columns, is it supposed to be stored for the next iteration? – andandandand May 15 '11 at 05:00
Yes, the `// handle overflow here` comment is an indication that you are supposed to store it for the next iteration or whatever. – Gabe May 15 '11 at 05:02

score 1 · Answer 2 · answered May 15 '11 at 14:51

1

The best way to avoid overflow is not to have it happen in the first place. Make all your calculations with a higher width numbers to avoid problems.

For example, lets say we have base 256 numbers and each digit is stored as a single unsigned byte.

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

You could be fancy and convert the divisions by powers of two into bit operations, but it isn't really necessary.

answered May 15 '11 at 14:51

hugomg

68,213
24
160
246

this doesn't handle the carry problem. – andandandand May 15 '11 at 20:08
It does, as long as the type you use to do the math (in my example, `int`) is twice as wide as the type used to store the numbers (in the case `bytes`). This is just how in 4-th grade you store numbers with one digit but do the multiplications with two digits. – hugomg May 15 '11 at 20:19

Implementing BigInteger's multiply...from scratch (and making sure it's O(n^2))

2 Answers2