Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #7549

Re: BitSet vs BigInteger (false Android doc)

Show all headers | View raw

On 02.09.2011 22:34, Patricia Shanahan wrote:
> On 9/2/2011 1:23 PM, Arne Vajhøj 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/

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-02 21:48 +0200
  Re: BitSet vs BigInteger (false Android doc) Arne Vajhøj <arne@vajhoej.dk> - 2011-09-02 16:23 -0400
    Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-02 13:34 -0700
      Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-02 22:51 +0200
        Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-02 18:58 -0700
          Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-03 20:15 +0200
            Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-03 12:37 -0700
              Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-03 22:46 +0200
                Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-03 16:32 -0700
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-04 02:58 +0200
                Re: BitSet vs BigInteger (false Android doc) Arne Vajhøj <arne@vajhoej.dk> - 2011-09-05 19:32 -0400
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 08:58 +0200
                Re: BitSet vs BigInteger (false Android doc) Lew <lewbloch@gmail.com> - 2011-09-06 00:41 -0700
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 11:57 +0200
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 12:12 +0200
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 12:44 +0200
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 12:02 +0200
                Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-06 13:38 -0700
                Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-06 10:33 -0700
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 22:28 +0200
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-06 22:41 +0200
                Re: BitSet vs BigInteger (false Android doc) Patricia Shanahan <pats@acm.org> - 2011-09-06 14:34 -0700
                Re: BitSet vs BigInteger (false Android doc) Lew <lewbloch@gmail.com> - 2011-09-06 14:51 -0700
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-07 00:33 +0200
                Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-07 00:40 +0200
            Re: BitSet vs BigInteger (false Android doc) Arne Vajhøj <arne@vajhoej.dk> - 2011-09-05 19:26 -0400
      Re: BitSet vs BigInteger (false Android doc) Robert Klemme <shortcutter@googlemail.com> - 2011-09-03 17:01 +0200
    Re: BitSet vs BigInteger (false Android doc) Jan Burse <janburse@fastmail.fm> - 2011-09-02 22:49 +0200
      Re: BitSet vs BigInteger (false Android doc) Gene Wirchenko <genew@ocis.net> - 2011-09-02 14:48 -0700
  Re: BitSet vs BigInteger (false Android doc) Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-03 13:54 -0400

csiph-web