Re: BitSet vs BigInteger (false Android doc)

Thanks for pointing to the BigInteger implementation on Android!

Patricia Shanahan schrieb:


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