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)

 
 
Arne Vajhj
Guest
Posts: n/a
 
      09-05-2011
On 9/3/2011 4:46 PM, Jan Burse wrote:
> 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.


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


BitSet is not in the domain of integers at all.

The BigInteger API has methods for converting between internal
representation and bytes in two complements. It should be obvious
that at least code that uses that feature will carry overhead
for an implementation not using two;s complement.

Arne

 
Reply With Quote
 
 
 
 
Lew
Guest
Posts: n/a
 
      09-06-2011
Jan Burse wrote:
> Arne Vajhj schrieb:
>> The BigInteger API has methods for converting between internal
>> representation and bytes in two complements. It should be obvious
>> that at least code that uses that feature will carry overhead
>> for an implementation not using two;s complement.

>
> No, the point is that this light handed reasoning does not
> work. Namely because:
>
> - BitSet is not dependent on some two's complement, sign-plus-
> magnitude or one's complement etc.., since these representations
> were invented for negative values. And BitSet does not work
> with an infinitely extended sign bit, which corresponds to
> a negative value. It has no not() operation.


BitSet doesn't represent integer values at all. According to its Javadoc:
"This class implements a vector of bits that grows as needed. Each component of the bit set has a _boolean_ value. The bits of a _BitSet_ are indexed by nonnegative integers. Individual indexed bits can be examined, set, or cleared. One _BitSet_ may be used to modify the contents of another _BitSet_through logical AND, logical inclusive OR, and logical exclusive OR operations.
By default, all bits in the set initially have the value _false_."

As you must be aware, booleans and integers are distinct and incompatible types, never mind vectors of booleans. From the Javadocs it is quite clear that BitSet is not intended to represent any kind of arithmetic type.

The concepts of sign-magnitude, 1s- or 2s-complement, sign, sign extension,and negative and positive values are all equally meaningless and completely irrelevant for BitSet.
\0
Also, BitSet does indeed have a "not" operation, which it calls 'flip()'.
\0
Furthermore, from the remark that "[t]he length of a bit set relates to logical length of a bit set and is defined independently of implementation", we conclude that the implementation doesn't matter as long as it meets the contract.

> - BigInteger is also not dependent for positive values on some
> two's complement, sign-plus-maginitude or one's complement etc..,
> since these presentation were invented for negative values.
>
> So the Android javadoc [sic] comment is false in that it mentions an
> irrelevant aspect of the matter.


Of which comment do you speak? Android's Javadocs for BitSet make no mention of any of the aforementioned irrelevant concepts pertaining to integer types.

Are you referring to Android's documentation for BigInteger, which states, "This API includes operations for bitwise operations in two's complement [sic] 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."?

How is that false? It's obviously factual and correct. The BigInteger APIdoes include operations for two's-complement bitwise operations, no? Two's complement is not the internal representation of BigInteger in Android, is it? Such methods are likely to be inefficient, aren't they? So what's false?

As for relevance, it's rather important in an Android context to be aware of performance considerations, so the need for speed in bitwise operations makes relevant the comment. Clearly.

What's irrelevant is trying to speak of BitSet as if it were an integral type. This is not a mistake the Android Javadocs make. Let's see, now - where did I see that error? I wonder ...

Oh, yeah, the remark, "BitSet and BigInteger are the same on the common domain of positive integers."

--
Lew



 
Reply With Quote
 
 
 
 
Jan Burse
Guest
Posts: n/a
 
      09-06-2011
Lew schrieb:
> Also, BitSet does indeed have a "not" operation, which it calls 'flip()'.


Sorry, but flip() is not the same as not(). Just compare the
signatures:

flip: Domain x Nat -> Domain

flip(x,n) := xor(x,2^n)

not: Domain -> Domain$

not(x) := xor(x,-1)

This is really where the bitwise operations of BigInteger differentiate
from the bitwise operations of BitSet. BitSet does only know a
potentially infinitely extended sign bit of zero. So all the values
seen as bits are:

...0xxxxxxx

