Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > BitSet vs BigInteger (false Android doc)

Reply
Thread Tools

BitSet vs BigInteger (false Android doc)

 
 
Jan Burse
Guest
Posts: n/a
 
      09-02-2011
Dear All,

Just notice the following note on Android for
java.lang.BigInteger:

Slow Two's Complement Bitwise Operations
This API includes operations for bitwise operations
in two's complement representation. Two's complement
is not the internal representation used by this
implementation, so such methods may be inefficient.
Use BitSet for high-performance bitwise operations
on arbitrarily-large sequences of bits.

But why should be BitSet any faster than BigInteger? Both
BitSet and BigInteger don't use some sparse representation.
They just allocate an array, in the case of BitSet its a long
array, and in the case of BigInteger int array.

The BigInteger sign does not slow down the process in any way.
Its just that the highest int of the BigInteger carries a sign,
which is arbirarily extended to the left. So BigInteger can
represent:

....1xxxxxx

With an infinite sequence of 1's to the left. And then do
boolean operation. But there is practically no overhead
for that. But what I saw is that BitSet is not immutable,
so this could be a reason. But the two's complement is
not an issue, this is just rubbish.

Right?

Bye

 
Reply With Quote
 
 
 
 
Arne Vajhj
Guest
Posts: n/a
 
      09-02-2011
On 9/2/2011 3:48 PM, Jan Burse wrote:
> Just notice the following note on Android for
> java.lang.BigInteger:
>
> Slow Two's Complement Bitwise Operations
> This API includes operations for bitwise operations
> in two's complement representation. Two's complement
> is not the internal representation used by this
> implementation, so such methods may be inefficient.
> Use BitSet for high-performance bitwise operations
> on arbitrarily-large sequences of bits.
>
> But why should be BitSet any faster than BigInteger? Both
> BitSet and BigInteger don't use some sparse representation.
> They just allocate an array, in the case of BitSet its a long
> array, and in the case of BigInteger int array.
>
> The BigInteger sign does not slow down the process in any way.
> Its just that the highest int of the BigInteger carries a sign,
> which is arbirarily extended to the left. So BigInteger can
> represent:
>
> ....1xxxxxx
>
> With an infinite sequence of 1's to the left. And then do
> boolean operation. But there is practically no overhead
> for that. But what I saw is that BitSet is not immutable,
> so this could be a reason. But the two's complement is
> not an issue, this is just rubbish.
>
> Right?


Not necessarily.

If the internal representation does not match
the external representations then some operations could
be expensive due to the conversion between representations
and/or complications for the operation itself.

Arne







 
Reply With Quote
 
 
 
 
Jan Burse
Guest
Posts: n/a
 
      09-02-2011
Patricia Shanahan schrieb:
> Also, they have more freedom of action in implementing BitSet


True, actually I was expecting to see a more clever BitSet,
but in JDK 1.6.0_26 its just this long array.
 
Reply With Quote
 
Gene Wirchenko
Guest
Posts: n/a
 
      09-02-2011
On Fri, 02 Sep 2011 22:49:20 +0200, Jan Burse <(E-Mail Removed)>
wrote:

[snip]

>That BitSet corresponds to the domain of positive integers
>can be seen by the fact that BitSet has no not() operation,
>whereby BigInteger has.


Perhaps the chip has 1's complement integer arithmetic. The
difference would then be in the negative values only.

Sincerely,

Gene Wirchenko
 
Reply With Quote
 
Robert Klemme
Guest
Posts: n/a
 
      09-03-2011
On 02.09.2011 22:34, Patricia Shanahan wrote:
> On 9/2/2011 1:23 PM, Arne Vajhj wrote:
>> On 9/2/2011 3:48 PM, Jan Burse wrote:
>>> Just notice the following note on Android for
>>> java.lang.BigInteger:
>>>
>>> Slow Two's Complement Bitwise Operations
>>> This API includes operations for bitwise operations
>>> in two's complement representation. Two's complement
>>> is not the internal representation used by this
>>> implementation, so such methods may be inefficient.
>>> Use BitSet for high-performance bitwise operations
>>> on arbitrarily-large sequences of bits.
>>>
>>> But why should be BitSet any faster than BigInteger? Both
>>> BitSet and BigInteger don't use some sparse representation.
>>> They just allocate an array, in the case of BitSet its a long
>>> array, and in the case of BigInteger int array.
>>>
>>> The BigInteger sign does not slow down the process in any way.
>>> Its just that the highest int of the BigInteger carries a sign,
>>> which is arbirarily extended to the left. So BigInteger can
>>> represent:
>>>
>>> ....1xxxxxx
>>>
>>> With an infinite sequence of 1's to the left. And then do
>>> boolean operation. But there is practically no overhead
>>> for that. But what I saw is that BitSet is not immutable,
>>> so this could be a reason. But the two's complement is
>>> not an issue, this is just rubbish.
>>>
>>> Right?

