提高Java的BigInteger性能

Question

如何提高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 <iostream> 
#include <gmpxx.h> 
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 S（红宝石）和32.2小号完成JRuby中

而且还去（比较）：

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); 
} 

在1.6 S和0.7小号完成MulRange

编辑根据要求：

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小号

EDIT 2对于那些谁仍然认为，第一和第二的Java代码是不公平的..

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破解：10.1 s
• 字符串创建：〜20小号

Answer 1

计算本身不应该这么长。但是，字符串创建可能需要一段时间。

这个程序（荣誉给OldCurmudgeon和https://stackoverflow.com/a/8583188/823393）花费约为39秒，酷睿i7，3GHz的，Java的7/21，与-Xmx1000m -sever启动时：

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<n; j+=lineWidth) 
      { 
       int j0 = j; 
       int j1 = Math.min(s.length(), j+lineWidth); 
       System.out.println(s.substring(j0, j1)); 
      } 
     } 
     catch (Exception e) 
     { 
      System.err.println(e); 
     } 
    } 
} 

打印时间的实际计算后，它需要相当长的一段时间才能完成创建字符串，但在这里很难将其考虑在内。

这仍然是不是一个明智的基准，但表明，计算本身至少没有问题。

但是，诚然，只使用BigInteger而不是这个MutableBigInteger黑客，它需要appx。 15秒，这与C++实现相比相当差。

Answer 2

开始：

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 } 

这将创建一个新的BigInteger每次因为MAX_CONSTANT是16。

---

我觉得因为GC开始收集一些旧BigInteger情况，但无论如何，你应该总是使用int和长也可能走慢..这里是不是真的需要的BigInteger。

上次测试后，我想我们可以确定它可能是由GC引起的。

Answer 3

我有一些clojure代码使用大整数计算第100 000斐波纳契数。现在这个线程不是关于clojure，而是因为clojure在JVM上运行，我在一些现有的大整数实现上运行了基准测试，我觉得这里的评论可能是有价值的。

当它使用JVM的BigInteger类（由Clojure中的XN文字语法表示）的算法如下所示：

(defn fibo [n] 
    (loop [i n a 1N b 1N] 
    (if (> i 0) 
     (recur (dec i) b (+ a b)) 
     a))) 

此使用四大整数实现我已经重新实现，我跑了基准使用可以进行热身和一些统计分析的clojure criterium库来尝试获得相关的数字。

结果在我的2.8 GHz英特尔酷睿i7的MacBook：

• apfloatapint类 - 964毫秒
• JVM BigInteger类 - 130毫秒
• jscienceLargeInteger类 - 104毫秒
• huldraBigInt class - 60 ms

现在我意识到这是所有的轶事，我们只是在这里测量加法，但我不得不说，在这种情况下，huldra口号“2015年以来表现超越BigInteger”看起来相当准确。

任何意见指针潜在的候选人更快的大诠释加法算法非常赞赏。

Answer 4

其他答案与使用代码调整性能有关。

如果您使用的是Java版本低于1.8.051，你可以调大整数性能使用以下命令选项：

1.8.051

-XX:-UseMontgomerySquareIntrinsic 
-XX:-UseMontgomeryMultiplyIntrinsic 
-XX:-UseSquareToLenIntrinsic 
-XX:-UseMultiplyToLenIntrinsic 

后，这些选项是默认开启。