So when you do a BitSet operation between two operands of BitSet,
then the shorter operand is extended so that both sizes match,
before the operation is done (not necessary for all operation). And
this extension works by padding with 0.

In BigInteger we can represent two different bitset patterns.
Namely the either a zero extended indefinitely, for positive
numbers, or a one extended indefinitely, for negative numbers.
So all the values in BigInteger seen as bits are:

...0xxxxxxx or
...1xxxxxxx

The BigInteger operations have two pad eiter with 0 or with 1,
depending on the sign of the given operand. The not() is not
available in BitSet because the -1 is not available in BitSet.

But what concerns the Android comment. It is false because
two's complement is not relevant when we compare BitSet and
BigInteger, because two's complement is one way to represent
a negative number:

...1xxxxxxx

And implicitly the Android comment is also false, since it
implies that two's complement is the only way to represent
negative numbers and it is also false, since it implies
that some of negative number representations have a negative
complexity impact on negative number bitwise operations.

Bye
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      09-06-2011
Lew schrieb:
> Oh, yeah, the remark, "BitSet and BigInteger
> are the same on the common domain of positive integers."


No, interestingly new false believes come up right now,
such as confusing flip() and not(). But beware I am
very patient, I can argue with you guys for ages as long
as you keep inventing wrong paraphernalia and are not
able to face a simple mistake in a javadoc.

Maybe this is based on a general assumption that javadocs
are above critique. But I think javadocs can be buggy
in the same way that code can be buggy. They are just
written by someone, and it can be that this someone had
good intentions, but nevertheless something went wrong.

Bye
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      09-06-2011
Jan Burse schrieb:
> ut what concerns the Android comment. It is false because
> two's complement is not relevant when we compare BitSet and
> BigInteger, because two's complement is one way to represent
> a negative number:
>
> ...1xxxxxxx


Lew wrote:
> The concepts of sign-magnitude, 1s- or 2s-complement, sign, sign
> extension, and negative and positive values are all
> equally meaningless and completely irrelevant for BitSet.


At least here you agree that the Android java doc comment
is flawed. But then somehow your abandon your own observations
in favor of the "obvious":

Lew also wrote:
> Are you referring to Android's documentation for BigInteger, which
> states, "This API includes operations for bitwise operations in two's
> complement [sic] 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."?
>
> How is that false? It's obviously factual and correct.


Bye
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      09-06-2011
Jan Burse schrieb:
> And implicitly the Android comment is also false, since it
> implies that two's complement is the only way to represent
> negative numbers and it is also false, since it implies
> that some of negative number representations have a negative
> complexity impact on negative number bitwise operations.


Correction:
And implicitly the Android comment is also false, since it
implies that two's complement is the only way to efficiently
represent negative numbers for a bitwise operations with
two's complement semantic.


That non two's complement representations with two's
complement semantic can also be efficient I have indicated
in a response to Patricia Shanahan. There some implementation
with sign-and-magnitude can also work fast.



Bye
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      09-06-2011
Jan Burse schrieb:
>> - BigInteger is also not dependent for positive values on some
>> two's complement, sign-plus-maginitude or one's complement etc..,
>> since these presentation were invented for negative values.

> ...
>


> import java.math.BigInteger;
> public class BigIntegerTest {
> public static void main(String[] args) {
> BigInteger x = BigInteger.valueOf(3);
> BigInteger y = BigInteger.valueOf(2);
> System.out.println(x.or(y.not()));
> }
> }


Well the above invalidates my claim to some extend. Since you
produced an example where you get a negative number from
bitwise ops on positive numbers.

But from the context of my claim, it should of course also be
clear that I exclude the not() operation. Since I have mentioned
the not() operation many times a special to BigInteger.

If you exclude the not() operation, you will stay in the positive
domain. Also excluding the not() operation makes sense since
you cannot directly translate an example that uses the not()
from BigInteger to BitSet.

You can translate the following special case (use a purely
functional notation, although the BitSet call is in fact an
inline modification of the first operand):

BigInteger: and(x,not(y))
BitSet: andNot(x,y)

