Increase BigInteger performance of Java

How to improve the large integer performance of Java?

For example, this factional program:

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

The plan was completed in 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;
}

Completed in 1.0s

And Ruby (for comparison):

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

Completed in 4.4S (Ruby) and 32.2s in jruby

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

Mulrange is completed in 1.6s and 0.7s

Edit as required:

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

Running time: 31.4 seconds

For those who still think the first and second Java codes are unfair, edit 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 );
  }
}

Completed in 31.1s

Edit 3 @ oldcurmudgeon comments:

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

Completed in 23.7s

Edit 4 as described by @ marco13, the biggest problem is that the string creation is not in BigInteger itself

>BigInteger: 3.0s > mutablebiginteger hack: 10.1s > string creation: ~ 20s

Solution

The calculation itself should not take so long However, string creation may take some time

Core i7,3ghz, this program of Java 7 / 21 (kudos to oldcurmudgeon and https://stackoverflow.com/a/8583188/823393 ）It takes about 3.9 seconds to start 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",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);
        }
    }
}

After printing the actual calculated duration, it takes quite a long time until the creation of the string is completed, but this is hardly considered here

This is still not a wise benchmark, but it shows that the calculation itself is at least no problem

But of course, when using only BigInteger instead of the mutable BigInteger hacker, it needs appx 15 seconds, poor compared with C implementation