Bagaimana Anda menghitung basis log 2 di Java untuk bilangan bulat?

138

Saya menggunakan fungsi berikut untuk menghitung log basis 2 untuk bilangan bulat:

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

Apakah memiliki kinerja optimal?

Apakah ada yang tahu fungsi J2SE API siap untuk tujuan itu?

UPD1 Anehnya bagi saya, aritmatika float point tampaknya lebih cepat daripada aritmatika integer.

UPD2 Karena komentar saya akan melakukan penyelidikan lebih rinci.

UPD3 Fungsi aritmatika integer saya 10 kali lebih cepat dari Math.log (n) /Math.log (2).

Nulldevice
sumber
1
Bagaimana Anda menguji kinerja ini? Pada Sistem saya (Core i7, jdk 1.6 x64) versi integer hampir 10 kali lebih cepat daripada versi floating point. Pastikan untuk benar-benar melakukan sesuatu dengan hasil fungsi sehingga JIT tidak dapat menghapus perhitungan sepenuhnya!
x4u
Anda benar. Saya tidak menggunakan hasil perhitungan dan kompiler telah mengoptimalkan sesuatu. Sekarang saya memiliki hasil yang sama seperti Anda - fungsi integer adalah 10 kali lebih cepat (Core 2 Duo, jdk 1.6 c64)
Nulldevice
6
Ini secara efektif memberi Anda Math.floor(Math.log(n)/Math.log(2)), jadi itu tidak benar-benar menghitung basis log 2!
Dori

Jawaban:

74

Jika Anda berpikir untuk menggunakan floating-point untuk membantu integer arithmetics, Anda harus berhati-hati.

Saya biasanya mencoba menghindari perhitungan FP jika memungkinkan.

Operasi titik-mengambang tidak tepat. Anda tidak akan pernah tahu pasti apa yang akan (int)(Math.log(65536)/Math.log(2))dievaluasi. Misalnya, Math.ceil(Math.log(1<<29) / Math.log(2))adalah 30 pada PC saya di mana secara matematis seharusnya 29. Saya tidak menemukan nilai untuk x di mana (int)(Math.log(x)/Math.log(2))gagal (hanya karena hanya ada 32 nilai "berbahaya"), tetapi itu tidak berarti bahwa ia akan bekerja dengan cara yang sama pada PC apa pun.

Trik yang biasa di sini adalah menggunakan "epsilon" saat pembulatan. Seperti (int)(Math.log(x)/Math.log(2)+1e-10)seharusnya tidak pernah gagal. Pilihan "epsilon" ini bukanlah tugas sepele.

Lebih banyak demonstrasi, menggunakan tugas yang lebih umum - mencoba menerapkan int log(int x, int base):

Kode pengujian:

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);
        }
    }
}

Jika kita menggunakan implementasi logaritma yang paling mudah,

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

ini mencetak:

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

Untuk benar-benar menghilangkan kesalahan saya harus menambahkan epsilon yaitu antara 1e-11 dan 1e-14. Bisakah Anda memberi tahu ini sebelum pengujian? Saya pasti tidak bisa.

Rotsor
sumber
3
"Itu tidak berarti bahwa itu akan bekerja dengan cara yang sama pada PC manapun" - Itu akan terjadi jika Anda menggunakan strictfp, bukan?
Ken
@ Ken: Mungkin ... Tapi Anda hanya bisa yakin setelah secara mendalam menyebutkan semua nilai input yang mungkin. (kami beruntung ada begitu sedikit dari mereka di sini)
Rotsor
2
Secara teknis, ya, tapi itu berlaku untuk fungsi apa pun. Pada titik tertentu Anda harus percaya bahwa jika Anda menggunakan dokumentasi yang tersedia, dan menguji sebagian kecil dari "semua nilai input yang mungkin", bahwa program Anda akan bekerja dengan cukup baik. strictfptampaknya benar-benar mendapatkan banyak omong kosong karena, pada kenyataannya, ketat. :-)
Ken
bagaimana cara return ((long)Math.log(x) / (long)Math.log(base));mengatasi semua kesalahan?
Bukan bug
92

Ini adalah fungsi yang saya gunakan untuk perhitungan ini:

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 );
}

Ini sedikit lebih cepat daripada Integer.numberOfLeadingZeros () (20-30%) dan hampir 10 kali lebih cepat (jdk 1,6 x64) daripada implementasi berbasis Math.log () seperti ini:

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 );
}

Kedua fungsi mengembalikan hasil yang sama untuk semua nilai input yang mungkin.

Pembaruan: Java 1.7 server JIT dapat menggantikan beberapa fungsi matematika statis dengan implementasi alternatif berdasarkan pada intrinsik CPU. Salah satu fungsi tersebut adalah Integer.numberOfLeadingZeros (). Jadi dengan 1.7 atau lebih baru VM server, implementasi seperti yang ada di pertanyaan sebenarnya sedikit lebih cepat daripada yang di binlogatas. Sayangnya, JIT klien tampaknya tidak memiliki pengoptimalan ini.

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

