I am doing calculations with BigIntegers that uses a loop that calls multiply() about 100 billion times, and the new object creation from the BigInteger is making it very slow. I was hoping somebody had written or found a MutableBigInteger class. I found the MutableBigInteger in the java.math package, but it is private and when I copy the code into a new class, many errors come up, most of which I don't know how to fix.
What implementations exist of a Java class like MutableBigInteger that allows modifying the value in place?
Like strings, BigInteger objects are immutable. Methods like add , multiply , and pow all return new BigIntegers, rather than modify an existing one. Internally, a BigInteger is implemented using an array of int s, similar to the way a string is implemented using an array of char s.
BigInteger. This version of BigInteger is just a wrapper class for long and its purpose is to only to support a JDK 1.0. 2 version of BigDecimal.
BigInteger provides analogues to all of Java's primitive integer operators, and all relevant methods from java. lang. Math. Additionally, BigInteger provides operations for modular arithmetic, GCD calculation, primality testing, prime generation, bit manipulation, and a few other miscellaneous operations.
BigMul: BigInteger is by far the slowest since it utilizes a naive O(n 2) algorithm, whereas BigInt uses (a parallel) Karatsuba, and Apint probably uses FFT making it the fastest.
Is their any particular reason you cannot use reflection to gain access to the class?
I was able to do so without any problems, here is the code:
public static void main(String[] args) throws Exception {
Constructor<?> constructor = Class.forName("java.math.MutableBigInteger").getDeclaredConstructor(int.class);
constructor.setAccessible(true);
Object x = constructor.newInstance(new Integer(17));
Object y = constructor.newInstance(new Integer(19));
Constructor<?> constructor2 = Class.forName("java.math.MutableBigInteger").getDeclaredConstructor(x.getClass());
constructor2.setAccessible(true);
Object z = constructor.newInstance(new Integer(0));
Object w = constructor.newInstance(new Integer(0));
Method m = x.getClass().getDeclaredMethod("multiply", new Class[] { x.getClass(), x.getClass()});
Method m2 = x.getClass().getDeclaredMethod("mul", new Class[] { int.class, x.getClass()});
m.setAccessible(true);
m2.setAccessible(true);
// Slightly faster than BigInteger
for (int i = 0; i < 200000; i++) {
m.invoke(x, y, z);
w = z;
z = x;
x = w;
}
// Significantly faster than BigInteger and the above loop
for (int i = 0; i < 200000; i++) {
m2.invoke(x, 19, x);
}
BigInteger n17 = new BigInteger("17");
BigInteger n19 = new BigInteger("19");
BigInteger bigX = n17;
// Slowest
for (int i = 0; i < 200000; i++) {
bigX = bigX.multiply(n19);
}
}
Edit: I decided to play around with a bit more, it does appear that java.math.MutableBigInteger doesn't behave exactly as you would expect.
It operates differently when you multiply and it will throw a nice exception when it has to increase the size of the internal array when assigning to itself. Something I guess is fairly expected. Instead I have to swap around the objects so that it is always placing the result into a different MutableBigInteger. After a couple thousand calculations the overhead from reflection becomes negligible. MutableBigInteger does end up pulling ahead and offers increasingly better performance as the number of operations increases. If you use the 'mul' function with an integer primitive as the value to multiply with, the MutableBigInteger runs almost 10 times faster than using BigInteger. I guess it really boils down to what value you need to multiply with. Either way if you ran this calculation "100 billion times" using reflection with MutableBigInteger, it would run faster than BigInteger because there would be "less" memory allocation and it would cache the reflective operations, removing overhead from reflection.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With