Logaritma biner

Logaritma biner (bahasa Inggris: binary logarithm) dalam matematika adalah, adalah logaritma dengan basis 2, yang biasanya dilambangkan dengan log₂ n atau ²log n. Logaritma biner merupakan fungsi invers dari fungsi kuadrat atau fungsi pangkat dua. Logaritme biner n adalah kepangkatan bilangan dua untuk mendapatkan nilai  n. Jadi:

Kurva log₂ n

$x=\log _{2}n\quad \Longleftrightarrow \quad 2^{x}=n.$

Misalnya logaritma biner 1 adalah 0, logaritma biner 2 adalah 1, logaritma biner 4 adalah 2, logaritma biner 8 adalah 3, logaritma biner 16 adalah 4, logaritma biner 32 adalah  5 dan seterusnya.

Logaritma biner terkait erat dengan sistem bilangan biner. Dalam sejarahnya, aplikasi pertama logaritma biner adalah dalam teori musik, oleh Leonhard Euler: logaritma biner dari perbandingan frekuensi antara dua nada menghasilkan perbedaan oktaf antara nada-nada tersebut. Bidang lain yang sering menggunakan logaritma biner di antaranya adalah teori informasi, kombinatorika, ilmu komputer, bioinformatika, desain turnamen olahraga, dan fotografi.

Sejarah

Leonhard Euler adalah orang pertama yang menerapkan logaritme biner pada teori musik, pada tahun 1739.

Tabel pangkat dua dipublikasikan oleh Michael Stifel pada tahun 1544 dan dapat ditafsirkan (dengan membalikkan baris-barisnya) sebagai tabel logaritma biner. Aplikasi logaritma biner pada teori musik dilakukan oleh Leonhard Euler pada tahun 1739, jauh sebelum teori informasi dan ilmu komputer menjadi bidang studi. Sebagai bagian karyanya dalam bidang ini, Euler menyertakan suatu tabel logaritma biner untuk bilangan bulat dari 1 sampai 8, sampai dengan tujuh desimal untuk keakuratannya.

Notasi

Dalam matematika, logaritma biner suatu bilangan n ditulis sebagai log₂ n atau ²log n. Namun, sejumlah notasi lain fungsi ini telah diusulkan dan digunakan dalam berbagai bidang.

Sejumlah pengarang menuliskan logaritme biner sebagai lg n. Donald Knuth mengungkapkan bahwa notasi ini didapatnya dari usulan Edward Reingold, tetapi penggunaannya dalam teori informasi maupun ilmu komputer tampaknya sudah ada sebelum Reingold aktif. Logaritme biner juga pernah ditulis sebagai log n, dengan catatan bahwa basis default logaritma adalah bilangan 2 (bukan 10 sebagaimana lazimnya).

Notasi lain yang terkadang digunakan untuk fungsi tersebut (terutama dalam bahasa Jerman) adalah ld n, dari frasa bahasa Latin logarithmus duālis. Spesifikasi ISO 31-11 dan ISO 80000-2 menyarankan notasi lainnya, lb n; dalam spesifikasi ini, lg n digunakan untuk log₁₀ n.

Penerapan

Teori informasi

Banyak digit (bit) dalam representasi biner sebuah bilangan bulat positif n adalah bagian bulat dari 1 + log₂ n, i.e.

$\lfloor \log _{2}n\rfloor +1.\,$

Dalam teori informasi, definisi dari banyak konten informasi dan entropi informasi sering diekspresikan dengan logaritma biner, menyebabkan bit menjadi satuan fundamental untuk informasi. Akan tetapi, logaritma alami dan nat juga digunakan dalam notasi alternatif untuk definisi tersebut.

Kombinatorika

Sebuah braket turnamen sistem gugur 16-pemain yang berstruktur pohon biner lengkap. Tinggi pohon tersebut (banyak babak dalam turnamen) sama dengan logaritma biner untuk pohon biner lengkap yang banyak daunnya adalah perpangkatan dari dua, dan satu nilai lebih besar daripada logaritma biner untuk pohon dengan banyak daun selain itu.