But for the following operation, we don't find an equivalent
in BitSet, since we would leave the positive integer domain,
as you have shown:

BigInteger: or(x,not(y))
BitSet: ??

So the Android advice is limited to the cases where you
stay in the positive domain. And in this domain there is
no performance penalty found in any representation schema
that deals with negatives numbers, since we work with positive
numbers only. And in the positive domain the same algorithm
are usually used for BigInteger bitwise operation and for
BitSet operations.

Also in the Android code the same algorithm is used for
BigInteger bitwise operations and for BitSet operations. I
have quoted as an example the xor() code. But since the
Android code internally uses C for the integer operations
and Java for the bitwise operations in BigInteger, a
copy operation is involved that copies from C to Java,
before doing the bitwise operation.

This copying is cached, and of course does not happen
anymore after a couple of bitwise operations, since the
operands are already cached, and the result as well.

Bye

P.S.: BigInteger has also an andNot(), which sends
positive integers to positive integers, I do not exclude
this operation in my claim.
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      09-06-2011
Patricia Shanahan schrieb:
> conversions. The combination of the comment in question and reading the
> code shows that they did not take that path. Instead, they always
> convert for bit manipulation and advise use of BitSet instead.


The Android comment can be corrected as follows:
"It is adviced to use BitSet if only positive bit patterns
come into play and if it is possible to use inline modifications."

But the comment should maybe also include a warning, that using
objects with inline modifications can lead to more programming
errors. Reasons are for example that the objects are now mutable
and thus various side effects can occur. Here is an example:

Hashtable tab = new Hashtable();
BitSet bits = new BitSet();
tab.put(bits,"A");
bits.flip(3);

The above will result in a slightly broken hashtable. Although
the entries in a hashtable do store the hash once it is computed.
But the following code will not work as expected:

Enumerated en=tab.keys();
while (en.hasMoreElements()) {
BitSet bits=en.nextElement();
System.out.println("key="+bits+", value="+tab.get(bits));
}

But I guess you all know about these dangers.

Best Regards

 
Reply With Quote
 
Lew
Guest
Posts: n/a
 
      09-06-2011
Jan Burse wrote:
> Patricia Shanahan schrieb:
>> conversions. The combination of the comment in question and reading the
>> code shows that they did not take that path. Instead, they always
>> convert for bit manipulation and advise use of BitSet instead.

>
> The Android comment can be corrected as follows:
> "It is adviced [sic] to use BitSet if only positive bit patterns
> come into play and if it is possible to use inline modifications."


The Android comment is not incorrect to begin with.

> But the comment should maybe also include a warning, that using
> objects with inline modifications can lead to more programming
> errors. Reasons are for example that the objects are now mutable
> and thus various side effects can occur. Here is an example:
>
> Hashtable tab = new Hashtable();


'Hashtable'? Really?

> BitSet bits = new BitSet();
> tab.put(bits,"A");
> bits.flip(3);
>
> The above will result in a slightly broken hashtable. Although


This is an example of the general principle that a mutable key in a 'Map' can mess things up, if you change the key while the 'Map' holds it. It hardly requires a warning in every mutable class's Javadocs.

> the entries in a hashtable do store the hash once it is computed.
> But the following code will not work as expected:
>
> Enumerated en=tab.keys();


'Enumerated'? Really?

> while (en.hasMoreElements()) {
> BitSet bits=en.nextElement();
> System.out.println("key="+bits+", value="+tab.get(bits));
> }
>
> But I guess you all know about these dangers.


Anyone familiar with the dangers of mutable keys in a 'Map' knows at least something about these dangers.

--
Lew
 
Reply With Quote
 
Jan Burse
Guest
Posts: n/a
 
      09-06-2011
Lew schrieb:
> It hardly requires a warning in every mutable class's Javadocs.


Maybe you have a hearing problem. I didn't say in any instance
to put in every mutable class a warning. Where do you find
that I did say that?

I only thought that when migrating from BitSet to BigInteger
one might un-intentionally break a contract that existed for the
old BigInteger implementation.

So such a warning can be apropriate.

Best Regards
 
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