Persoalan motivasi:
Dalam pemrograman kompetitif, logaritma memang jarang digunakan. Bila diperlukan, biasanya bukan sebagai inti soal/algoritma utama. Artinya, logaritma bisa jadi seperti perkakas yang dibutuhkan untuk menyelesaikan soal. Tanpa perkakas itu, soal tidak dapat terselesaikan meskipun kita tahu algoritma utamanya. Oleh karena itu saya harap tulisan ini dapat membekali Anda :)
\(\displaystyle\log_{a}{x} = \frac{\log_{p}{x}}{\log_{p}{a}}\)
Sehingga menghitung logaritma basis 2 dari 1024 dapat dilakukan dengan log(1024)/log(2).
Invers dari fungsi log(x) adalah exp(x). Fungsi exp(x) akan mengembalikan hasil dari ex. Dengan begitu, dipenuhi log(exp(x)) = x.
\(\displaystyle\frac{a^b}{c!} = e^{\log{\frac{a^b}{c!} } }\)
Yang mana:
\(\displaystyle
\begin{eqnarray*}
\log{\frac{a^b}{c!}} &=& \log{a^b} - \log{c!}\\
&=& b \log{a} - \log{(1 \times 2 \times 3 \times ... \times c)}\\
&=& b \log{a} - (\log{1} + \log{2} + \log{3} + ... + \log{c})\\
\end{eqnarray*}
\)
Sekarang tidak ada lagi bilangan yang nilainya besar dan komputasi dapat dilakukan :)
Anda juga dapat memanfaatkannya untuk membandingkan dua bilangan yang besar. Misalnya ab dengan c!. Cukup periksa mana yang lebih besar, log(ab) atau log(c!).
Dengan cara yang sama Anda juga dapat mengetahui banyaknya digit dari ab atau a!.
Intinya, Misalkan N memiliki D digit (cari dengan cara yang sebelumnya dijelaskan). Cukup bagi N dengan 10D-K. Untuk N yang besar (misalnya dalam bentuk pangkat atau faktorial), perhitungan dapat dilakukan dengan logaritma sebagai berikut:
\(\displaystyle\begin{eqnarray*}\log{\frac{N}{10^{D-K}}} &=& \log{N} - \log{10^{D-K}}\\
&=& \log{N} - (D-K)\log{10} \end{eqnarray*}\)
Hasil dari ekspresi itu tinggal dipangkatkan oleh e, lalu bulatkan ke bawah.
Bandingkan dengan:
Program tersebut berguna untuk mencari nilai dari a×(a+1)×(a+2)×...×(b). Cara pertama memang lebih efisien apabila ada banyak kasus uji, tetapi akumulasi precision error-nya terlalu besar. Saya pernah mendapatkan WA karena hal tersebut, oleh karena itu hati-hatilah dalam melakukan perhitungan.
- Diberikan dua bilangan bulat a dan b (1 ≤ a, b ≤ 108). Apa tiga digit pertama dari ab?
- Diberikan sebuah bilangan bulat N (1 ≤ N ≤ 105). Tentukan banyaknya digit dari N faktorial!
- Diberikan sebuah bilangan bulat N. Tentukan K, sedemikian sehingga NK lebih kecil dari K faktorial!
- Diberikan sebuah bilangan genap n. Tentukan \(\displaystyle \frac{C^{N}_{N/2}}{2^N}\)!
Dalam pemrograman kompetitif, logaritma memang jarang digunakan. Bila diperlukan, biasanya bukan sebagai inti soal/algoritma utama. Artinya, logaritma bisa jadi seperti perkakas yang dibutuhkan untuk menyelesaikan soal. Tanpa perkakas itu, soal tidak dapat terselesaikan meskipun kita tahu algoritma utamanya. Oleh karena itu saya harap tulisan ini dapat membekali Anda :)
Logaritma Natural
Baik C++ maupun Pascal, logaritma disajikan dalam bentuk fungsi log(x). Fungsi tersebut bekerja dalam basis e (bilangan natural, sama dengan 2.81...). Oleh karena itu untuk menghitung logaritma basis 2 dari 1024, bisa digunakan sifat:\(\displaystyle\log_{a}{x} = \frac{\log_{p}{x}}{\log_{p}{a}}\)
Sehingga menghitung logaritma basis 2 dari 1024 dapat dilakukan dengan log(1024)/log(2).
Invers dari fungsi log(x) adalah exp(x). Fungsi exp(x) akan mengembalikan hasil dari ex. Dengan begitu, dipenuhi log(exp(x)) = x.
Pertumbuhan Fungsi Logaritma
Hal yang mengagumkan dari logaritma adalah pertumbuhan nilainya yang sangat lambat. Misalkan kita memiliki barisan 1, 2, 4, 8, 16, .... Barisan tersebut tumbuh dengan sangat cepat. Sementara barisan log(1), log(2), log(4), log(8), log(16), ... tumbuh dengan sangat lambat. Sebagai perbandingan, suku ke-30 dari barisan pertama adalah 1152921504606846976, sementara untuk barisan kedua hanya 18.06. Bahkan untuk 2100, nilai log-nya hanya sekitar 30.
Pertumbuhan nilai yang lambat
Kompresi Bilangan
Pertumbuhan nilai yang lambat ini dimanfaatkan untuk mengkompresi bilangan (terutama faktorial atau pemangkatan), sehingga nilainya tetap rendah. Sebagai contoh, diberikan a, b, dan c, hitung ab/c! dan dijamin bahwa hasilnya di antara 1 sampai 109. Salah satu solusinya adalah dengan melakukan komputasinya dalam logaritma, lalu dikembalikan hasilnya dengan pemangkatan oleh e. Berikut penjabarannya:\(\displaystyle\frac{a^b}{c!} = e^{\log{\frac{a^b}{c!} } }\)
Yang mana:
\(\displaystyle
\begin{eqnarray*}
\log{\frac{a^b}{c!}} &=& \log{a^b} - \log{c!}\\
&=& b \log{a} - \log{(1 \times 2 \times 3 \times ... \times c)}\\
&=& b \log{a} - (\log{1} + \log{2} + \log{3} + ... + \log{c})\\
\end{eqnarray*}
\)
Sekarang tidak ada lagi bilangan yang nilainya besar dan komputasi dapat dilakukan :)
Anda juga dapat memanfaatkannya untuk membandingkan dua bilangan yang besar. Misalnya ab dengan c!. Cukup periksa mana yang lebih besar, log(ab) atau log(c!).
Menghitung Banyaknya Digit Bilangan
Setiap bilangan bisa dinyatakan dalam a × 10b. Bila dipenuhi |a| < 1, maka b menyatakan banyaknya digit dari bilangan tersebut. Dengan memanfaatkan fakta ini, mencari banyaknya digit dari N bisa dilakukan dengan menghitung \(\lfloor\log_{10}{N}\rfloor\).Dengan cara yang sama Anda juga dapat mengetahui banyaknya digit dari ab atau a!.
Mengetahui Beberapa Digit Pertama Suatu Bilangan
Misalnya kita tertarik dengan K digit pertama dari bilangan N. Salah satu cara yang dapat dilakukan adalah membagi N dengan 10x sedemikian sehingga hanya bilangan itu menjadi lebih kecil dari 10K, lalu bulatkan ke bawah. Hasilnya adalah K digit pertama dari N. Contohnya, bila N = 1234567890 (memiliki 10 digit) dan K = 3, maka bagi N dengan 107. Hasilnya adalah 123.4567890. Setelah dibulatkan ke bawah, hasilnya 123.Intinya, Misalkan N memiliki D digit (cari dengan cara yang sebelumnya dijelaskan). Cukup bagi N dengan 10D-K. Untuk N yang besar (misalnya dalam bentuk pangkat atau faktorial), perhitungan dapat dilakukan dengan logaritma sebagai berikut:
\(\displaystyle\begin{eqnarray*}\log{\frac{N}{10^{D-K}}} &=& \log{N} - \log{10^{D-K}}\\
&=& \log{N} - (D-K)\log{10} \end{eqnarray*}\)
Hasil dari ekspresi itu tinggal dipangkatkan oleh e, lalu bulatkan ke bawah.
Masalah Presisi
Meskipun logaritma dapat mengkompresi bilangan, tidak ada jaminan bahwa hasilnya akurat. Anda harus terampil dalam meminimalisasi precision error, entah dengan menggunakan nilai epsilon dalam pembulatan atau dengan melakukan komputasi dengan baik. Perhatikan kode berikut:Bandingkan dengan:
Program tersebut berguna untuk mencari nilai dari a×(a+1)×(a+2)×...×(b). Cara pertama memang lebih efisien apabila ada banyak kasus uji, tetapi akumulasi precision error-nya terlalu besar. Saya pernah mendapatkan WA karena hal tersebut, oleh karena itu hati-hatilah dalam melakukan perhitungan.
Hati-Hati dengan Overflow dan Underflow!
Biasanya tipe data double memang cukup untuk jangkauan nilai yang besar dan kecil. Namun jangan minta double untuk menampung 2-50000 atau 1000 faktorial. Ingat bahwa kompresi bilangan yang sebelumnya saya paparkan hanya berlaku dalam operasi intermediet, dan hasil akhir dijamin memiliki nilai yang dapat ditampung oleh bilangan double.Penutup
Demikian pengetahuan yang ingin saya bagikan. Sebagai latihan, Anda dapat mengerjakan soal:- SPOJ - FACVSPOW
- UVa 10883 - Supermean
- UVa 11029 - Leading and Trailing
- UVa 10398 - The Golden Pentagon
Tidak ada komentar :
Posting Komentar