Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #7553
| From | Jan Burse <janburse@fastmail.fm> |
|---|---|
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: BitSet vs BigInteger (false Android doc) |
| Date | 2011-09-03 22:46 +0200 |
| Organization | albasani.net |
| Message-ID | <j3u3me$k4s$1@news.albasani.net> (permalink) |
| References | (2 earlier) <yJCdnamwfpVooPzTnZ2dnUVZ_umdnZ2d@earthlink.com> <j3rflb$lh6$2@news.albasani.net> <KOmdnWyhfYV_FPzTnZ2dnUVZ_s-dnZ2d@earthlink.com> <j3tqr7$vp8$1@news.albasani.net> <_ZGdna1ucfWYH__TnZ2dnUVZ_oudnZ2d@earthlink.com> |
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/Android/android-core/platform-libcore/java/math/Logical.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
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar
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