java.math.BigInteger pow (показатель степени) вопрос - PullRequest
Новая
       28

java.math.BigInteger pow (показатель степени) вопрос

6 голосов
/ 29 мая 2010

Я провел несколько тестов по методу pow (экспонента). К сожалению, мои математические навыки недостаточно сильны для решения следующей проблемы.

Я использую этот код: 

BigInteger.valueOf(2).pow(var);

Результаты:

  • вар | время в мс
  • 2000000 | 11450
  • 2500000 | 12471
  • 3000000 | 22379
  • 3500000 | 32147
  • 4000000 | 46270
  • 4500000 | 31459
  • 5000000 | 49922

См? 250000 экспонента рассчитывается почти так же быстро, как 2000000. 4 500 000 вычисляется намного быстрее, чем 4 000 000.

Почему это?

Чтобы помочь вам, вот оригинальная реализация BigInteger.pow (экспонента): 

 public BigInteger pow(int exponent) {
    if (exponent < 0)
        throw new ArithmeticException("Negative exponent");
    if (signum==0)
        return (exponent==0 ? ONE : this);

    // Perform exponentiation using repeated squaring trick
        int newSign = (signum<0 && (exponent&1)==1 ? -1 : 1);
    int[] baseToPow2 = this.mag;
        int[] result = {1};

    while (exponent != 0) {
        if ((exponent & 1)==1) {
        result = multiplyToLen(result, result.length, 
                                       baseToPow2, baseToPow2.length, null);
        result = trustedStripLeadingZeroInts(result);
        }
        if ((exponent >>>= 1) != 0) {
                baseToPow2 = squareToLen(baseToPow2, baseToPow2.length, null);
        baseToPow2 = trustedStripLeadingZeroInts(baseToPow2);
        }
    }
    return new BigInteger(result, newSign);
    }

Ответы [ 3 ]

9 голосов
/ 29 мая 2010

Алгоритм использует повторное возведение в квадрат (squareToLen) и умножение (multiplyToLen). Время выполнения этих операций зависит от размера используемых чисел. Умножения больших чисел в конце расчета намного дороже, чем в начале.

Умножение выполняется только при выполнении этого условия: ((exponent & 1)==1). Количество квадратичных операций зависит от количества битов в числе (исключая начальные нули), но умножение требуется только для битов, которые установлены в 1. Проще увидеть операции, которые требуются, глядя на двоичный представление числа: 

2000000: 0000111101000010010000000
2500000: 0001001100010010110100000
3000000: 0001011011100011011000000
3500000: 0001101010110011111100000
4000000: 0001111010000100100000000
4500000: 0010001001010101000100000
5000000: 0010011000100101101000000

Обратите внимание, что 2.5M и 4.5M удачны в том, что у них установлено меньше старших бит, чем числа, окружающие их. В следующий раз это произойдет в 8.5M: 

8000000: 0011110100001001000000000
8500000: 0100000011011001100100000
9000000: 0100010010101010001000000

Сладкие пятна имеют точную степень 2. 

1048575: 0001111111111111111111111 // 16408 ms
1048576: 0010000000000000000000000 //  6209 ms
1 голос
/ 29 мая 2010

Я не уверен, сколько раз вы запускали время. Как отмечали некоторые комментаторы, вам нужно много-много раз рассчитывать операции, чтобы получить хорошие результаты (а они все еще могут быть ошибочными).

Предполагая, что вы хорошо рассчитали время, помните, что в математике можно использовать множество сочетаний клавиш. Вам не нужно делать операции 5 * 5 * 5 * 5 * 5 * 5, чтобы вычислить 5 ^ 6.

Вот один из способов сделать это намного быстрее. http://en.wikipedia.org/wiki/Exponentiation_by_squaring

1 голос
/ 29 мая 2010

Просто предположение:

показатель степени обрабатывается побитно, и если младший бит равен 1, выполняется дополнительная работа.

Если L - количество бит в показателе степени и A количество битов, которые равны 1 и t1 время для обработки общей части и t2 дополнительное время обработки, когда LSbit равен 1

тогда время выполнения будет

L t1 + A t2

или время зависит от количества единиц в двоичном представлении.

сейчас пишу небольшую программу для проверки моей теории ...

...