提高Java的BigInteger性能
如何提高Java的Big Integer的性能？
例如，这个阶乘程序：
import java.math.*; class Fac { public static void main(String[] args) { BigInteger i = BigInteger.ONE; for(BigInteger z=BigInteger.valueOf(2);z.compareTo(BigInteger.valueOf(99999)) != 0;) { i = i.multiply(z); z = z.add(BigInteger.ONE); } System.out.println( i ); } } 该计划于31.5秒完成
C ++中的位置：
#include #include using namespace std; int main() { mpz_class r; r = 1; for(int z=2;z<99999;++z) { r *= mpz_class(z); } cout << r << endl; }
在1.0秒完成
和Ruby（用于比较）：
puts (2...99999).inject(:*)
完成在4.4秒（Ruby）和JRuby的32.2秒
还有Go（用于比较）：
package main import ( "fmt" "math/big" ) func main() { i := big.NewInt(1); one := big.NewInt(1) for z := big.NewInt(2); z.Cmp(big.NewInt(99999)) < 0; { i.Mul(i,z); z.Add(z,one) } fmt.Println( i ); }
为MulRange完成1.6秒和0.7秒
编辑按要求：
import java.math.*; class F2 { public static void main(String[] args) { BigInteger i = BigInteger.ONE, r = BigInteger.valueOf(2); for(int z=2; z<99999 ; ++z) { i = i.multiply(r); r = r.add(BigInteger.ONE); } System.out.println( i ); } }
运行时间： 31.4秒
对那些仍然认为第一个和第二个java代码不公平的人编辑2 ..
import java.math.*; class F3 { public static void main(String[] args) { BigInteger i = BigInteger.ONE; for(int z=2; z<99999 ; ++z) { i = i.multiply(BigInteger.valueOf(z)); } System.out.println( i ); } }
在31.1秒完成
编辑3 @OldCurmudgeon评论：
import java.math.*; import java.lang.reflect.*; class F4 { public static void main(String[] args) { try { Constructor Bignum = Class.forName("java.math.MutableBigInteger").getDeclaredConstructor(int.class); Bignum.setAccessible(true); Object i = Bignum.newInstance(1); Method m = i.getClass().getDeclaredMethod("mul", new Class[] { int.class, i.getClass()}); m.setAccessible(true); for(int z=2; z<99999 ; ++z) { m.invoke(i, z, i); } System.out.println( i ); } catch(Exception e) { System.err.println(e); } } }
在23.7秒完成
编辑4正如@ Marco13所述，最大的问题是字符串创建不是在BigInteger本身上。
- BigInteger：
3.0秒 - MutableBigInteger hack：
10.1秒 - 字符串创建：~
20秒
计算本身不应该花这么长时间。 但是， 字符串创建可能需要一段时间。
当使用-Xmx1000m -sever启动时，此程序（Kudos to OldCurmudgeon和https://stackoverflow.com/a/8583188/823393 ）在Core -Xmx1000m -sever ，Java 7/21上大约需要3.9秒：
import java.lang.reflect.Constructor; import java.lang.reflect.Method; public class FastBigInteger { public static void main(String[] args) { try { Class c = Class.forName("java.math.MutableBigInteger"); Constructor con = c.getDeclaredConstructor(int.class); con.setAccessible(true); Object i = con.newInstance(1); Method m = c.getDeclaredMethod("mul", new Class[] { int.class, c }); m.setAccessible(true); long before = System.nanoTime(); for (int z = 2; z < 99999; ++z) { m.invoke(i, z, i); } long after = System.nanoTime(); System.out.println("Duration "+(after-before)/1e9); String s = i.toString(); int n = s.length(); int lineWidth = 200; for (int j=0; j
在打印实际计算的持续时间之后，它需要很长时间才能完成字符串的创建，但这里很难将其考虑在内。
这仍然不是一个明智的基准 ，但表明计算本身至少没有问题。
但诚然，当只使用BigInteger而不是这个MutableBigInteger黑客时，它需要MutableBigInteger 。 15秒，与C ++实现相比相当差。
从…开始：
import java.math.*; class Fac { public static void main(String[] args) { BigInteger i = BigInteger.ONE; BigInteger maxValue = BigInteger.valueOf(99999); for(BigInteger z=BigInteger.valueOf(2); z.compareTo(maxValue) != 0;) { i = i.multiply(z); z = z.add(BigInteger.ONE); } System.out.println( i ); } }
.valueOf来源
1081 public static BigInteger More ...valueOf(long val) { 1082 // If -MAX_CONSTANT < val < MAX_CONSTANT, return stashed constant 1083 if (val == 0) 1084 return ZERO; 1085 if (val > 0 && val <= MAX_CONSTANT) 1086 return posConst[(int) val]; 1087 else if (val < 0 && val >= -MAX_CONSTANT) 1088 return negConst[(int) -val]; 1089 1090 return new BigInteger(val); 1091 }
自MAX_CONSTANT为16以来，它每次都会创建一个新的BigInteger。
我认为它会变慢，因为GC开始收集一些较旧的BigInteger实例，但无论如何你应该总是使用int和long ..这里不需要BigInteger。
在您上次测试后，我认为我们可以确定它可能是由GC造成的。
我有一些使用大整数计算第100 000个斐波纳契数的clojure代码。 现在这个线程不是关于clojure，而是因为clojure在JVM上运行，我在一些现有的大整数实现上运行基准测试，我觉得这里的评论可能很有价值。
使用JVM BigInteger类时的算法（由clojure中的xN文字语法表示）如下所示：
(defn fibo [n] (loop [ina 1N b 1N] (if (> i 0) (recur (dec i) b (+ ab)) a)))
我已经使用四个大整数实现重新实现了这个，并且我使用clojure 标准库运行基准测试，该库执行热身和一些统计分析以尝试获得某些相关数字。
我的2,8 GHz Intel Core i7 macbook上的结果：
- apfloat apint类 – 964毫秒
- jvm BigInteger类 – 130毫秒
- jscience LargeInteger类 – 104毫秒
- huldra BigInt类 – 60毫秒
现在我意识到这都是轶事，而且我们只是在这里测量加法，但我不得不说huldra口号“自2015年以来表现优于BigInteger”在这种情况下似乎相当准确。
任何评论指向更快的大型int加法算法的潜在候选者都非常感谢。
其他答案与使用代码调整性能有关。
如果使用的Java版本低于1.8.051，则可以使用以下命令选项调整大整数性能：
-XX:-UseMontgomerySquareIntrinsic -XX:-UseMontgomeryMultiplyIntrinsic -XX:-UseSquareToLenIntrinsic -XX:-UseMultiplyToLenIntrinsic
在1.8.051之后，默认情况下会打开这些选项。