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

Re: BitSet vs BigInteger (false Android doc)

From	Eric Sosman <esosman@ieee-dot-org.invalid>
Newsgroups	comp.lang.java.programmer
Subject	Re: BitSet vs BigInteger (false Android doc)
Date	2011-09-03 13:54 -0400
Organization	A noiseless patient Spider
Message-ID	<j3tpn7$ka8$1@dont-email.me> (permalink)
References	<j3rbtv$d5g$1@news.albasani.net>

Show all headers | View raw

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
esosman@ieee-dot-org.invalid

Back to comp.lang.java.programmer | Previous | Next — Previous 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