Implementasi ini juga mengembalikan hasil yang sama untuk semua 2 ^ 32 nilai input yang mungkin seperti dua implementasi lainnya yang saya posting di atas.

Berikut adalah runtime aktual di PC saya (Sandy Bridge i7):

JDK 1,7 32 Bit klien 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

Ini adalah kode tes:

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 );
x4u
sumber
9
BSRInstruksi x86 memang 32 - numberOfLeadingZeros, tetapi tidak terdefinisi untuk 0, jadi kompiler (JIT) harus memeriksa bukan-nol jika tidak dapat membuktikannya tidak harus. Instruksi set BMI ekstensi (Haswell dan yang lebih baru) diperkenalkan LZCNT, yang sepenuhnya mengimplementasikan dengan numberOfLeadingZerostepat, dalam satu instruksi. Keduanya 3 siklus latensi, 1 per siklus throughput. Jadi saya benar-benar merekomendasikan menggunakan numberOfLeadingZeros, karena itu membuatnya mudah untuk JVM yang baik. (Satu hal yang aneh lzcntadalah bahwa ia memiliki ketergantungan salah pada nilai lama register yang ditimpa.)
Peter Cordes
Saya paling tertarik dengan komentar Anda tentang Java 1.7 server penggantian intrinsik JIT CPU. Apakah Anda memiliki URL referensi? (Tautan kode sumber JIT juga OK.)
kevinarpe
37

Mencoba Math.log(x) / Math.log(2)

Chris B.
sumber
8
Meskipun secara matematis ini benar, perlu diketahui bahwa ada risiko salah perhitungan karena aritmatika floating-point tidak tepat, seperti yang dijelaskan dalam jawaban Rotsor.
leeyuiwah
28

Anda dapat menggunakan identitas

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

jadi ini akan berlaku untuk log2.

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

cukup tancapkan ini ke metode java Math log10 ....

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

hvgotcodes
sumber
3
Meskipun secara matematis ini benar, perlu diketahui bahwa ada risiko salah perhitungan karena aritmatika floating-point tidak tepat, seperti yang dijelaskan dalam jawaban Rotsor.
leeyuiwah
18

Kenapa tidak:

public static double log2(int n)
{
    return (Math.log(n) / Math.log(2));
}
TofuBeer
sumber
6
Meskipun secara matematis ini benar, perlu diketahui bahwa ada risiko salah perhitungan karena aritmatika floating-point tidak tepat, seperti yang dijelaskan dalam jawaban Rotsor.
leeyuiwah
9

Ada fungsi di perpustakaan jambu:

LongMath.log2()

Jadi saya sarankan untuk menggunakannya.

Demetr
sumber
Bagaimana saya bisa menambahkan paket ini ke aplikasi saya?
Elvin Mammadov
Unduh toples dari sini dan tambahkan ke jalur build proyek Anda.
Debosmit Ray
2
Haruskah saya menambahkan perpustakaan ke aplikasi saya hanya untuk menggunakan satu fungsi?
Tash Pemhiwa
7
Mengapa Anda menyarankan untuk menggunakannya? Pembacaan cepat dari sumber Guava menunjukkan bahwa ia melakukan hal yang sama dengan metode OP (beberapa baris kode yang sangat dipahami), dengan biaya menambahkan ketergantungan yang tidak berguna. Hanya karena Google menyediakan sesuatu tidak membuatnya lebih baik daripada memahami masalah dan solusinya sendiri.
Dave
3

Untuk menambahkan jawaban x4u, yang memberi Anda dasar log biner suatu angka, fungsi ini mengembalikan langit-langit log biner angka:

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);
}
Ofek Ron
sumber
Di mana variabel "angka"?
barteks2x
3

Beberapa kasus baru berfungsi ketika saya menggunakan Math.log10:

public static double log2(int n)
{
    return (Math.log10(n) / Math.log10(2));
}
Marina
sumber
0

mari tambahkan:

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

Sumber: https://github.com/pochuan/cs166/blob/master/ps1/rmq/SparseTableRMQ.java

Guido Celada
sumber
Itu akan membuat tabel pencarian. OP meminta cara yang lebih cepat untuk "menghitung" logaritma.
Dave
-4

Untuk menghitung log basis 2 dari n, ekspresi berikut dapat digunakan:

double res = log10(n)/log10(2);
Akanksha
sumber
2
Jawaban ini telah diposting beberapa kali, dan telah diketahui berpotensi tidak akurat karena kesalahan pembulatan. Perhatikan OP meminta nilai integral; sama sekali tidak jelas presisi pembulatan apa yang perlu digunakan untuk mendapatkan dari sini ke integer.
AnotherParker