Meskipun logaritma alami lebih penting daripada logaritma biner dalam banyak bidang matematika murni seperti teori bilangan dan analisis matematis, logaritma biner memiliki beberapa penerapan dalam kombinatoriks:

• Semua binary tree dengan n daun memiliki tinggi paling tidak sebesar $\log _{2}n$, dengan nilainya sama persisi apabila n merupakan perpangkatan dari dua dan pohonnya merupakan pohon biner lengkap.
• Semua keluarga himpunan dengan n himpunan berbeda memiliki paling tidak $\log _{2}n$ anggota dalam gabungannya, dengan nilainya sama persis apabila keluarga tersebut merupakan sebuah himpunan kuasa.

Kompleksitas komputasi

Pencarian biner pada larik yang berurut merupakan algoritma yang kompleksitas waktunya melibatkan logaritma biner

Logaritma biner juga sering muncul dalam analisis algoritma, bukan hanya karena aritmetika bilangan biner kerap digunakan dalam algoritma, tetapi juga karena logaritma biner muncul dalam analisis algoritma yang menggunakan percabangan dua arah. Jika suatu masalah awalnya punya n pilihan untuk dipilih, dan setiap pengulangan algoritma membagi dua banyak pilihannya, maka banyak pengulangan yang diperlukan untuk mendapatkan satu pilihan adalah bagian bulat dari log₂ n. Ide ini digunakan dalam menganalisis beberapa algoritma dan struktur data. Contohnya, dalam pencarian biner, ukuran masalah dibagi dua pada setiap pengulangannya, sehingga perlu kira-kira log₂n pengulangan untuk mendapatkan masalah berukuran 1, yang bisa diselesaikan dalam waktu konstan. Tidak jauh berbeda, pohon pencarian biner yang seimbang dan memiliki n element pasti punya tinggi log₂ n + 1.

Namun, lama waktu dijalankannya algoritma biasanya diekspresikan dalam notasi O besar, yang mengabaikan faktor konstanta. Karena log₂ n = (log_k n)/(log_k 2), dengan k adalah angka apapun yang lebih 1, algoritma yang berjalan dalam waktu O(log₂ n) bisa juga dikatakan berjalan dalam waktu O(log₁₃ n). Jadi basis logaritma dalam ekspresi-ekspresi seperti O(log n) atau O(n log n) tidaklah penting. Akan tetapi, dalam beberapa konteks, basis logaritma perlu dijelaskan. Contohnya O(2^log₂ n) tidak sama dengan O(2^ln n) karena yang pertama sama dengan O(n) sedangkan yang kedua sama dengan O(n^0.6931...).

Algoritma dengan waktu jalan O(n log n) terkadang disebut linearitmik. Contoh algoritma dengan waktu jalan O(log n) atau O(n log n) di antaranya:

• Waktu rata-rata dari quicksort dan beberapa algoritma pengurutan lainnya
• Pencarian dalam pohon pencarian biner yang seimbang
• Pemangkatan dengan menguadratkan
• Subbarisan naik terpanjang

Logarimta biner juga muncul dalam bentuk eksponen batas waktu untuk beberapa algoritma divide and conquer, seperti algortima Karatsuba untuk perkalian bilangan n-bit dalam waktu $O(n^{\log _{2}3})$.

Bioinformatika

Sebuah data mikrolarik dari ekspresi kira-kira 8700 gen. Tingkat ekspresi relatif dari gen-gen tersebut direpresentasikan menggunakan logaritma biner.

Dalam analisis data mikrolarik dalam bioinformatika, tingkat ekspresi gen biasanya dibandingkan dengan menggunakan logaritma biner dari rasio tingkat ekspresi. Dengan menggunakan logaritma basis 2, tingkat ekspresi yang menjadi dua kali lipat bisa digambarkan dengan rasio log 1, tingkat ekspresi yang menjadi setengah bisa digambarkan dengan log rasio −1, dan tingkat ekspresi yang tidak berubah bisa digambarkan dengan rasio log nol, sebagai contoh. Titik-titik data yang didapatkan dengan cara ini biasanya divisualisasikan sebagai sebuah diagram pencar di mana salah satu atau kedua sumbu koordinatnya adalah logaritma biner dari rasio intensitas, atau dalam visualisasi seperti diagram MA dan diagram RA yang memutar dan menskalakan rasio log dari diagram pencarnya.

