Как вы рассчитываете основание журнала 2 в Java для целых чисел? - PullRequest
Новая
       57

Как вы рассчитываете основание журнала 2 в Java для целых чисел?

128 голосов
/ 22 июля 2010

Я использую следующую функцию для вычисления базы журнала 2 для целых чисел: 

public static int log2(int n){
    if(n <= 0) throw new IllegalArgumentException();
    return 31 - Integer.numberOfLeadingZeros(n);
}

Имеет ли она оптимальную производительность?

Кто-нибудь знает готовую функцию API J2SE для этой цели?

UPD1 Удивительно для меня, арифметика с плавающей точкой оказывается быстрее, чем целочисленная арифметика.

UPD2 Из-закомментарии Я проведу более детальное исследование.

UPD3 Моя целочисленная арифметическая функция в 10 раз быстрее, чем Math.log (n) /Math.log (2).

Ответы [ 10 ]

85 голосов
/ 22 июля 2010

Это функция, которую я использую для этого вычисления: 

public static int binlog( int bits ) // returns 0 for bits=0
{
    int log = 0;
    if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
    if( bits >= 256 ) { bits >>>= 8; log += 8; }
    if( bits >= 16  ) { bits >>>= 4; log += 4; }
    if( bits >= 4   ) { bits >>>= 2; log += 2; }
    return log + ( bits >>> 1 );
}

Это немного быстрее, чем Integer.numberOfLeadingZeros () (20-30%), и почти в 10 раз быстрее (jdk 1.6 x64), чемреализация на основе Math.log (), подобная этой: 

private static final double log2div = 1.000000000001 / Math.log( 2 );
public static int log2fp0( int bits )
{
    if( bits == 0 )
        return 0; // or throw exception
    return (int) ( Math.log( bits & 0xffffffffL ) * log2div );
}

Обе функции возвращают одинаковые результаты для всех возможных входных значений.

Обновление: Java 1.7Сервер JIT способен заменить несколько статических математических функций альтернативными реализациями, основанными на встроенных процессорах.Одной из таких функций является Integer.numberOfLeadingZeros ().Таким образом, при использовании виртуальной машины 1.7 или новее реализация, подобная рассматриваемой, фактически немного быстрее, чем binlog выше.К сожалению, клиентская JIT, похоже, не имеет этой оптимизации. 

public static int log2nlz( int bits )
{
    if( bits == 0 )
        return 0; // or throw exception
    return 31 - Integer.numberOfLeadingZeros( bits );
}

Эта реализация также возвращает те же результаты для всех 2 ^ 32 возможных входных значений, что и две другие реализации, которые я опубликовал выше.

Вот фактическое время выполнения на моем ПК (Sandy Bridge i7):

JDK 1.7 32-битная клиентская виртуальная машина: 

binlog:         11.5s
log2nlz:        16.5s
log2fp:        118.1s
log(x)/log(2): 165.0s

JDK 1.7Виртуальный сервер x64: 

binlog:          5.8s
log2nlz:         5.1s
log2fp:         89.5s
log(x)/log(2): 108.1s

Это тестовый код: 

int sum = 0, x = 0;
long time = System.nanoTime();
do sum += log2nlz( x ); while( ++x != 0 );
time = System.nanoTime() - time;
System.out.println( "time=" + time / 1000000L / 1000.0 + "s -> " + sum );
68 голосов
/ 22 июля 2010

Если вы думаете об использовании чисел с плавающей точкой, чтобы помочь с целочисленной арифметикой, вы должны быть осторожны.

Я обычно стараюсь избегать вычислений FP по возможности.

Операции с плавающей точкойне точны.Вы никогда не можете точно знать, что оценит (int)(Math.log(65536)/Math.log(2)).Например, Math.ceil(Math.log(1<<29) / Math.log(2)) - это 30 на моем ПК, где математически это должно быть ровно 29. Я не нашел значения для x, где (int)(Math.log(x)/Math.log(2)) терпит неудачу (только потому, что есть только 32 «опасных» значения), но это не такозначает, что он будет работать одинаково на любом ПК.

