Java: Implementing a Unsigned 128bit Integer

Question

first off I should ask:
Does anyone knows of a current implementation 128b UINT for Java?

I need something to hold natural cardinal values. ie: A huge counter.
I know of BigIntegers, which are slow and immutable. A 128b UINT makes sense ...

I was thinking about implementing an OWORD, using a pair of primitive longs.

Overflows would throw an Exception and not Wraparound.

What example sourcecode/blogs should I look to for implementing the workings of this class?

Solution 1

I would use 32 bit integers as the representation, because you need a bigger type (long) to get the extra precision for the carry bit, overflow detection and multiplication. Think of a 32 bit integer as a digit and apply the algorithms from primary school.

Solution 2

Don't tell me that you plan to have 128 static setters and getters, one for each bit??? I'd definitively go for setBit(int index, boolean value) and getBit(int index) as instance methods.

More things you need: a toString() method so you can get a human readable representation (at some point you will want to print the numbers, I think).

Remember that all the ordinal types in java are signed (with the exception of char), so if you plan to use two longs, keep always in mind that the lower part could be problematic for detecting overflows and such... anyway, you will have a 127 bit number unless because the lower part would be treated as a 63 bit unsigned.

Comments

[Tim]

BigInteger is slow when all you need is just a little over 64 bits.. Ran into this problem a year ago and turned out to be 25 times slower than the original long. See this anwer for details: stackoverflow.com/questions/962747/…

[Ira Baxter]

Where did the OP even hint at setters for each bit?

[fortran]

stackoverflow.com/revisions/1096964/list you should take a look before criticizing.

[Ira Baxter]

OK, now I see it. I didn't expect I'd have to read the revisions of a question to understand it; that seems a bit over the top. I've undinged your response.

[fortran]

not to understand it, but don't expect people coming back to change their answers everytime the question is updated (among other things because it's not notified)...

[Ira Baxter]

You can use 64 bit longs just fine ==> twice as fast. A carry out can be determined by changes to the sign bit.

[starblue]

@Ira Baxter I doubt it would be faster. It would be possible but more complicated for addition, but not for multiplication. Java BigInteger uses int[], and I suppose they know what they are doing.

[Ira Baxter]

If you want a very high performance BigInt package, you use the largest wordsize available to your machine for which there are native machine instruction support. Its hard to find a PC these days that isn't 64 bits. I stand by my position: use a long. The algorithms in the BigInt package are probably typical of most multiprecision packages; long should drop relatively easily into place. Additions of large bigints now simply take half as many cycles. Multiplications should be 4x as fast because you only need 1 product instead of 4 half-wide cross products.

[Ira Baxter]

I might soften this a little: you want the largest set of bits for which you can get a double-precision product from two single-precision multiplies. Java ints cast as longs satisfy this in a Java-independent way, which sort of justifies your answer. If you need speed, you'll drop into native machine code. On the x86, the FP unit offers 80 bit precision minimum which implies you might want to choose 40-bit "digits".

[Ira Baxter]

Odd that this is the accepted answer, considering the OP said he didn't want BigInteger.

[Gili]

Tim, your comment contains a broken link.