Teori musik

Dalam teori musik, interval atau perbedaan dalam persepsi antara dua nada ditentukan oleh rasio kedua frekuensinya. Interval yang datang dari rasio bilangan rasional dengan pembilang dan penyebut kecil pada khususnya dianggap merdu. Interval yang paling sederhana dan paling penting adalah oktaf, suatu rasio frekuensi 2:1. Bilangan oktaf dari perbedaan dua nada merupakan logaritma biner dari rasio frekuensi kedua nada itu.

Untuk mempelajari sistem penalaan dan aspek lain dari teori musik dibutuhkan pembedaan yang lebih peka antara nada-nada, sehingga diperlukan suatu pengukuran besarnya interval yang lebih halus dari suatu oktaf dan dapat ditambah (sebagaimana suatu logaritma) bukannya dikalikan (sebagaimana rasio frekuensi). Jadi, jika nada-nada x, y, dan z membentuk urutan nada-nada yang menaik, maka ukuran interval dari x ke y ditambah ukuran interval dari y ke z seharusnya sama dengan ukuran interval dari x ke z. Pengukuran semacam ini dilakukan dengan satuan sen, yang membagi suatu oktaf menjadi 1200 interval yang sama (12 semitone yang masing-masing terdiri dari 100 cent). Secara matematis, nada-nada dengan frekuensi f₁ dan f₂, mempunyai jumlah sen dalam interval dari x ke y sebesar

$\left|1200\log _{2}{\frac {f_{1}}{f_{2}}}\right|.$

Istilah milioktaf didefinisikan dengan cara yang sama, tetapi dengan pengali 1000 bukannya 1200.

Penjadwalan olahraga

Dalam permainan dan olah raga dengan dua pemain atau tim dalam masing-masing permainan atau pertandingannya, logaritma biner menunjukkan banyak babak yang diperlukan untuk menentukan pemengang dalam suatu turnamen dengan sistem gugur. Sebagai contoh, turnamen dengan 4 pemain perlu log₂(4) = 2 babak untuk menentukan pemenangnya, turnamen dengan 32 tim memerlukan log₂(32) = 5 babak, dsb. Dalam kasus di mana terdapat n pemain/tim dan n bukan perpangkatan dari 2, log₂n dibulatkan ke atas karena akan diperlukan paling tidak satu babak di mana tidak semua pesertanya bertanding. Misalnya, log₂(6) kira-kira sama dengan 2,585, dibulatkan ke atas, menunjukkan bahwa turnamen dengan 6 tim memerlukan 3 babak (bisa jadi 2 tim tidak bermain di babak pertama, atau satu tim tidak bermain di babak kedua). Banyak babak yang sama juga diperlukan untuk menentukan pemenang yang jelas dalam turnamen sistem Swiss.

Fotografi

Dalam fotografi, nilai eksposur diukur menggunakan logaritma biner jumlah cahaya yang mencapai film atau sensor, sejalan dengan hukum Weber–Fechner yang menyatakan respons logaritmik sistem penglihatan manusia terhadap cahaya. Satu stop exposur adalah satu unit dalam skala logaritma basis-2. Lebih tepatnya, nilai exposure suatu foto didefinisikan sebagai:

$\log _{2}{\frac {N^{2}}{t}}$

di mana $N$ adalah bilangan-f yang mengukur bukaan lensa selama exposur, dan $t$ adalah jumlah detik lamanya exposur.

Logaritma biner (diekspresikan dalam satuan stop) juga digunakan dalam densitometri, untuk mengekspresikan rentang dinamis dari bahan atau sensor digital yang sensitif cahaya.

Kalkulasi

Dukungan perpustakaan software

Fungsi log2 dimasukkan ke dalam fungsi matematika C standar. Versi default fungsi ini mengambil argumen double precision tetapi varian-variannya mengizinkan argumen dalam bentuk single-precision atau sebagai long double.

Pranala luar

• Weisstein, Eric W. "Binary Logarithm". MathWorld.