Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have two byte arrays that represent unsigned 256-bit values and I want to multiply them resulting into a new value. What is the fastest ways to do this in Java? And are there other factors I should take into account?

This is my current multiply-function:

// two input values
// i.e. each 0x00000000000000000000000000000000000000000000000000000000000000ff
byte[] input1Array = new byte[32];
byte[] input2Array = new byte[32];

BigInteger input1 = new BigInteger(1, input1Array);
BigInteger input2 = new BigInteger(1, input2Array);
BigInteger result = input1.multiply(input2);

byte[] bytes = result.toByteArray();
ByteBuffer data    =  ByteBuffer.allocate(32);
System.arraycopy(bytes, 0, data.array(), 32 - bytes.length, bytes.length);

// expected 0x000000000000000000000000000000000000000000000000000000000000fe01
byte[] resultArray = data.array();

This takes ~1500ms on my PC for 10000000 iterations and something tells me this can be done faster.

share|improve this question
    
Multiplying two 32-byte numbers can produce a 64-byte value. Are the inputs actually limited to 128-bit? –  David Harkness Jun 14 at 18:58
    
The inputs are not limited and the output should overflow to a new unsigned 256-bit value. –  mahler Jun 14 at 21:21
add comment

2 Answers 2

Your code is somewhat hypothetical, in the example you give, it is 0 * 0, which will be pretty fast....

Still, let's put things in to perspective. You are performing 10 million loops in 1.5 seconds. A modern Intel CPU runs at 3.9GHz. In 1.5 seconds, that's about 6billion cycles (5.85 billion or so).

about 6 billion cycles for 10 million loops is about 600 cycles per loop. Now, in that loop, you are:

  1. creating two byte arrays (OK, maybe you reuse those).
  2. creating 2 BigInteger objects
  3. running an add on those BigIntegers and computing a 3rd BigInteger
  4. converting that third big-integer back to an array.
  5. creating a ByteBuffer
  6. copying the array content to the byte buffer
  7. getting the byte buffer's internal array.

That is an amazing amount of work to do in 600 instruction cycles.I would expect the various object creates (three BigIntegers, two arrays, and a Buffer) are the most expensive things to do as they require multiple instructions, allocations/reservations, and registrations in the object creation, including CPU/cache management, etc.

Frankly, what you have is pretty good.

You could reduce the amount of work you are doing by completely removing the ByteBuffer from the last section. This code:

byte[] bytes = result.toByteArray();
ByteBuffer data    =  ByteBuffer.allocate(32);
System.arraycopy(bytes, 0, data.array(), 32 - bytes.length, bytes.length);

// expected 0x000000000000000000000000000000000000000000000000000000000000fe01
byte[] resultArray = data.array();

could instead be:

byte[] bytes = result.toByteArray();
if (bytes.length < 32) {
    byte[] tmp = new byte[32];
    System.arrayCopy(byte, 0, tmp, 32 - bytes.length, bytes.length);
    bytes = tmp;
}

But, what if the sum is more than 32 bytes?

Also, if you are at/near the limits, and you have negative input values, then you may end up with a negative result. I know your code appears to limit the negative impact by forcing a positive sign, but it could 'overflow' the 32 bytes.

share|improve this answer
    
The question is actually multiplying two 0xff values (hard to see with all those leading zeros). –  David Harkness Jun 14 at 19:01
    
Thanks for the detailed response. I do re-use the byte arrays. And I also declared the ByteBuffer as a static re-usable object. As for sums larger than 32 bytes, I want to overflow back at 0. –  mahler Jun 14 at 20:10
    
mahler I think the point is that you could do the same thing with byte[]'s instead of ByteBuffers for a performance boost. –  corsiKa Jun 14 at 22:02
add comment

I'd guess, that the most time-consuming part is the multiplication itself, although maybe not by a large margin. Try to benchmark it in isolation (which might be hard) or use a simple trick: Compute the product twice in another benchmark and subtract the times.

BigInteger uses int[] internally, which means that a product of two 64-element arrays gets computed. Before Java 8, the naive multiplication gets used (meaning 64**2 = 4096 multiplication). Java 8 can do better by switching to am asymptotically faster algorithm, but this happens for bigger arrays only.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.