>>
>> Not necessarily.
>>
>> If the internal representation does not match
>> the external representations then some operations could
>> be expensive due to the conversion between representations
>> and/or complications for the operation itself.

>
> Also, they have more freedom of action in implementing BitSet, because
> it only needs to do the bit operations. BigInteger has to do the bit
> operations in a way that is consistent with signed integer arithmetic.


And there's more freedom to change the implementation at some point in
the future (or for another platform). BitSet is geared towards bit
operations while BigInteger is geared to math. So any changes done to
any of the two classes will keep the respective purpose of the class in
mind while they might neglect the other purpose which just comes as an
convenient add on.

Kind regards

robert

--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      09-03-2011
On 9/2/2011 3:48 PM, Jan Burse wrote:
> Dear All,
>
> Just notice the following note on Android for
> java.lang.BigInteger:
>
> Slow Two's Complement Bitwise Operations
> This API includes operations for bitwise operations
> in two's complement representation. Two's complement
> is not the internal representation used by this
> implementation, so such methods may be inefficient.
> Use BitSet for high-performance bitwise operations
> on arbitrarily-large sequences of bits.
>
> But why should be BitSet any faster than BigInteger? [...]


Question: Are Android's BitSet and BigInteger similar to Java's?
If not, read no further. But if so:

- Flipping a bit in a BitSet flips it _in situ_, modifying the
value of the original BitSet.

- Flipping a bit in a BigInteger produces a brand-new BigInteger,
leaving the original BigInteger untouched.

So: Flip a thousand bits one by one in a BitSet and you make a
thousand changes to the value of that one BitSet (perhaps the
underlying array gets reallocated sometimes). Flip the same thousand
bits in a BigInteger and you create a thousand new BigInteger instances
with their thousand new underlying arrays. In a crude timing test on
my machine, the difference was noticeable: Flipping a thousand bits a
thousand times took 437 ms with BigInteger, 16 ms with BitSet. YMMV.

--
Eric Sosman
http://www.velocityreviews.com/forums/(E-Mail Removed)d
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      09-03-2011
Patricia Shanahan schrieb:
> On 9/2/2011 1:51 PM, Jan Burse wrote:
>> Patricia Shanahan schrieb:
>>> Also, they have more freedom of action in implementing BitSet

>>
>> True, actually I was expecting to see a more clever BitSet,
>> but in JDK 1.6.0_26 its just this long array.

>
> Are you looking at the actual Android implementations for the classes?
>
> Patricia


I don't think that Android uses some special BitSet resp. BigInteger,
since then classes are java.*.

But it looks that nevertheless the implementation in JDK and Android are
not verbatim the same:

Here is the Android BitSet XOR:

public void xor(BitSet bs) {
int bsActualLen = bs.getActualArrayLength();
if (bsActualLen > bits.length) {
long[] tempBits = new long[bsActualLen];
System.arraycopy(bs.bits, 0, tempBits, 0,
bs.actualArrayLength);
for (int i = 0; i < actualArrayLength; i++) {
tempBits[i] ^= bits[i];
}
bits = tempBits;
actualArrayLength = bsActualLen;
isLengthActual = !((actualArrayLength > 0) &&
(bits[actualArrayLength - 1] == 0));
} else {
long[] bsBits = bs.bits;
for (int i = 0; i < bsActualLen; i++) {
bits[i] ^= bsBits[i];
}
if (bsActualLen > actualArrayLength) {
actualArrayLength = bsActualLen;
isLengthActual = true;
}
}
needClear();
}

http://www.java2s.com/Open-Source/An...itSet.java.htm

And here is the Oracle JDK BitSet XOR:


public void xor(BitSet set) {
int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);

if (wordsInUse < set.wordsInUse) {
ensureCapacity(set.wordsInUse);
wordsInUse = set.wordsInUse;
}