Обычный трюк здесь заключается в использовании "epsilon" при округлении.Как (int)(Math.log(x)/Math.log(2)+1e-10) никогда не должен потерпеть неудачу.Выбор этого «эпсилона» не является тривиальной задачей.

Больше демонстрации с использованием более общей задачи - попытка реализовать int log(int x, int base):

Код тестирования: 

static int pow(int base, int power) {
    int result = 1;
    for (int i = 0; i < power; i++)
        result *= base;
    return result;
}

private static void test(int base, int pow) {
    int x = pow(base, pow);
    if (pow != log(x, base))
        System.out.println(String.format("error at %d^%d", base, pow));
    if(pow!=0 && (pow-1) != log(x-1, base))
        System.out.println(String.format("error at %d^%d-1", base, pow));
}

public static void main(String[] args) {
    for (int base = 2; base < 500; base++) {
        int maxPow = (int) (Math.log(Integer.MAX_VALUE) / Math.log(base));
        for (int pow = 0; pow <= maxPow; pow++) {
            test(base, pow);
        }
    }
}

Если мы используем самую простую реализацию логарифма, 

static int log(int x, int base)
{
    return (int) (Math.log(x) / Math.log(base));
}

это печатает: 

error at 3^5
error at 3^10
error at 3^13
error at 3^15
error at 3^17
error at 9^5
error at 10^3
error at 10^6
error at 10^9
error at 11^7
error at 12^7
...

Чтобы полностью избавиться от ошибок, мне пришлось добавить epsilon, которыймежду 1e-11 и 1e-14.Могли бы вы сказать это до тестирования?Я определенно не мог.

32 голосов
/ 22 июля 2010

Попробуйте Math.log(x) / Math.log(2)

26 голосов
/ 22 июля 2010

вы можете использовать идентификатор 

            log[a]x
 log[b]x = ---------
            log[a]b

, так что это будет применимо для log2. 

            log[10]x
 log[2]x = ----------
            log[10]2

просто подключите это к методу java Math log10 ....

http://mathforum.org/library/drmath/view/55565.html

18 голосов
/ 22 июля 2010

Почему бы и нет: 

public static double log2(int n)
{
    return (Math.log(n) / Math.log(2));
}
8 голосов
/ 25 апреля 2015

В библиотеках гуавы есть функция: 

LongMath.log2()

Поэтому я предлагаю использовать его.

3 голосов
/ 19 февраля 2019

Некоторые случаи просто работали, когда я использовал Math.log10: 

public static double log2(int n)
{
    return (Math.log10(n) / Math.log10(2));
}
3 голосов
/ 11 марта 2016

Чтобы добавить к ответу x4u, который дает вам пол двоичного журнала числа, эта функция возвращает ceil двоичного журнала числа: 

public static int ceilbinlog(int number) // returns 0 for bits=0
{
    int log = 0;
    int bits = number;
    if ((bits & 0xffff0000) != 0) {
        bits >>>= 16;
        log = 16;
    }
    if (bits >= 256) {
        bits >>>= 8;
        log += 8;
    }
    if (bits >= 16) {
        bits >>>= 4;
        log += 4;
    }
    if (bits >= 4) {
        bits >>>= 2;
        log += 2;
    }
    if (1 << log < number)
        log++;
    return log + (bits >>> 1);
}
0 голосов
/ 25 июля 2018

Для вычисления логарифмической базы 2 из n можно использовать следующее выражение: 

double res = log10(n)/log10(2);
0 голосов
/ 24 сентября 2014

давайте добавим: 

int[] fastLogs;

private void populateFastLogs(int length) {
    fastLogs = new int[length + 1];
    int counter = 0;
    int log = 0;
    int num = 1;
    fastLogs[0] = 0;
    for (int i = 1; i < fastLogs.length; i++) {
        counter++;
        fastLogs[i] = log;
        if (counter == num) {
            log++;
            num *= 2;
            counter = 0;
        }
    }
}

Источник: https://github.com/pochuan/cs166/blob/master/ps1/rmq/SparseTableRMQ.java

...