如何提高
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.5s完成
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.0s完成
和Ruby(用于比较)：
puts (2...99999).inject(:*)
完成在4.4s(Ruby)和32.2s在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 );
}
MulRange在1.6s和0.7s完成
编辑根据要求：
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.1s完成
编辑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.7s完成
编辑4如@ Marco13所述,最大的问题是字符串创建不在BigInteger本身.
> BigInteger：3.0s
> MutableBigInteger hack：10.1s
>字符串创建：〜20s
解决方法
计算本身不应该花费这么长时间.然而,字符串创建可能需要一段时间.
Core i7,3GHz,Java 7/21的这个程序(Kudos to OldCurmudgeon和https://stackoverflow.com/a/8583188/823393)在使用-Xmx1000m -sever启动时需要大约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",c });
m.setAccessible(true);
long before = System.nanoTime();
for (int z = 2; z < 99999; ++z)
{
m.invoke(i,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实现相比较差.