// Perform logical XOR on words in common
for (int i = 0; i < wordsInCommon; i++)
words[i] ^= set.words[i];

// Copy any remaining words
if (wordsInCommon < set.wordsInUse)
System.arraycopy(set.words, wordsInCommon,
words, wordsInCommon,
set.wordsInUse - wordsInCommon);

recalculateWordsInUse();
checkInvariants();
}



So basically the same representation and algorithm.
The Android seems to stem from Apache Harmony.

http://en.wikipedia.org/wiki/Apache_...in_Android_SDK

Bye
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      09-03-2011
Thanks for pointing to the BigInteger implementation on Android!

Patricia Shanahan schrieb:
> It uses a NativeBN implementation, which appears from various comments
> and fields to be sign-and-magnitude based, not 2's complement. The bit
> manipulation methods use a method prepareJavaRepresentation that I think
> converts to 2's complement.


I don't see how the 1's complement influences the BigInteger performance
when we compare with BitSet. BitSet can only represent what corresponds
to positive numbers in BigInteger.

The prepareJavaRepresentation will only do an array copy, if the java
reprentation is not already cached. And then for example for xor
the fast route will be taken since we have two positive numbers:

static BigInteger xorPositive(BigInteger longer, BigInteger
shorter) {
// PRE: longer and shorter are positive;
// PRE: longer has at least as many digits as shorter
int resLength = longer.numberLength;
int[] resDigits = new int[resLength];
int i = Math.min(longer.getFirstNonzeroDigit(), shorter
.getFirstNonzeroDigit());
for (; i < shorter.numberLength; i++) {
resDigits[i] = longer.digits[i] ^ shorter.digits[i];
}
for (; i < longer.numberLength; i++) {
resDigits[i] = longer.digits[i];
}

return new BigInteger(1, resLength, resDigits);
}


http://www.java2s.com/Open-Source/An...gical.java.htm

Actually the code for negative numbers xor in 1's complement looks
really horrible. But this doesn't mean that it has an inherent
different complexity order.

If I remember well then we have -x = ~x + 1. So there is a potential
carry/borrow. This doesn't change much the loops. In fact you
might compare the not() in 1's complement and 2's complement. The
not() is much faster in 1's complement representation (with 2's
complement semantics).

But still I don't think that the Android comment covers the current
state of affairs. Since it explicitly refers to BitSet, and BitSet
and BigInteger are the same on the common domain of positive integers.

And now seeing Logical, there is a new argument against the comment.
Bit operations on 1's complement need not change the complexity
order.

Bye
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      09-04-2011
Patricia Shanahan schrieb:
>
> Could you explain why you are assuming 1's complement rather than
> sign-and-magnitude?


oops, find replace, I guess it is sign-and-magnitude.

The -x = ~x + 1 is needed to go back and forth from
the absolute magnitude to 2's complement magnitude.

Sorry for the error.

 
Reply With Quote
 
Arne Vajhj
Guest
Posts: n/a
 
      09-05-2011
On 9/3/2011 2:15 PM, Jan Burse wrote:
> Patricia Shanahan schrieb:
>> On 9/2/2011 1:51 PM, Jan Burse wrote:
>>> Patricia Shanahan schrieb:
>>>> Also, they have more freedom of action in implementing BitSet
>>>
>>> True, actually I was expecting to see a more clever BitSet,
>>> but in JDK 1.6.0_26 its just this long array.

>>
>> Are you looking at the actual Android implementations for the classes?

>
> I don't think that Android uses some special BitSet resp. BigInteger,
> since then classes are java.*.


Unless a Java implementation has gotten a license to the SUN/Oracle
implementation source code, then the code should be somewhat different
to avoid copyright infringement.

And given that the Android code is open source, then I think you
should have done as Patricia did - simply checked it.

Arne




 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
bitset<32> and bitset<64> efficiency Ninds C++ 14 12-03-2012 11:02 PM
[ANN] Android Debug Bridge (ADB) Scripting Language For Android(SL4A) convenience library Stef Mientki Python 0 11-27-2011 04:46 PM
Android, Android, Android Lawrence D'Oliveiro NZ Computing 2 05-21-2011 05:06 AM
how to convert "BigInteger" into "Integer"? how to print out a BigInteger binary value? nick Java 1 10-26-2004 02:45 PM
how to convert "BigInteger" into "Integer"? how to print out a BigInteger binary value? nick Java 0 10-26-2004 08:18 AM



Advertisments