Logaritma biner

Logaritma biner
Informasi umum
Bidang penerapan	Teori musik
Domain dan Citra
Domain dari fungsi	${\displaystyle (0,\infty )}$
Daerah hasil fungsi	${\displaystyle (-\infty ,\infty )}$
Nilai-nilai spesifik
Nilai di 0	${\displaystyle 1}$
Nilai maksimum	Tidak ada
Nilai minimum	Tidak ada
Invers	${\displaystyle x=2^{y}}$
Turunan	${\displaystyle {\frac {1}{x\ln 2}}}$

Logaritma biner (bahasa Inggris: binary logarithm) dalam matematika adalah, adalah logaritma dengan basis 2, yang biasanya dilambangkan dengan ${\displaystyle \log _{2}n}$ atau ${\displaystyle ^{2}\!\log n}$. Logaritma biner merupakan fungsi invers dari fungsi kuadrat atau fungsi pangkat dua. Logaritma biner ${\displaystyle n}$ adalah kepangkatan bilangan dua untuk mendapatkan nilai ${\displaystyle n}$. Jadi:

${\displaystyle 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 logaritma 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.^[1][2] 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.^[3][4]

Notasi

Dalam matematika, logaritma biner suatu bilangan n ditulis sebagai ${\displaystyle \log _{2}n}$ atau ${\displaystyle ^{2}\!\log n}$. Namun, sejumlah notasi lain fungsi ini telah diusulkan dan digunakan dalam berbagai bidang.

Sejumlah pengarang menuliskan logaritma biner sebagai ${\displaystyle \lg n}$.^[5][6] Donald Knuth mengungkapkan bahwa notasi ini didapatnya dari usulan Edward Reingold,^[7] tetapi penggunaannya dalam teori informasi maupun ilmu komputer tampaknya sudah ada sebelum Reingold aktif.^[8][9] Logaritma biner juga pernah ditulis sebagai ${\displaystyle \log n}$, dengan catatan bahwa basis default logaritma adalah bilangan 2 (bukan 10 sebagaimana lazimnya).^[10][11][12]

Notasi lain yang terkadang digunakan untuk fungsi tersebut (terutama dalam bahasa Jerman) adalah ${\displaystyle \operatorname {ld} n}$, dari frasa bahasa Latin logarithmus duālis.^[13] Spesifikasi ISO 31-11 dan ISO 80000-2 menyarankan notasi lainnya, ${\displaystyle \operatorname {lb} n}$; dalam spesifikasi ini, ${\displaystyle \lg n}$ digunakan untuk ${\displaystyle \log _{10}n}$.^[14][15][16]

Penerapan

Teori informasi

Banyak digit (bit) dalam representasi biner sebuah bilangan bulat positif ${\displaystyle n}$ adalah bagian bulat dari ${\displaystyle 1+\log _{2}n}$, yakni^[6]

${\displaystyle \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.^[17]

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 kombinatorik:

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

Kompleksitas komputasi

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

Logaritma biner juga sering muncul dalam analisis algoritma,^[12] bukan hanya karena aritmetika bilangan biner kerap digunakan dalam algoritma, tetapi juga karena logaritma biner muncul dalam analisis algoritma yang menggunakan percabangan dua arah.^[7] Jika suatu masalah awalnya punya ${\displaystyle 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 ${\displaystyle \log _{2}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 ${\displaystyle \log _{2}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 ${\displaystyle \log _{2}n+1}$.

Namun, lama waktu dijalankannya algoritma biasanya diekspresikan dalam notasi O besar, yang mengabaikan faktor konstanta. Karena ${\displaystyle \log _{2}n={\frac {\log _{k}n}{\log _{k}2}}}$, dengan ${\displaystyle k}$ adalah suatu bilangan yang lebih dari 1, algoritma yang berjalan dalam waktu ${\displaystyle O(\log _{2}n)}$ bisa juga dikatakan berjalan dalam waktu ${\displaystyle O(\log _{13}n)}$. Jadi basis logaritma dalam ekspresi-ekspresi seperti ${\displaystyle O(\log n)}$ atau ${\displaystyle O(n\log n)}$ tidaklah penting.^[5] Akan tetapi, dalam beberapa konteks, basis logaritma perlu dijelaskan. Contohnya ${\displaystyle O(2^{\log _{2}n})}$ tidak sama dengan ${\displaystyle O(2^{\ln n})}$ karena yang pertama sama dengan ${\displaystyle O(n)}$ sedangkan yang kedua sama dengan ${\displaystyle O(n^{0.6931\dots })}$.

Algoritma dengan waktu jalan ${\displaystyle O(n\log n)}$ terkadang disebut linearitmik.^[20] Contoh algoritma dengan waktu jalan ${\displaystyle O(\log n)}$ atau ${\displaystyle O(n\log n)}$ di antaranya:

• Waktu rata-rata dari quicksort dan beberapa algoritma pengurutan lainnya^[21]
• Pencarian dalam pohon pencarian biner yang seimbang^[22]
• Pemangkatan dengan menguadratkan^[23]
• Subbarisan naik terpanjang^[24]

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 ${\displaystyle O(n^{\log _{2}3})}$.^[25]

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 ${\displaystyle \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.^[26] 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.^[27]

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 ${\displaystyle 2:1}$. Bilangan oktaf dari perbedaan dua nada merupakan logaritma biner dari rasio frekuensi kedua nada itu.^[28]

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 ${\displaystyle x}$, ${\displaystyle y}$, dan ${\displaystyle z}$ membentuk urutan nada-nada yang menaik, maka ukuran interval dari ${\displaystyle x}$ ke ${\displaystyle y}$ ditambah ukuran interval dari ${\displaystyle y}$ ke ${\displaystyle z}$ seharusnya sama dengan ukuran interval dari ${\displaystyle x}$ ke ${\displaystyle 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 ${\displaystyle f_{1}}$ dan ${\displaystyle f_{2}}$, mempunyai jumlah sen dalam interval dari ${\displaystyle x}$ ke ${\displaystyle y}$ sebesar^[28]

${\displaystyle \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.^[29]

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.^[30][31] Lebih tepatnya, nilai exposure suatu foto didefinisikan sebagai:

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

di mana ${\displaystyle N}$ adalah bilangan-f yang mengukur bukaan lensa selama exposur, dan ${\displaystyle 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.^[32]

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.^[33]

Referensi

1. Groza, Vivian Shaw; Shelley, Susanne M. (1972), Precalculus mathematics, New York: Holt, Rinehart and Winston, hlm. 182, ISBN 978-0-03-077670-0 .
2. Stifel, Michael (1544), Arithmetica integra (dalam bahasa Latin), hlm. 31 . A copy of the same table with two more entries appears on p. 237, and another copy extended to negative powers appears on p. 249b.
3. Euler, Leonhard (1739), "Chapter VII. De Variorum Intervallorum Receptis Appelationibus", Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae (dalam bahasa Latin), Saint Petersburg Academy, hlm. 102–112 .
4. Tegg, Thomas (1829), "Binary logarithms", London encyclopaedia; or, Universal dictionary of science, art, literature and practical mechanics: comprising a popular view of the present state of knowledge, Volume 4, hlm. 142–143 .
5. Templat:Introduction to Algorithms
6. Sedgewick, Robert; Wayne, Kevin Daniel (2011), Algorithms, Addison-Wesley Professional, hlm. 185, ISBN 9780321573513 .
7. Knuth, Donald E. (1997), The Art of Computer Programming, Volume 1: Fundamental Algorithms (edisi ke-3rd), Addison-Wesley Professional, ISBN 9780321635747 , p. 11. The same notation was in the 1973 2nd edition of the same book (p. 23) but without the credit to Reingold.
8. Trucco, Ernesto (1956), "A note on the information content of graphs", Bull. Math. Biophys., 18: 129–135, doi:10.1007/BF02477836, MR 0077919 .
9. Mitchell, John N. (1962), "Computer multiplication and division using binary logarithms", IRE Transactions on Electronic Computers, EC-11 (4): 512–517, doi:10.1109/TEC.1962.5219391 .
10. Fiche, Georges; Hebuterne, Gerard (2013), Mathematics for Engineers, John Wiley & Sons, hlm. 152, ISBN 9781118623336, In the following, and unless otherwise stated, the notation log x always stands for the logarithm to the base 2 of x .
11. Cover, Thomas M.; Thomas, Joy A. (2012), Elements of Information Theory (edisi ke-2nd), John Wiley & Sons, hlm. 33, ISBN 9781118585771, Unless otherwise specified, we will take all logarithms to base 2 .
12. Goodrich, Michael T.; Tamassia, Roberto (2002), Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, hlm. 23, One of the interesting and sometimes even surprising aspects of the analysis of data structures and algorithms is the ubiquitous presence of logarithms ... As is the custom in the computing literature, we omit writing the base b of the logarithm when b = 2. 
13. For instance, see Bauer, Friedrich L. (2009), Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum, Springer Science & Business Media, hlm. 54, ISBN 9783642029929 .
14. For DIN 1302 see Brockhaus Enzyklopädie in zwanzig Bänden [Brockhaus Encyclopedia in Twenty Volumes] (dalam bahasa Jerman), 11, Wiesbaden: F.A. Brockhaus, 1970, hlm. 554, ISBN 978-3-7653-0000-4 .
15. For ISO 31-11 see Thompson, Ambler; Taylor, Barry M (March 2008), Guide for the Use of the International System of Units (SI) — NIST Special Publication 811, 2008 Edition — Second Printing (PDF), NIST, hlm. 33 .
16. For ISO 80000-2 see "Quantities and units – Part 2: Mathematical signs and symbols to be used in the natural sciences and technology" (PDF), International Standard ISO 80000-2 (edisi ke-1st), December 1, 2009, Section 12, Exponential and logarithmic functions, p. 18 .
17. Van der Lubbe, Jan C. A. (1997), Information Theory, Cambridge University Press, hlm. 3, ISBN 9780521467605 .
18. Leiss, Ernst L. (2006), A Programmer's Companion to Algorithm Analysis, CRC Press, hlm. 28, ISBN 9781420011708 .
19. Ekuivalennya, sebuah keluarga dengan k anggota berbeda punya maksimal 2^k himpunan berbeda, dengan nilainya sama persis apabila keluarganya merupakan himpunan kuasa.
20. (Sedgewick & Wayne 2011), p. 186.
21. Cormen et al., p. 156; Goodrich & Tamassia, p. 238.
22. Cormen et al., p. 276; Goodrich & Tamassia, p. 159.
23. Cormen et al., pp. 879–880; Goodrich & Tamassia, p. 464.
24. Edmonds, Jeff (2008), How to Think About Algorithms, Cambridge University Press, hlm. 302, ISBN 9781139471756 .
25. Cormen et al., p. 844; Goodrich & Tamassia, p. 279.
26. Causton, Helen; Quackenbush, John; Brazma, Alvis (2009), Microarray Gene Expression Data Analysis: A Beginner's Guide, John Wiley & Sons, hlm. 49–50, ISBN 9781444311563 .
27. Eidhammer, Ingvar; Barsnes, Harald; Eide, Geir Egil; Martens, Lennart (2012), Computational and Statistical Methods for Protein Quantification by Mass Spectrometry, John Wiley & Sons, hlm. 105, ISBN 9781118493786 .
28. Campbell, Murray; Greated, Clive (1994), The Musician's Guide to Acoustics, Oxford University Press, hlm. 78, ISBN 9780191591679 .
29. France, Robert (2008), Introduction to Physical Education and Sport Science, Cengage Learning, hlm. 282, ISBN 9781418055295 .
30. Allen, Elizabeth; Triantaphillidou, Sophie (2011), The Manual of Photography, Taylor & Francis, hlm. 228, ISBN 9780240520377 .
31. Davis, Phil (1998), Beyond the Zone System, CRC Press, hlm. 17, ISBN 9781136092947 .
32. Zwerman, Susan; Okun, Jeffrey A. (2012), Visual Effects Society Handbook: Workflow and Techniques, CRC Press, hlm. 205, ISBN 9781136136146 .
33. "7.12.6.10 The log2 functions", ISO/IEC 9899:1999 specification (PDF), hlm. 226 .

Pranala luar

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