Увеличение производительности BigInteger Java

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

и Руби (для сравнения):

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

завершено в 4.4 с (рубин) и 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

EDIT В соответствии с запросом:

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 s

EDIT 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 сек

EDIT 4 Как заявил @ Marco13 самая большая проблема была в создании строки не на самом BigInteger ..

• BigInteger: 3.0 s
• MutableBigInteger hack: 10.1 s
• Создание строки: ~ 20 сек

Answer 1

Само вычисление не должно длиться так долго. Однако создание строки может занять некоторое время.

Эта программа (Престижность OldCurmudgeon и https://stackoverflow.com/a/8583188/823393) занимает около 3,9 секунд на Core 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 взломать, требуется приложение. 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 (обозначенный буквальный синтаксис Xn в Clojure) выглядит следующим образом:

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

Я повторно реализовал это при помощи четыре больших целочисленных реализаций, и я побежал тесты используя библиотеку clojure criterium, которая делает разминки и некоторый статистический анализ, чтобы попытаться добраться до нескольких соответствующих номеров.

Результаты на моем 2,8 ГГц Intel Core i7 MacBook:

• apfloatapint класса - 964 мс
• BigInteger класс JVM - 130 мс
• jscienceLargeInteger класса - 104 мс
• huldraBigInt класс - 60 мс

Теперь я понимаю, что это все анекдотично и что мы только измеряем добавление здесь, но я должен сказать, что фраза huldra catch «Превосходительство BigInteger с 2015 года» кажется довольно точной в этом случае.

Любые комментарии с указателями на потенциальных кандидатов для более быстрых алгоритмов добавления больших чисел очень ценятся.

Answer 4

Другие ответы связаны с настройкой производительности с использованием кода.

Если вы используете Java версию меньше, чем 1.8.051, вы можете настроить большую производительность целого, используя следующие параметры командной строки:

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

После 1.8.051, эти опции включены по умолчанию.