1adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/* 2adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Licensed to the Apache Software Foundation (ASF) under one or more 3adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * contributor license agreements. See the NOTICE file distributed with 4adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * this work for additional information regarding copyright ownership. 5adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * The ASF licenses this file to You under the Apache License, Version 2.0 6adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * (the "License"); you may not use this file except in compliance with 7adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the License. You may obtain a copy of the License at 8adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 9adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * http://www.apache.org/licenses/LICENSE-2.0 10adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * 11adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Unless required by applicable law or agreed to in writing, software 12adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * distributed under the License is distributed on an "AS IS" BASIS, 13adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 14adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * See the License for the specific language governing permissions and 15adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * limitations under the License. 16adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 17adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 18adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectpackage java.math; 19adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 20adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.IOException; 21adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectInputStream; 22adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.ObjectOutputStream; 23adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Projectimport java.io.Serializable; 247365de1056414750d0a7d1fdd26025fd247f0d04Jesse Wilsonimport java.util.Random; 25adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 26adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project/** 27995e3c8d0f5dc43bc8ba5f305d1525210caaf796Elliott Hughes * An immutable arbitrary-precision signed integer. 28fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 29fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <h3>Fast Cryptography</h3> 30fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * This implementation is efficient for operations traditionally used in 31fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * cryptography, such as the generation of large prime numbers and computation 32fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * of the modular inverse. 33fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 34fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <h3>Slow Two's Complement Bitwise Operations</h3> 35fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * This API includes operations for bitwise operations in two's complement 36fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * representation. Two's complement is not the internal representation used by 37fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * this implementation, so such methods may be inefficient. Use {@link 38fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * java.util.BitSet} for high-performance bitwise operations on 39fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * arbitrarily-large sequences of bits. 40adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 41fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilsonpublic class BigInteger extends Number 42fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson implements Comparable<BigInteger>, Serializable { 43adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 44adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** This is the serialVersionUID used by the sun implementation. */ 45adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private static final long serialVersionUID = -8287574255936472291L; 46adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 47fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson private transient BigInt bigInt; 48adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 49fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson private transient boolean nativeIsValid = false; 50adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 51fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson private transient boolean javaIsValid = false; 52adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 53adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** The magnitude of this in the little-endian representation. */ 54fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson transient int[] digits; 55adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 56fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson /** 57fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * The length of this in measured in ints. Can be less than 58fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * digits.length(). 59fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson */ 60adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project transient int numberLength; 61adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 62adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** The sign of this. */ 63adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project transient int sign; 64adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 65fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson /** The {@code BigInteger} constant 0. */ 66adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public static final BigInteger ZERO = new BigInteger(0, 0); 67adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 68fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson /** The {@code BigInteger} constant 1. */ 69adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public static final BigInteger ONE = new BigInteger(1, 1); 70adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 71fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson /** The {@code BigInteger} constant 10. */ 72adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public static final BigInteger TEN = new BigInteger(1, 10); 73adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 74adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** The {@code BigInteger} constant -1. */ 75adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static final BigInteger MINUS_ONE = new BigInteger(-1, 1); 76adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 77adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** All the {@code BigInteger} numbers in the range [0,10] are cached. */ 78adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project static final BigInteger[] SMALL_VALUES = { ZERO, ONE, new BigInteger(1, 2), 79adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project new BigInteger(1, 3), new BigInteger(1, 4), new BigInteger(1, 5), 80adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project new BigInteger(1, 6), new BigInteger(1, 7), new BigInteger(1, 8), 81adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project new BigInteger(1, 9), TEN }; 82adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 83adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private transient int firstNonzeroDigit = -2; 84f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes 85adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** sign field, used for serialization. */ 86adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private int signum; 87adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 88adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** absolute value field, used for serialization */ 89adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private byte[] magnitude; 90f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes 91adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** Cache for the hash code. */ 92adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private transient int hashCode = 0; 93adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 94fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInteger(BigInt bigInt) { 95e31b37859051d3902e06e4ba384995df7188917fHans Boehm if (bigInt == null || !bigInt.hasNativeBignum()) { 96172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson throw new AssertionError(); 97fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 98fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setBigInt(bigInt); 99adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 100adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 101adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project BigInteger(int sign, long value) { 102fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt bigInt = new BigInt(); 103adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bigInt.putULongInt(value, (sign < 0)); 104fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setBigInt(bigInt); 105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 106adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a number without creating new space. This construct should be 109adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * used only if the three fields of representation are known. 110f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 111fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param sign the sign of the number. 112fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param numberLength the length of the internal array. 113fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param digits a reference of some array created before. 114adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 115adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project BigInteger(int sign, int numberLength, int[] digits) { 116fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setJavaRepresentation(sign, numberLength, digits); 117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 118adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 119adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 120adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a random non-negative {@code BigInteger} instance in the range 121fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * {@code [0, pow(2, numBits)-1]}. 122f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 123fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param numBits maximum length of the new {@code BigInteger} in bits. 124fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param random is the random number generator to be used. 125fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws IllegalArgumentException if {@code numBits} < 0. 126adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 127fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger(int numBits, Random random) { 128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (numBits < 0) { 129172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson throw new IllegalArgumentException("numBits < 0: " + numBits); 130adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (numBits == 0) { 132fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setJavaRepresentation(0, 1, new int[] { 0 }); 133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 134fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int sign = 1; 135fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int numberLength = (numBits + 31) >> 5; 136fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int[] digits = new int[numberLength]; 137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = 0; i < numberLength; i++) { 138fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson digits[i] = random.nextInt(); 139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 140dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes // Clear any extra bits. 141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project digits[numberLength - 1] >>>= (-numBits) & 31; 142fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setJavaRepresentation(sign, numberLength, digits); 143adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 144fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson javaIsValid = true; 145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 146adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 148fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Constructs a random {@code BigInteger} instance in the range {@code [0, 149fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * pow(2, bitLength)-1]} which is probably prime. The probability that the 150dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes * returned {@code BigInteger} is prime is greater than 151dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes * {@code 1 - 1/2<sup>certainty</sup>)}. 152f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 153dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes * <p><b>Note:</b> the {@code Random} argument is ignored if 154dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes * {@code bitLength >= 16}, where this implementation will use OpenSSL's 155dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes * {@code BN_generate_prime_ex} as a source of cryptographically strong pseudo-random numbers. 156fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 157fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param bitLength length of the new {@code BigInteger} in bits. 158fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param certainty tolerated primality uncertainty. 159fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws ArithmeticException if {@code bitLength < 2}. 160fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @see <a href="http://www.openssl.org/docs/crypto/BN_rand.html"> 161fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Specification of random generator used from OpenSSL library</a> 162adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 163dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes public BigInteger(int bitLength, int certainty, Random random) { 164adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (bitLength < 2) { 165172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson throw new ArithmeticException("bitLength < 2: " + bitLength); 166adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 167dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes if (bitLength < 16) { 168dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes // We have to generate short primes ourselves, because OpenSSL bottoms out at 16 bits. 169dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes int candidate; 170dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes do { 171dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes candidate = random.nextInt() & ((1 << bitLength) - 1); 172dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes candidate |= (1 << (bitLength - 1)); // Set top bit. 173dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes if (bitLength > 2) { 174dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes candidate |= 1; // Any prime longer than 2 bits must have the bottom bit set. 175dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes } 176dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes } while (!isSmallPrime(candidate)); 177dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes BigInt prime = new BigInt(); 178dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes prime.putULongInt(candidate, false); 179dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes setBigInt(prime); 180dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes } else { 181dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes // We need a loop here to work around an OpenSSL bug; http://b/8588028. 182dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes do { 183dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes setBigInt(BigInt.generatePrimeDefault(bitLength)); 184dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes } while (bitLength() != bitLength); 185dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes } 186dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes } 187dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes 188dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes private static boolean isSmallPrime(int x) { 189dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes if (x == 2) { 190dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes return true; 191dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes } 192dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes if ((x % 2) == 0) { 193dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes return false; 194dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes } 195dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes final int max = (int) Math.sqrt(x); 196dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes for (int i = 3; i <= max; i += 2) { 197dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes if ((x % i) == 0) { 198dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes return false; 199dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes } 200dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes } 201dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes return true; 202adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 203adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 204adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 205fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Constructs a new {@code BigInteger} by parsing {@code value}. The string 206fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * representation consists of an optional plus or minus sign followed by a 207fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * non-empty sequence of decimal digits. Digits are interpreted as if by 208fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * {@code Character.digit(char,10)}. 209f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 210fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param value string representation of the new {@code BigInteger}. 211fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code value == null}. 212fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NumberFormatException if {@code value} is not a valid 213fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * representation of a {@code BigInteger}. 214adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 215fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger(String value) { 216fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt bigInt = new BigInt(); 217fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson bigInt.putDecString(value); 218fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setBigInt(bigInt); 219adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 220adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 221adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 222fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Constructs a new {@code BigInteger} instance by parsing {@code value}. 223fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * The string representation consists of an optional plus or minus sign 224fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * followed by a non-empty sequence of digits in the specified radix. Digits 225fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * are interpreted as if by {@code Character.digit(char, radix)}. 226f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 227fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param value string representation of the new {@code BigInteger}. 228fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param radix the base to be used for the conversion. 229fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code value == null}. 230fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NumberFormatException if {@code value} is not a valid 231fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * representation of a {@code BigInteger} or if {@code radix < 232fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Character.MIN_RADIX} or {@code radix > Character.MAX_RADIX}. 233adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 234fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger(String value, int radix) { 235fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (value == null) { 236fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson throw new NullPointerException("value == null"); 237adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 238adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (radix == 10) { 239fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt bigInt = new BigInt(); 240fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson bigInt.putDecString(value); 241fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setBigInt(bigInt); 242adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else if (radix == 16) { 243fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt bigInt = new BigInt(); 244fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson bigInt.putHexString(value); 245fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setBigInt(bigInt); 246adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 247fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) { 2481f07ea29bc2d334c55c16227582a7795b8c117c1Elliott Hughes throw new NumberFormatException("Invalid radix: " + radix); 249adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 250172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson if (value.isEmpty()) { 251172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson throw new NumberFormatException("value.isEmpty()"); 252adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 253fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInteger.parseFromString(this, value, radix); 254adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 255adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 256adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 257adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 258fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Constructs a new {@code BigInteger} instance with the given sign and 259fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * magnitude. 260f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 261fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param signum sign of the new {@code BigInteger} (-1 for negative, 0 for 262fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * zero, 1 for positive). 263fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param magnitude magnitude of the new {@code BigInteger} with the most 264fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * significant byte first. 265fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code magnitude == null}. 266fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NumberFormatException if the sign is not one of -1, 0, 1 or if 267fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * the sign is zero and the magnitude contains non-zero entries. 268adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 269adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger(int signum, byte[] magnitude) { 270adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (magnitude == null) { 271fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson throw new NullPointerException("magnitude == null"); 272adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 2738454d3c5b9778ae359d11cd98ed81c589e951d0aElliott Hughes if (signum < -1 || signum > 1) { 2741f07ea29bc2d334c55c16227582a7795b8c117c1Elliott Hughes throw new NumberFormatException("Invalid signum: " + signum); 275adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 276adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (signum == 0) { 277adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (byte element : magnitude) { 278adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (element != 0) { 2798454d3c5b9778ae359d11cd98ed81c589e951d0aElliott Hughes throw new NumberFormatException("signum-magnitude mismatch"); 280adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 281adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 282adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 283fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt bigInt = new BigInt(); 284fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson bigInt.putBigEndian(magnitude, signum < 0); 285fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setBigInt(bigInt); 286adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 287adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 288adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 289adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Constructs a new {@code BigInteger} from the given two's complement 290adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * representation. The most significant byte is the entry at index 0. The 291adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * most significant bit of this entry determines the sign of the new {@code 292fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * BigInteger} instance. The array must be nonempty. 293f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 294fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param value two's complement representation of the new {@code 295fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * BigInteger}. 296fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code value == null}. 297fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NumberFormatException if the length of {@code value} is zero. 298adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 299fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger(byte[] value) { 300fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (value.length == 0) { 301fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson throw new NumberFormatException("value.length == 0"); 302adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 303fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt bigInt = new BigInt(); 304fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson bigInt.putBigEndianTwosComplement(value); 305fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setBigInt(bigInt); 306adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 307adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 308adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 309fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns the internal native representation of this big integer, computing 310fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * it if necessary. 311adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 312fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt getBigInt() { 313fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (nativeIsValid) { 314fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return bigInt; 315fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 316fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson 317fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson synchronized (this) { 318fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (nativeIsValid) { 319fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return bigInt; 320fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 321fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt bigInt = new BigInt(); 322fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson bigInt.putLittleEndianInts(digits, (sign < 0)); 323fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setBigInt(bigInt); 324fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return bigInt; 325fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 326fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 327fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson 328fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson private void setBigInt(BigInt bigInt) { 329fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson this.bigInt = bigInt; 330fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson this.nativeIsValid = true; 331fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 332fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson 333fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson private void setJavaRepresentation(int sign, int numberLength, int[] digits) { 334172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson // decrement numberLength to drop leading zeroes... 335fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson while (numberLength > 0 && digits[--numberLength] == 0) { 336fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson ; 337fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 338172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson // ... and then increment it back because we always drop one too many 339fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (digits[numberLength++] == 0) { 340fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson sign = 0; 341fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 342fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson this.sign = sign; 343fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson this.digits = digits; 344fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson this.numberLength = numberLength; 345fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson this.javaIsValid = true; 346fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 347fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson 348fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson void prepareJavaRepresentation() { 349fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (javaIsValid) { 350fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return; 351fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 352fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson 353fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson synchronized (this) { 354fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (javaIsValid) { 355fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return; 356fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 357fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int sign = bigInt.sign(); 358fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int[] digits = (sign != 0) ? bigInt.littleEndianIntsMagnitude() : new int[] { 0 }; 359fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setJavaRepresentation(sign, digits.length, digits); 360fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 361fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 362fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson 363fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson /** Returns a {@code BigInteger} whose value is equal to {@code value}. */ 364fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public static BigInteger valueOf(long value) { 365fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (value < 0) { 366fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (value != -1) { 367fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return new BigInteger(-1, -value); 368adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 369adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return MINUS_ONE; 37099d9f92a991cbbfc58b103b3f1c114fbac5d1188Elliott Hughes } else if (value < SMALL_VALUES.length) { 371fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return SMALL_VALUES[(int) value]; 372fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } else {// (value > 10) 373fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return new BigInteger(1, value); 374adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 375adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 376adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 377adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 378fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns the two's complement representation of this {@code BigInteger} in 379fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * a byte array. 380adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 381adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public byte[] toByteArray() { 382adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return twosComplement(); 383adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 384adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 385adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 386fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is the absolute value of {@code 387fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * this}. 388adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 389adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger abs() { 390fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt bigInt = getBigInt(); 391fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (bigInt.sign() >= 0) { 392fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return this; 393adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 394fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt a = bigInt.copy(); 395fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson a.setSign(1); 396fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return new BigInteger(a); 397adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 398adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 399adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 400fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is the {@code -this}. 401adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 402adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger negate() { 403fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt bigInt = getBigInt(); 404adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int sign = bigInt.sign(); 405fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (sign == 0) { 406fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return this; 407adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 408fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt a = bigInt.copy(); 409fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson a.setSign(-sign); 410fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return new BigInteger(a); 411adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 412adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 413adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 414fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code this + value}. 415adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 416fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger add(BigInteger value) { 417172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson BigInt lhs = getBigInt(); 418172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson BigInt rhs = value.getBigInt(); 419172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson if (rhs.sign() == 0) { 420fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return this; 421fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 422172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson if (lhs.sign() == 0) { 423fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return value; 424fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 425172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson return new BigInteger(BigInt.addition(lhs, rhs)); 426adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 427adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 428adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 429fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code this - value}. 430adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 431fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger subtract(BigInteger value) { 432172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson BigInt lhs = getBigInt(); 433172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson BigInt rhs = value.getBigInt(); 434172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson if (rhs.sign() == 0) { 435fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return this; 436fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 437172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson return new BigInteger(BigInt.subtraction(lhs, rhs)); 438adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 439adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 440adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 441adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the sign of this {@code BigInteger}. 442f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 443fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @return {@code -1} if {@code this < 0}, {@code 0} if {@code this == 0}, 444fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * {@code 1} if {@code this > 0}. 445adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 446adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int signum() { 447fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (javaIsValid) { 448fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return sign; 449fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 450fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return getBigInt().sign(); 451adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 452adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 453adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 454fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code this >> n}. For 455adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * negative arguments, the result is also negative. The shift distance may 456adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * be negative which means that {@code this} is shifted left. 457fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 458fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method on negative values is 459adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * not recommended as the current implementation is not efficient. 460f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 461fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param n shift distance 462adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code this >> n} if {@code n >= 0}; {@code this << (-n)} 463fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * otherwise 464adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 465adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger shiftRight(int n) { 466adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return shiftLeft(-n); 467adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 468adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 469adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 470fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code this << n}. The 471fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * result is equivalent to {@code this * pow(2, n)} if n >= 0. The shift 472fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * distance may be negative which means that {@code this} is shifted right. 473fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * The result then corresponds to {@code floor(this / pow(2, -n))}. 474fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 475fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method on negative values is 476adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * not recommended as the current implementation is not efficient. 477f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 478fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param n shift distance. 479adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code this << n} if {@code n >= 0}; {@code this >> (-n)}. 480fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * otherwise 481adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 482adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger shiftLeft(int n) { 483fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (n == 0) { 484fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return this; 485fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 486adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int sign = signum(); 487fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (sign == 0) { 488fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return this; 489adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 490fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if ((sign > 0) || (n >= 0)) { 491fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return new BigInteger(BigInt.shift(getBigInt(), n)); 492fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } else { 493adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Negative numbers faking 2's complement: 494adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Not worth optimizing this: 495adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Sticking to Harmony Java implementation. 496adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return BitLevel.shiftRight(this, -n); 497adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 498adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 499adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 5007cf86eabacd844cae438db573d45727d7b3374bfJesse Wilson BigInteger shiftLeftOneBit() { 5017cf86eabacd844cae438db573d45727d7b3374bfJesse Wilson return (signum() == 0) ? this : BitLevel.shiftLeftOneBit(this); 5027cf86eabacd844cae438db573d45727d7b3374bfJesse Wilson } 5037cf86eabacd844cae438db573d45727d7b3374bfJesse Wilson 504adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 505adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the length of the value's two's complement representation without 506adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * leading zeros for positive numbers / without leading ones for negative 507adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * values. 508fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 509fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p>The two's complement representation of {@code this} will be at least 510adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code bitLength() + 1} bits long. 511fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 512fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p>The value will fit into an {@code int} if {@code bitLength() < 32} or 513adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * into a {@code long} if {@code bitLength() < 64}. 514f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 515adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return the length of the minimal two's complement representation for 516fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * {@code this} without the sign bit. 517adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 518adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int bitLength() { 519fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson // Optimization to avoid unnecessary duplicate representation: 520fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (!nativeIsValid && javaIsValid) { 521fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return BitLevel.bitLength(this); 522fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 523fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return getBigInt().bitLength(); 524adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 525adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 526adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 527adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Tests whether the bit at position n in {@code this} is set. The result is 528fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * equivalent to {@code this & pow(2, n) != 0}. 529fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 530fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method is not recommended as 531adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the current implementation is not efficient. 532f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 533fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param n position where the bit in {@code this} has to be inspected. 534fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws ArithmeticException if {@code n < 0}. 535adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 536adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean testBit(int n) { 537adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (n < 0) { 538172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson throw new ArithmeticException("n < 0: " + n); 539adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 540adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int sign = signum(); 541fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (sign > 0 && nativeIsValid && !javaIsValid) { 542fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return getBigInt().isBitSet(n); 543fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } else { 544adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Negative numbers faking 2's complement: 545adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Not worth optimizing this: 546adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Sticking to Harmony Java implementation. 547fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson prepareJavaRepresentation(); 548adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (n == 0) { 549adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return ((digits[0] & 1) != 0); 550adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 551adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int intCount = n >> 5; 552adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (intCount >= numberLength) { 553adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return (sign < 0); 554adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 555adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int digit = digits[intCount]; 556adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project n = (1 << (n & 31)); // int with 1 set to the needed position 557adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (sign < 0) { 558adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int firstNonZeroDigit = getFirstNonzeroDigit(); 559fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (intCount < firstNonZeroDigit) { 560adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 561fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } else if (firstNonZeroDigit == intCount) { 562adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project digit = -digit; 563fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } else { 564adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project digit = ~digit; 565adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 566adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 567adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return ((digit & n) != 0); 568adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 569adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 570adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 571adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 572fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} which has the same binary representation 573adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * as {@code this} but with the bit at position n set. The result is 574fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * equivalent to {@code this | pow(2, n)}. 575fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 576fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method is not recommended as 577adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the current implementation is not efficient. 578f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 579fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param n position where the bit in {@code this} has to be set. 580fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws ArithmeticException if {@code n < 0}. 581adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 582adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger setBit(int n) { 583fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson prepareJavaRepresentation(); 584fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (!testBit(n)) { 585adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return BitLevel.flipBit(this, n); 586fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } else { 587adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return this; 588adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 589adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 590adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 591adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 592fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} which has the same binary representation 593adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * as {@code this} but with the bit at position n cleared. The result is 594fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * equivalent to {@code this & ~pow(2, n)}. 595fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 596fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method is not recommended as 597adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the current implementation is not efficient. 598f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 599fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param n position where the bit in {@code this} has to be cleared. 600fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws ArithmeticException if {@code n < 0}. 601adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 602adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger clearBit(int n) { 603fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson prepareJavaRepresentation(); 604adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (testBit(n)) { 605adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return BitLevel.flipBit(this, n); 606adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 607adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return this; 608adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 609adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 610adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 611adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 612fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} which has the same binary representation 613adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * as {@code this} but with the bit at position n flipped. The result is 614fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * equivalent to {@code this ^ pow(2, n)}. 615fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 616fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method is not recommended as 617adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the current implementation is not efficient. 618f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 619fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param n position where the bit in {@code this} has to be flipped. 620fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws ArithmeticException if {@code n < 0}. 621adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 622adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger flipBit(int n) { 623fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson prepareJavaRepresentation(); 624adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (n < 0) { 625172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson throw new ArithmeticException("n < 0: " + n); 626adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 627adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return BitLevel.flipBit(this, n); 628adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 629adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 630adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 631adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the position of the lowest set bit in the two's complement 632fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * representation of this {@code BigInteger}. If all bits are zero (this==0) 633adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * then -1 is returned as result. 634f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 635fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method is not recommended as 636fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * the current implementation is not efficient. 637adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 638adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int getLowestSetBit() { 639fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson prepareJavaRepresentation(); 640adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (sign == 0) { 641adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return -1; 642adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 643adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // (sign != 0) implies that exists some non zero digit 644adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int i = getFirstNonzeroDigit(); 645adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return ((i << 5) + Integer.numberOfTrailingZeros(digits[i])); 646adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 647adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 648adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 649fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns the number of bits in the two's complement representation of 650fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * {@code this} which differ from the sign bit. If {@code this} is negative, 651fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * the result is equivalent to the number of bits set in the two's 652fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * complement representation of {@code -this - 1}. 653f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 654fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p>Use {@code bitLength(0)} to find the length of the binary value in 655fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * bits. 656fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 657fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method is not recommended as 658fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * the current implementation is not efficient. 659adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 660adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int bitCount() { 661fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson prepareJavaRepresentation(); 662adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return BitLevel.bitCount(this); 663adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 664adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 665adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 666fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code ~this}. The result 667adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * of this operation is {@code -this-1}. 668f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 669fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method is not recommended as 670fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * the current implementation is not efficient. 671adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 672adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger not() { 673fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson this.prepareJavaRepresentation(); 674fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return Logical.not(this); 675adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 676adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 677adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 678fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code this & value}. 679f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 680fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method is not recommended 681fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * as the current implementation is not efficient. 682fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 683fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param value value to be and'ed with {@code this}. 684fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code value == null}. 685adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 686fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger and(BigInteger value) { 687fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson this.prepareJavaRepresentation(); 688fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson value.prepareJavaRepresentation(); 689fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return Logical.and(this, value); 690adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 691adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 692adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 693fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code this | value}. 694fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 695fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method is not recommended as 696adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the current implementation is not efficient. 697f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 698fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param value value to be or'ed with {@code this}. 699fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code value == null}. 700adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 701fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger or(BigInteger value) { 702fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson this.prepareJavaRepresentation(); 703fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson value.prepareJavaRepresentation(); 704fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return Logical.or(this, value); 705adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 706adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 707adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 708fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code this ^ value}. 709fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 710fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method is not recommended as 711adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the current implementation is not efficient. 712f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 713fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param value value to be xor'ed with {@code this} 714fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code value == null} 715adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 716fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger xor(BigInteger value) { 717fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson this.prepareJavaRepresentation(); 718fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson value.prepareJavaRepresentation(); 719fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return Logical.xor(this, value); 720adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 721adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 722adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 723fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code this & ~value}. 724fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Evaluating {@code x.andNot(value)} returns the same result as {@code 725fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * x.and(value.not())}. 726fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * 727fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * <p><b>Implementation Note:</b> Usage of this method is not recommended 728fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * as the current implementation is not efficient. 729f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 730fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param value value to be not'ed and then and'ed with {@code this}. 731fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code value == null}. 732adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 733fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger andNot(BigInteger value) { 734fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson this.prepareJavaRepresentation(); 735fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson value.prepareJavaRepresentation(); 736fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return Logical.andNot(this, value); 737adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 738adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 739adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 740adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns this {@code BigInteger} as an int value. If {@code this} is too 741172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson * big to be represented as an int, then {@code this % (1 << 32)} is 742fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * returned. 743adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 744adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 745adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int intValue() { 746fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (nativeIsValid && bigInt.twosCompFitsIntoBytes(4)) { 747fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return (int) bigInt.longInt(); 748adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 749fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson this.prepareJavaRepresentation(); 750fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return (sign * digits[0]); 751adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 752adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 753adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 754172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson * Returns this {@code BigInteger} as a long value. If {@code this} is too 755172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson * big to be represented as a long, then {@code this % pow(2, 64)} is 756fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * returned. 757adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 758adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 759adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public long longValue() { 760fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (nativeIsValid && bigInt.twosCompFitsIntoBytes(8)) { 761adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return bigInt.longInt(); 762adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 763fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson prepareJavaRepresentation(); 764fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson long value = numberLength > 1 765fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson ? ((long) digits[1]) << 32 | digits[0] & 0xFFFFFFFFL 766fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson : digits[0] & 0xFFFFFFFFL; 767fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return sign * value; 768adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 769adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 770adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 771172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson * Returns this {@code BigInteger} as a float. If {@code this} is too big to 772172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson * be represented as a float, then {@code Float.POSITIVE_INFINITY} or 773172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson * {@code Float.NEGATIVE_INFINITY} is returned. Note that not all integers 774172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson * in the range {@code [-Float.MAX_VALUE, Float.MAX_VALUE]} can be exactly 775172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson * represented as a float. 776adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 777adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 778adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public float floatValue() { 779adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return (float) doubleValue(); 780adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 781adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 782adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 783fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns this {@code BigInteger} as a double. If {@code this} is too big 784172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson * to be represented as a double, then {@code Double.POSITIVE_INFINITY} or 785fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * {@code Double.NEGATIVE_INFINITY} is returned. Note that not all integers 786fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * in the range {@code [-Double.MAX_VALUE, Double.MAX_VALUE]} can be exactly 787fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * represented as a double. 788adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 789adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 790adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public double doubleValue() { 791adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return Conversion.bigInteger2Double(this); 792adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 793adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 794adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 795fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Compares this {@code BigInteger} with {@code value}. Returns {@code -1} 796fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * if {@code this < value}, {@code 0} if {@code this == value} and {@code 1} 797fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * if {@code this > value}, . 798f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 799fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param value value to be compared with {@code this}. 800fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code value == null}. 801adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 802fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public int compareTo(BigInteger value) { 803fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return BigInt.cmp(getBigInt(), value.getBigInt()); 804adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 805adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 806adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 807fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns the minimum of this {@code BigInteger} and {@code value}. 808f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 809fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param value value to be used to compute the minimum with {@code this}. 810fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code value == null}. 811adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 812fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger min(BigInteger value) { 813fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return this.compareTo(value) == -1 ? this : value; 814adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 815adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 816adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 817fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns the maximum of this {@code BigInteger} and {@code value}. 818f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 819fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param value value to be used to compute the maximum with {@code this} 820fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code value == null} 821adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 822fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger max(BigInteger value) { 823fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return this.compareTo(value) == 1 ? this : value; 824adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 825adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 826adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 827adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public int hashCode() { 828071b891828c603fdfb35c922a3873076478dfd33ganxiaolin if (hashCode == 0) { 829071b891828c603fdfb35c922a3873076478dfd33ganxiaolin prepareJavaRepresentation(); 830071b891828c603fdfb35c922a3873076478dfd33ganxiaolin int hash = 0; 831071b891828c603fdfb35c922a3873076478dfd33ganxiaolin for (int i = 0; i < numberLength; ++i) { 832071b891828c603fdfb35c922a3873076478dfd33ganxiaolin hash = hash * 33 + digits[i]; 833071b891828c603fdfb35c922a3873076478dfd33ganxiaolin } 834071b891828c603fdfb35c922a3873076478dfd33ganxiaolin hashCode = hash * sign; 835f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes } 836adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return hashCode; 837adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 838adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 839adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 840adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean equals(Object x) { 841adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (this == x) { 842adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return true; 843adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 844adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (x instanceof BigInteger) { 845fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return this.compareTo((BigInteger) x) == 0; 846adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 847adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return false; 848f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes } 849adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 850adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 851adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a string representation of this {@code BigInteger} in decimal 852adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * form. 853adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 854adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project @Override 855adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public String toString() { 856fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return getBigInt().decString(); 857adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 858adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 859adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 860adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a string containing a string representation of this {@code 861adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * BigInteger} with base radix. If {@code radix < Character.MIN_RADIX} or 862adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * {@code radix > Character.MAX_RADIX} then a decimal representation is 863adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * returned. The characters of the string representation are generated with 864adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * method {@code Character.forDigit}. 865f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 866fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param radix base to be used for the string representation. 867adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 868adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public String toString(int radix) { 869adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (radix == 10) { 870fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return getBigInt().decString(); 871adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 872fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson prepareJavaRepresentation(); 873adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return Conversion.bigInteger2String(this, radix); 874adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 875fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 876adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 877adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 878fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is greatest common divisor 879fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * of {@code this} and {@code value}. If {@code this == 0} and {@code 880fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * value == 0} then zero is returned, otherwise the result is positive. 881f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 882fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param value value with which the greatest common divisor is computed. 883fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code value == null}. 884adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 885fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger gcd(BigInteger value) { 886fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return new BigInteger(BigInt.gcd(getBigInt(), value.getBigInt())); 887adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 888adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 889adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 890fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code this * value}. 891f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 892fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code value == null}. 893adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 894fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson public BigInteger multiply(BigInteger value) { 895fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return new BigInteger(BigInt.product(getBigInt(), value.getBigInt())); 896adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 897adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 898adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 899fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code pow(this, exp)}. 900f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 901fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws ArithmeticException if {@code exp < 0}. 902adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 903adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger pow(int exp) { 904adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (exp < 0) { 905172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson throw new ArithmeticException("exp < 0: " + exp); 906adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 907fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return new BigInteger(BigInt.exp(getBigInt(), exp)); 908adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 909adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 910adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 911fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a two element {@code BigInteger} array containing 912fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * {@code this / divisor} at index 0 and {@code this % divisor} at index 1. 913f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 914fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param divisor value by which {@code this} is divided. 915fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code divisor == null}. 916fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws ArithmeticException if {@code divisor == 0}. 917adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see #divide 918adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @see #remainder 919adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 920adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger[] divideAndRemainder(BigInteger divisor) { 921fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt divisorBigInt = divisor.getBigInt(); 922adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project BigInt quotient = new BigInt(); 923adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project BigInt remainder = new BigInt(); 924fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt.division(getBigInt(), divisorBigInt, quotient, remainder); 925fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return new BigInteger[] {new BigInteger(quotient), new BigInteger(remainder) }; 926adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 927adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 928adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 929fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code this / divisor}. 930f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 931fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param divisor value by which {@code this} is divided. 932adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code this / divisor}. 933fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code divisor == null}. 934fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws ArithmeticException if {@code divisor == 0}. 935adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 936adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger divide(BigInteger divisor) { 937adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project BigInt quotient = new BigInt(); 938fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt.division(getBigInt(), divisor.getBigInt(), quotient, null); 939adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return new BigInteger(quotient); 940adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 941adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 942adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 943fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code this % divisor}. 944adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Regarding signs this methods has the same behavior as the % operator on 945fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * ints: the sign of the remainder is the same as the sign of this. 946f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 947fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param divisor value by which {@code this} is divided. 948fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code divisor == null}. 949fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws ArithmeticException if {@code divisor == 0}. 950adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 951adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger remainder(BigInteger divisor) { 952adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project BigInt remainder = new BigInt(); 953fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt.division(getBigInt(), divisor.getBigInt(), null, remainder); 954adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return new BigInteger(remainder); 955adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 956adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 957adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 958fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code 1/this mod m}. The 959adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * modulus {@code m} must be positive. The result is guaranteed to be in the 960adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * interval {@code [0, m)} (0 inclusive, m exclusive). If {@code this} is 961adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * not relatively prime to m, then an exception is thrown. 962f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 963fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param m the modulus. 964fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code m == null} 965fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws ArithmeticException if {@code m < 0 or} if {@code this} is not 966fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * relatively prime to {@code m} 967adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 968adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger modInverse(BigInteger m) { 969adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (m.signum() <= 0) { 9708454d3c5b9778ae359d11cd98ed81c589e951d0aElliott Hughes throw new ArithmeticException("modulus not positive"); 971adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 972fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return new BigInteger(BigInt.modInverse(getBigInt(), m.getBigInt())); 973adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 974adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 975adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 976fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code 977b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes * pow(this, exponent) mod modulus}. The modulus must be positive. The 978b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes * result is guaranteed to be in the interval {@code [0, modulus)}. 979b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes * If the exponent is negative, then 980b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes * {@code pow(this.modInverse(modulus), -exponent) mod modulus} is computed. 981b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes * The inverse of this only exists if {@code this} is relatively prime to the modulus, 982b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes * otherwise an exception is thrown. 983b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes * 984b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes * @throws NullPointerException if {@code modulus == null} or {@code exponent == null}. 985b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes * @throws ArithmeticException if {@code modulus < 0} or if {@code exponent < 0} and 986b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes * not relatively prime to {@code modulus}. 987b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes */ 988b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes public BigInteger modPow(BigInteger exponent, BigInteger modulus) { 989b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes if (modulus.signum() <= 0) { 990b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes throw new ArithmeticException("modulus.signum() <= 0"); 991b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes } 992b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes int exponentSignum = exponent.signum(); 993b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes if (exponentSignum == 0) { // OpenSSL gets this case wrong; http://b/8574367. 994b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes return ONE.mod(modulus); 995b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes } 996b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes BigInteger base = exponentSignum < 0 ? modInverse(modulus) : this; 997b5ccf74bdea2d417d9e4820945fe3ba1f636a0d2Elliott Hughes return new BigInteger(BigInt.modExp(base.getBigInt(), exponent.getBigInt(), modulus.getBigInt())); 998adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 999adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1000adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1001fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a {@code BigInteger} whose value is {@code this mod m}. The 1002adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * modulus {@code m} must be positive. The result is guaranteed to be in the 1003adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * interval {@code [0, m)} (0 inclusive, m exclusive). The behavior of this 1004adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * function is not equivalent to the behavior of the % operator defined for 1005adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * the built-in {@code int}'s. 1006f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 1007fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param m the modulus. 1008adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code this mod m}. 1009fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws NullPointerException if {@code m == null}. 1010fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws ArithmeticException if {@code m < 0}. 1011adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1012adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger mod(BigInteger m) { 1013adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (m.signum() <= 0) { 1014fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson throw new ArithmeticException("m.signum() <= 0"); 1015adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1016fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return new BigInteger(BigInt.modulus(getBigInt(), m.getBigInt())); 1017adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1018adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1019adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1020adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Tests whether this {@code BigInteger} is probably prime. If {@code true} 1021dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes * is returned, then this is prime with a probability greater than 1022dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes * {@code 1 - 1/2<sup>certainty</sup>)}. If {@code false} is returned, then this 1023fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * is definitely composite. If the argument {@code certainty} <= 0, then 1024fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * this method returns true. 1025f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 1026fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param certainty tolerated primality uncertainty. 1027adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return {@code true}, if {@code this} is probably prime, {@code false} 1028fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * otherwise. 1029adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1030adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public boolean isProbablePrime(int certainty) { 10310fa251a6abd62d73a1a3d1ca74ee0bfc55050d90Elliott Hughes if (certainty <= 0) { 10320fa251a6abd62d73a1a3d1ca74ee0bfc55050d90Elliott Hughes return true; 10330fa251a6abd62d73a1a3d1ca74ee0bfc55050d90Elliott Hughes } 1034fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return getBigInt().isPrime(certainty); 1035adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1036adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1037adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1038adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the smallest integer x > {@code this} which is probably prime as 1039adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * a {@code BigInteger} instance. The probability that the returned {@code 1040dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes * BigInteger} is prime is greater than {@code 1 - 1/2<sup>100</sup>}. 1041f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 10428454d3c5b9778ae359d11cd98ed81c589e951d0aElliott Hughes * @return smallest integer > {@code this} which is probably prime. 1043fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws ArithmeticException if {@code this < 0}. 1044adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1045adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project public BigInteger nextProbablePrime() { 1046adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (sign < 0) { 10478454d3c5b9778ae359d11cd98ed81c589e951d0aElliott Hughes throw new ArithmeticException("sign < 0"); 1048adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1049adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return Primality.nextProbablePrime(this); 1050adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1051adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1052adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1053fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Returns a random positive {@code BigInteger} instance in the range {@code 1054fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * [0, pow(2, bitLength)-1]} which is probably prime. The probability that 1055dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes * the returned {@code BigInteger} is prime is greater than {@code 1 - 1/2<sup>100</sup>)}. 1056f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes * 1057fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @param bitLength length of the new {@code BigInteger} in bits. 1058adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * @return probably prime random {@code BigInteger} instance. 1059fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * @throws IllegalArgumentException if {@code bitLength < 2}. 1060adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1061dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes public static BigInteger probablePrime(int bitLength, Random random) { 1062dd9d07889d37fd2d8d5052b517150ca31ac9d95aElliott Hughes return new BigInteger(bitLength, 100, random); 1063adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1064adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1065adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* Private Methods */ 1066adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1067adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1068adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns the two's complement representation of this BigInteger in a byte 1069adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * array. 1070adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1071adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private byte[] twosComplement() { 1072fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson prepareJavaRepresentation(); 1073fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (this.sign == 0) { 1074fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return new byte[] { 0 }; 1075adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1076adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project BigInteger temp = this; 1077adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int bitLen = bitLength(); 1078adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int iThis = getFirstNonzeroDigit(); 1079adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int bytesLen = (bitLen >> 3) + 1; 1080adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* Puts the little-endian int array representing the magnitude 1081adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * of this BigInteger into the big-endian byte array. */ 1082adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project byte[] bytes = new byte[bytesLen]; 1083adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int firstByteNumber = 0; 1084adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int highBytes; 1085adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int bytesInInteger = 4; 1086adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int hB; 1087adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1088adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (bytesLen - (numberLength << 2) == 1) { 1089adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bytes[0] = (byte) ((sign < 0) ? -1 : 0); 1090adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project highBytes = 4; 1091adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project firstByteNumber++; 1092adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 1093adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project hB = bytesLen & 3; 1094adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project highBytes = (hB == 0) ? 4 : hB; 1095adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1096f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes 1097fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int digitIndex = iThis; 1098adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bytesLen -= iThis << 2; 1099f33eae7e84eb6d3b0f4e86b59605bb3de73009f3Elliott Hughes 1100adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (sign < 0) { 1101fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int digit = -temp.digits[digitIndex]; 1102adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project digitIndex++; 1103fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (digitIndex == numberLength) { 1104adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bytesInInteger = highBytes; 1105adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1106adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = 0; i < bytesInInteger; i++, digit >>= 8) { 1107adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bytes[--bytesLen] = (byte) digit; 1108adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1109fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson while (bytesLen > firstByteNumber) { 1110adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project digit = ~temp.digits[digitIndex]; 1111adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project digitIndex++; 1112fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (digitIndex == numberLength) { 1113adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bytesInInteger = highBytes; 1114adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1115adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = 0; i < bytesInInteger; i++, digit >>= 8) { 1116adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bytes[--bytesLen] = (byte) digit; 1117adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1118adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1119adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 1120adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project while (bytesLen > firstByteNumber) { 1121fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int digit = temp.digits[digitIndex]; 1122adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project digitIndex++; 1123adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (digitIndex == numberLength) { 1124adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bytesInInteger = highBytes; 1125adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1126adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = 0; i < bytesInInteger; i++, digit >>= 8) { 1127adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bytes[--bytesLen] = (byte) digit; 1128adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1129adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1130adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1131adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return bytes; 1132adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1133adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1134adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1135171dc20afe5071d5cbfad7103903bfa2c1f8d00fElliott Hughes static int multiplyByInt(int[] res, int[] a, int aSize, int factor) { 1136adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long carry = 0; 1137adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1138adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = 0; i < aSize; i++) { 1139adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project carry += (a[i] & 0xFFFFFFFFL) * (factor & 0xFFFFFFFFL); 1140fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson res[i] = (int) carry; 1141adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project carry >>>= 32; 1142adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1143fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson return (int) carry; 1144adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1145adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1146171dc20afe5071d5cbfad7103903bfa2c1f8d00fElliott Hughes static int inplaceAdd(int[] a, int aSize, int addend) { 1147adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project long carry = addend & 0xFFFFFFFFL; 1148adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1149adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project for (int i = 0; (carry != 0) && (i < aSize); i++) { 1150adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project carry += a[i] & 0xFFFFFFFFL; 1151adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project a[i] = (int) carry; 1152adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project carry >>= 32; 1153adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1154adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return (int) carry; 1155adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1156adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1157adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** @see BigInteger#BigInteger(String, int) */ 1158fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson private static void parseFromString(BigInteger bi, String value, int radix) { 1159fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int stringLength = value.length(); 1160adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int endChar = stringLength; 1161adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1162fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int sign; 1163fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int startChar; 1164fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (value.charAt(0) == '-') { 1165adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project sign = -1; 1166adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project startChar = 1; 1167adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project stringLength--; 1168adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } else { 1169adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project sign = 1; 1170adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project startChar = 0; 1171adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1172fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson 1173adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /* 1174adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * We use the following algorithm: split a string into portions of n 1175adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * characters and convert each portion to an integer according to the 1176172531a275b620d879126a2d24d0074fe4f084a0Jesse Wilson * radix. Then convert an pow(radix, n) based number to binary using the 1177adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * multiplication method. See D. Knuth, The Art of Computer Programming, 1178adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * vol. 2. 1179adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1180adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1181adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int charsPerInt = Conversion.digitFitInInt[radix]; 1182adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int bigRadixDigitsLength = stringLength / charsPerInt; 1183adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int topChars = stringLength % charsPerInt; 1184adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1185adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project if (topChars != 0) { 1186adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project bigRadixDigitsLength++; 1187adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1188fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int[] digits = new int[bigRadixDigitsLength]; 1189adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Get the maximal power of radix that fits in int 1190adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int bigRadix = Conversion.bigRadices[radix - 2]; 1191adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project // Parse an input string and accumulate the BigInteger's magnitude 1192adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int digitIndex = 0; // index of digits array 1193adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int substrEnd = startChar + ((topChars == 0) ? charsPerInt : topChars); 1194adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1195fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson for (int substrStart = startChar; substrStart < endChar; 1196fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson substrStart = substrEnd, substrEnd = substrStart + charsPerInt) { 1197fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int bigRadixDigit = Integer.parseInt(value.substring(substrStart, substrEnd), radix); 1198fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int newDigit = multiplyByInt(digits, digits, digitIndex, bigRadix); 1199adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project newDigit += inplaceAdd(digits, digitIndex, bigRadixDigit); 1200adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project digits[digitIndex++] = newDigit; 1201adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1202fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int numberLength = digitIndex; 1203fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson bi.setJavaRepresentation(sign, numberLength, digits); 1204adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1205adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1206fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson int getFirstNonzeroDigit() { 1207fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (firstNonzeroDigit == -2) { 1208adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int i; 1209fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson if (this.sign == 0) { 1210adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project i = -1; 1211fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } else { 1212fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson for (i = 0; digits[i] == 0; i++) { 1213adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project ; 1214fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson } 1215adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1216adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project firstNonzeroDigit = i; 1217adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1218adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return firstNonzeroDigit; 1219adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1220adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1221fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson /** 1222adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Returns a copy of the current instance to achieve immutability 1223adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1224adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project BigInteger copy() { 1225fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson prepareJavaRepresentation(); 1226adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project int[] copyDigits = new int[numberLength]; 1227adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project System.arraycopy(digits, 0, copyDigits, 0, numberLength); 1228adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project return new BigInteger(sign, numberLength, copyDigits); 1229adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1230adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1231adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1232fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * Assigns all transient fields upon deserialization of a {@code BigInteger} 1233fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson * instance. 1234adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1235fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson private void readObject(ObjectInputStream in) 1236fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson throws IOException, ClassNotFoundException { 1237adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project in.defaultReadObject(); 1238fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt bigInt = new BigInt(); 1239fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson bigInt.putBigEndian(magnitude, signum < 0); 1240fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson setBigInt(bigInt); 1241adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1242adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project 1243adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project /** 1244adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * Prepares this {@code BigInteger} for serialization, i.e. the 1245adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project * non-transient fields {@code signum} and {@code magnitude} are assigned. 1246adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project */ 1247adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project private void writeObject(ObjectOutputStream out) throws IOException { 1248fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson BigInt bigInt = getBigInt(); 1249adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project signum = bigInt.sign(); 1250fd3f1748b8627e8b6ee907bdaad4cbf2abd7403bJesse Wilson magnitude = bigInt.bigEndianMagnitude(); 1251adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project out.defaultWriteObject(); 1252adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project } 1253adc854b798c1cfe3bfd4c27d68d5cee38ca617daThe Android Open Source Project} 1254