java - 提高 Java 的 BigInteger 性能

Question

如何提高 Java 大整数的性能？

例如，这个阶乘程序:

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(Ruby)和 32.2(在 JRuby)中完成

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

在 1.6 和 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 hack:10.1s
• 字符串创建:~20s

Answer 1

开始于:

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 和 long.. 这里并不真正需要 BigInteger。

根据您上次的测试，我认为我们可以确定它可能是由 GC 引起的。