Новая производительность/сложность BigInteger (String)

Мне интересно узнать о производительности / сложности построения объектов BigInteger с помощью конструктора new BigInteger(String).

Рассмотрим следующий метод:

  public static void testBigIntegerConstruction()
  {
    for (int exp = 1; exp < 10; exp++)
    {
      StringBuffer bigNumber = new StringBuffer((int) Math.pow(10.0, exp));
      for (int i = 0; i < Math.pow(10.0, exp - 1); i++)
      {
        bigNumber.append("1234567890");
      }

      String val = bigNumber.toString();
      long time = System.currentTimeMillis();
      BigInteger bigOne = new BigInteger(val);
      System.out.println("time for constructing a 10^" + exp
          + " digits BigInteger : " + ((System.currentTimeMillis() - time))
          + " ms");
    }
  }

Этот метод создает BigInteger объекты строк с цифрами 10^x, где x=1 в начале и увеличивается с каждой итерацией. Он измеряет и выводит время, необходимое для построения соответствующего объекта BigInteger.

На моей машине (Intel Core i5 660, JDK 6 Update 25 32 бит) вывод:

time for constructing a 10^1 digits BigInteger : 0 ms
time for constructing a 10^2 digits BigInteger : 0 ms
time for constructing a 10^3 digits BigInteger : 0 ms
time for constructing a 10^4 digits BigInteger : 16 ms
time for constructing a 10^5 digits BigInteger : 656 ms
time for constructing a 10^6 digits BigInteger : 59936 ms
time for constructing a 10^7 digits BigInteger : 6227975 ms

При игнорировании строк до 10 ^ 5 (из-за возможных искажений, вызванных эффектами кеширования процессора, JIT-компиляцией и т.д.), мы можем четко видеть сложность O (n ^ 2) здесь. Помня о том, что каждая операция на BigInteger создает новую из-за неизменности, , это большая эффективность для огромных чисел.

Вопросы:

  • Я что-то пропустил?

  • Почему это так?

  • Является ли это исправлено в более поздних JDK?

  • Есть ли альтернативы?

UPDATE:

Я сделал дальнейшие измерения, и я могу подтвердить утверждение из некоторых ответов: "Кажется, что BigInteger оптимизирован для последующих числовых операций с расходом более высоких затрат на строительство для огромных чисел, которые кажутся мне разумными.

Ответы

Ответ 1

Упрощение из источника несколько, это случай, потому что в "традиционном" синтаксическом цикле строк

for each digit y from left to right:
  x = 10 * x + y

у вас возникла проблема, что 10 * x неизбежно занимает время, линейное по длине x, и эта длина растет более или менее постоянным фактором для каждой цифры, также неизбежно.

(Фактическая реализация несколько более умна, чем эта - она ​​пытается разобрать двоичные цифры int за раз, и поэтому фактический множитель в цикле более вероятен 1 или 2 миллиарда - но да, он по-прежнему квадратичный.)

Тем не менее, число с цифрами 10^6 - это, по крайней мере, googol, и это больше, чем любое число, которое я слышал о том, что он используется даже для криптографических целей. Вы разбираете строку, которая занимает две мегабайты памяти. Да, это займет некоторое время, но я подозреваю, что авторы JDK не видели смысла оптимизировать такой редкий случай использования.

Ответ 2

Усиление O (n ^ 2) вызвано преобразованием десятичного в двоичное, если BigInteger указано как десятичные цифры.

Кроме того, 10 ^ 7 цифр - действительно огромное количество. Для типичных криптографических алгоритмов, таких как RSA, вы будете обрабатывать 10 ^ 3 до 10 ^ 4 цифры. Большинство операций BigInteger не оптимизированы для такого большого количества цифр.

Ответ 3

Фактически вы измеряете время, необходимое для анализа строки и создания BigInteger. Числовые операции с BigIntegers были бы намного более эффективными, чем это.