Как вы рассчитываете основание журнала 2 в Java для целых чисел?
Я использую следующую функцию для расчета лог-базы 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).
5 ответов
Если вы думаете об использовании плавающей точки для помощи в целочисленной арифметике, вам нужно быть осторожным.
Обычно я стараюсь избегать вычислений с плавающей запятой, когда это возможно.
Операции с плавающей точкой не являются точными. Вы никогда не можете знать наверняка, что получится (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 "опасных" значения), но это не значит, что оно будет работать одинаково на любом ПК.
Обычный трюк здесь - использование "эпсилона" при округлении. Например, (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
...
Чтобы полностью избавиться от ошибок, пришлось добавить эпсилон, который находится между 1e-11 и 1e-14. Могли бы вы сказать это до тестирования? Я определенно не мог.
Вот функция, которую я использую для этого вычисления:
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 );
}
Обе функции возвращают одинаковые результаты для всех возможных входных значений.
Update:
Серверный JIT Java 1.7 способен заменить несколько статических математических функций альтернативными реализациями, основанными на внутренних свойствах процессора. Одной из таких функций является 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 Bits client VM:
binlog: 11.5s
log2nlz: 16.5s
log2fp: 118.1s
log(x)/log(2): 165.0s
JDK 1.7 x64 server VM:
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 );
Почему бы и нет:
public static double log2(int n)
{
return (Math.log(n) / Math.log(2));
}
вы можете использовать идентификатор
log[a]x
log[b]x = ---------
log[a]b
, так что это будет применимо для log2.
log[10]x
log[2]x = ----------
log[10]2
просто вставьте это в метод java Math log10 ....