提高Java的BigInteger性能 [英] Increasing Java's BigInteger performance

问题描述

如何提高Java的Big Integer的性能？

How to increase performance of Java's 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完成 s

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 中完成s

和Ruby（用于比较）：

And Ruby (for comparison):

puts (2...99999).inject(:*)

在 4.4 < JR $中的$ code> s（Ruby）和 32.2

还有Go（用于比较） ：

And also Go (for comparison):

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 s 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 s

编辑2 对于那些仍然认为第一个和第二个java代码不公平的人......

EDIT 2 for those who still think that the first and second java code is unfair..

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完成 s

编辑3 @OldCurmudgeon评论：

EDIT 3 @OldCurmudgeon comment:

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完成 s

编辑4 正如@ Marco13所述，最大的问题是字符串创建不在BigInteger本身。 。

EDIT 4 As stated by @Marco13 the biggest problem was on the string creation not on the BigInteger itself..

• BigInteger： 3.0 s


• MutableBigInteger hack： 10.1 s


• 字符串创建：〜 20 s

• BigInteger: 3.0s
• MutableBigInteger hack: 10.1s
• String creation: ~20s

推荐答案

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

The computation itself should not take so long. The string creation may take a while, however.

此计划（感谢OldCurmudgeon和 https://stackoverflow.com/ a / 8583188/823393 ）在使用 -Xmx1000m -sever 启动的Core I7,3GHz，Java 7/21上大约需要3.9秒：

This program (Kudos to OldCurmudgeon and https://stackoverflow.com/a/8583188/823393 ) takes approximately 3.9 seconds on a Core I7, 3GHz, Java 7/21, when started with -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);
        }
    }
}

打印后的持续时间实际计算，它需要很长时间才能完成字符串的创建，但这里几乎不应该考虑到这一点。

After printing the duration for the actual computation, it takes quite a while until it finished creating the string, but this should hardly be taken into account here.

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

This is still not a sensible benchmark, but shows that there is at least no problem with the computation itself.

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

But admittedly, when using only BigInteger instead of this MutableBigInteger hack, it takes appx. 15 seconds, which is rather poor compared to the C++ implementation.

这篇关于提高Java的BigInteger性能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！