Catatan si Jay

November 7, 2010

Algoritma Logaritma

Filed under: Algoritma, Logaritma, Matematika — Hendra Jaya @ 12:17 pm

Referensi

Binary Logarithm

Pra-Pembahasan

Artikel ini akan membahas implementasi teknis tentang algoritma menghitung logaritma. Dimulai dari logaritma basis 2 (binary logarithm) sampai ke basis yang lain. Artikel ini mengasumsikan pembaca sudah memahami sifat-sifat dasar logaritma seperti :

\begin{array}{lll}log_a(a)&=&1\\log_a(a^n)&=&n\\log_a(x^y)&=&y.log_a(x)\\log_a(xy)&=&log_a(x)+log_a(y)\\log_a(\frac{x}{y})&=&log_a(x)-log_a(y)\end{array}

Logaritma dalam basis 2 secara matematis dinyatakan sebagai log_2(x) atau ada pula yang menuliskan lb(x)

Pembahasan

Setiap bilangan real positif x selalu dapat ditulis dalam basis 2 (biner), maka berlaku 2^n\leq x<2^{n+1} dimana n\in\mathbb{Z}.
Perhatikan bahwa persamaan 2^n=x hanya terjadi jika dan hanya jika x adalah bilangan kelipatan 2 (power of two).

Sebagai contoh :

\begin{array}{llcllcrlllr}2^0&\leq&1&<&2^1&\text{artinya}&0&\leq&log_2(1)&<&1\\2^1&\leq&2&<&2^2&\text{artinya}&1&\leq&log_2(2)&<&2\\2^2&\leq&4&<&2^3&\text{artinya}&2&\leq&log_2(4)&<&3\\2^-1&\leq&0.5&<&2^0&\text{artinya}&-1&\leq&log_2(0.5)&<&0\\2^0&\leq&1.414&<&2^1&\text{artinya}&0&\leq&log_2(1.414)&<&1\\2^2&\leq&6.5796&<&2^3&\text{artinya}&2&\leq&log_2(6.5796)&<&3\\2^6&\leq&64&<&2^7&\text{artinya}&6&\leq&log_2(64)&<&7\\2^{-4}&\leq&\frac{1}{16}&<&2^{-3}&\text{artinya}&-4&\leq&log_2(\frac{1}{16})&<&-3\\2^3&\leq&10&<&2^4&\text{artinya}&3&\leq&log_2(10)&<&4\end{array}

Secara sekilas dapat kita lihat bahwa log_2(x) tidak selalu berupa bilangan bulat. Nilai log_2(x) hanya akan bulat, yaitu n, jika dan hanya jika x adalah bilangan kelipatan 2 (power of two). Hal ini senada dengan paragraf sebelumnya.

Namun, untuk log_2(x) yang tidak bulat, maka nilainya pasti berada di rentang n dan n+1.
Atau secara matematis log_2(x)=n+\text{suatu nilai yang tidak bulat}

Contoh lagi :

\begin{array}{lllll}log_2(1)&=&0\\log_2(2)&=&1\\log_2(4)&=&2\\log_2(0.5)&=&-1\\log_2(1.414)&=&0.4997&=&0+0.4997\\log_2(6.5796)&=&2.7179&=&2+0.7179\\log_2(64)&=&6\\log_2(\frac{1}{16})&=&-4\\log_2(10)&=&3.3219&=&3+0.3219\end{array}

Sekarang, melalui aljabar sederhana, kita bisa memperoleh :

\begin{array}{rlclll}2^n&\leq&x&<&2^{n+1}\\1&\leq&2^{-n}.x&<&2&\mbox{Kalikan ketiga bagian dengan }2^{-n}\\log_2(1)&\leq&log_2(2^{-n}.x)&<&log_2(2)&\mbox{Kenakan fungsi }log_2(x)\mbox{ pada ketiga bagian pertidaksamaan}\\ 0&\leq&log_2(2^{-n})+log_2(x)&<&1\\ 0&\leq&-n+log_2(x)&<&1\\ 0&\leq&log_2(y)&<&1&\mbox{Misalkan }log_2(y)=log_2(x)-n\\1&\leq&y&<&2\end{array}

Di dalam bagian terakhir pertidaksamaan kita peroleh 1\leq y<2 dimana log_2(x)=log_2(y)+n

Dari bentuk log_2(x)=log_2(y)+n, pembaca seharusnya dapat memaklumi bahwa n adalah bagian bulat (integer part) dari log_2(x) sedangkan log_2(y) adalah bagian tidak bulat (fractional part). Seperti sudah dijelaskan di beberapa paragraf sebelum ini.

Untuk menghitung bagian yang bulat dapat dilakukan dengan mudah. Yaitu cukup dengan mengalikan/membagi x dengan 2 secara terus menerus sampai diperoleh 1\leq x<2.

Mengingat nilai log_2(1) adalah 0 dan nilai dari log_2(2) adalah 1, maka nilai dari log_2(x) sekarang pasti berupa 0.abcd\ldots Nilai inilah yang dimaksud dengan “bagian tidak bulat”.

Lantas, bagaimana menghitung bagian yang tidak bulat-nya?

Untuk menghitung bagian yang tidak bulat akan kita lakukan trik “mengkuadratkan terus menerus”.

Karena 1\leq y<2, kuadratkan bagian tengah menjadi 1\leq y^2<2

Karena 1\leq y^2<2, kuadratkan bagian tengah menjadi 1\leq y^4<2

Karena 1\leq y^4<2, kuadratkan bagian tengah menjadi 1\leq y^8<2

Berhenti ketika 2\leq y^{2^m}<4.

Triknya cukup mudah dimengerti. Yaitu kuadratkan terus sampai bagian tengah lebih besar atau sama dengan 2.

Intermezzo

Mengapa trik ini dapat dipakai?

Suatu bilangan 1.abcd\ldots jika dikuadratkan berkali-kali pasti akan “berkembang” sehingga pada akhirnya menembus angka 2. Kita tidak tahu berapa kali “pengkuadratan” yang diperlukan. Yang pasti, cepat atau lambat pasti bilangan tersebut akan menembus angka 2.

Sebagai contoh angka 1.001 baru akan menembus 2 pada saat dipangkatkan dengan 694, yakni 1.001^{694}\geq 2.
Di lain pihak, angka 1.2 sudah menempus angka 2 saat dipangkatkan dengan 4, yakni 1.2^4\geq 2.

Mungkinkah bilangan tersebut – ketika menembus angka 2 – juga menembus angka 4?

Ketika menembus angka 2 yang pertama kalinya, bilangan tersebut tidak akan menembus angka 4 karena :

\begin{array}{llllll}1&\leq&x&<&2&\text{Saat ini }x<2\\1^2&\leq&x^2&<&2^2\\1&\leq&x^2&<&4&\text{Saat ini }x^2\geq2\end{array}

Saatnya kembali ke pembahasan algoritma logaritma.

Sekarang, jika kita misalkan z=y^{2^m}, tentu saja berlaku 2\leq z<4. Dengan membagi ketiga bagian pertidaksamaan dengan 2 kita peroleh 1\leq \frac{z}{2}<2

Karena 2\leq y^{2^m}<4 dan z=y^{2^m}, maka :

\begin{array}{rlll}z&=&y^{2^m}\\log_2(z)&=&log_2(y^{2^m})&\text{Kenakan fungsi }log_2(x)\text{ pada kedua sisi}\\log_2(z)&=&2^m.log_2(y)\\log_2(2.\frac{z}{2})&=&2^m.log_2(y)&\text{Identitas perkalian}\\log_2(2)+log_2(\frac{z}{2})&=&2^m.log_2(y)\\1+log_2(\frac{z}{2})&=&2^m.log_2(y)\\2^{-m}.(1+log_2(\frac{z}{2}))&=&log_2(y)&\text{Kalikan kedua sisi dengan } 2^{-m}\\2^{-m}+2^{-m}.log_2(\frac{z}{2})&=&log_2(y)\end{array}

Kita peroleh log_2(y)=2^{-m}+2^{-m}.log_2(\frac{z}{2}). Ingat bahwa sebelumya kita telah mengetahui bahwa 1\leq \frac{z}{2}<2, sehingga trik yang sama dapat kita lakukan :

Dengan meng-kuadratkan \frac{z}{2} secukupnya, kita peroleh 2\leq \frac{z}{2}^{2^n}<4

Misalkan w=\frac{z}{2}^{2^n}, maka 2\leq w<4 atau 1\leq \frac{w}{2}<2

\begin{array}{rll}w&=&\frac{z}{2}^{2^n}\\log_2(w)&=&log_2(\frac{z}{2}^{2^n})\\log_2(w)&=&2^n.log_2(\frac{z}{2})\\log_2(2.\frac{w}{2})&=&2^n.log_2(\frac{z}{2})\\log_2(2)+log_2(\frac{w}{2})&=&2^n.log_2(\frac{z}{2})\\1+log_2(\frac{w}{2})&=&2^n.log_2(\frac{z}{2})\\2^{-n}.(1+log_2(\frac{w}{2}))&=&log_2(\frac{z}{2})\\2^{-n}+2^{-n}.log_2(\frac{w}{2})&=&log_2(\frac{z}{2})\end{array}

Dengan men-substitusikan log_2(\frac{z}{2}), kita peroleh :

log_2(y)=2^{-m}+2^{-m}.(2^{-n}+2^{-n}.log_2(\frac{w}{2}))

Dengan teknik yang sama, kita peroleh log_2(\frac{w}{2})=2^{-o}+2^{-o}.log_2(\frac{v}{2}).

Lalu di-substitusikan menjadi :

log_2(y)=2^{-m}+2^{-m}.(2^{-n}+2^{-n}.(2^{-o}+2^{-o}.log_2(\frac{v}{2})))

Dan seterusnya…

Sehingga bentuk umum-nya dapat dituliskan sebagai : log_2(y)=2^{-m}+2^{-m}.(2^{-n}+2^{-n}.(2^{-o}+2^{-o}(\ldots)))

atau ekivalen dengan : log_2(y)=2^{-m}+2^{-m-n}+2^{-m-n-o}+\ldots

atau jika ditulis ke dalam bentuk yang lebih seragam : log_2(y)=2^{-m_1}+2^{-m_1-m_2}+2^{-m_1-m_2-m_3}+\ldots

Sampai disini kita telah dapat menghitung bagian tidak bulat (fractional part) dari log_2(x).
Dengan menggabungkan bagian bulatnya kita peroleh log_2(x)=n+2^{-m_1}+2^{-m_1-m_2}+2^{-m_1-m_2-m_3}+\ldots

Dimana :

x adalah sembarang bilangan real positif, x>0 dan x\in\mathbb{R}
n adalah bagian bulat dari log_2(x)
2^{-m_1}+2^{-m_1-m_2}+2^{-m_1-m_2-m_3}+\ldots adalah bagian tidak bulat dari log_2(x)
Galat dari algoritma ini sangat kecil. Yaitu kurang dari 2^{-(m_1+m_2+m_3+\ldots+m_i)}

Untuk mencari logaritma dalam basis lain dapat menggunakan invarian log_a(b)=\frac{log_2(b)}{log_2(a)}

Pseudo-Code Algoritma log_2(x) :

  1. Asumsikan bahwa kondisi x>0 terpenuhi
  2. Tentukan batas toleransi kesalahan, err, secukupnya.
  3. Bagian bulat :
    1. Ambil a=0
    2. Periksa salah satu rentang nilai yang memenuhi x :
      1. Jika x memenuhi x<1 : lanjut ke langkah 3.3
      2. Jika x memenuhi 1\leq x<2 : lompat ke langkah 4
      3. Jika x memenuhi x\geq 2 : lanjut ke langkah 3.4
    3. Lakukan :
      1. Kali x dengan 2
      2. Kurangi a dengan 1
      3. Periksa apakah kondisi x<1 masih terpenuhi.
        1. Jika masih terpenuhi, kembali ke langkah 3.3
        2. Jika sudah tidak terpenuhi, lompat ke langkah 4
    4. Lakukan :
      1. Bagi x dengan 2
      2. Tambahkan a dengan 1
      3. Periksa apakah kondisi x\geq 2 masih terpenuhi.
        1. Jika masih terpenuhi, kembali ke langkah 3.4
        2. Jika sudah tidak terpenuhi, lompat ke langkah 4
  4. Bagian tidak bulat :
    1. Ambil b=1
    2. Periksa apakah kondisi b>err terpenuhi.
      1. Jika terpenuhi : lanjut ke langkah 4.3
      2. Jika tidak terpenuhi : lompat ke langkah 5
    3. Periksa apakah kondisi 1\leq x<2 terpenuhi.
      1. Jika terpenuhi :
        1. Kuadratkan x
        2. Bagi b oleh 2
        3. Kembali ke langkah 4.2
      2. Jika tidak terpenuhi :
        1. Bagi x oleh 2
        2. Tambahkan a dengan b
        3. Kembali ke langkah 4.2
  5. Hasil akhir algoritma adalah a

Berikut penulis sajikan pseudo-code yang lebih formal :

Pseudo Code Binary Logarithm

Implementasi

Java : Ideone, PDF
C++ : Sabar subur
Python : Logarithm Function

Contoh eksekusi algoritma :

1. Contoh menghitung log_2(0.3)

Nilai x=0.3

Ambil err=10^{-2}=0.01

Periksa rentang :

\begin{array}{rr}\mbox{[TRUE]}&0<0.3<1\\\mbox{[FALSE]}&1\leq 0.3<2\\\mbox{[FALSE]}&2\leq 0.3\end{array}

Menghitung bagian bulat

Nilai a=0

\begin{array}{rrrllll}\mbox{[TRUE]}&0<0.3<1&x&=&2.(0.3)&=&0.6\\&&a&=&0-1&=&-1\\\\\mbox{[TRUE]}&0<0.6<1&x&=&2.(0.6)&=&1.2\\&&a&=&-1-1&=&-2\\\\\mbox{[FALSE]}&0<1.2<1\end{array}

Menghitung bagian tidak bulat

Nilai b=1

\begin{array}{rrrllll}\mbox{[FALSE]}&2\leq 1<4\\\mbox{[TRUE]}&1>0.01&x&=&1.2^2&=&1.44\\&&b&=&\frac{1}{2}&=&0.5\\\\\mbox{[FALSE]}&2\leq 1.44<4\\\mbox{[TRUE]}&0.5>0.01&x&=&1.44^2&=&2.0736\\&&b&=&\frac{0.5}{2}&=&0.25\\\\\mbox{[TRUE]}&2\leq 2.0736<4&x&=&\frac{2.0736}{2}&=&1.0368\\&&a&=&-2+0.25&=&-1.75\\\mbox{[TRUE]}&0.25>0.01&x&=&1.0368^2&=&1.0749542\\&&b&=&\frac{0.25}{2}&=&0.125\\\\\mbox{[FALSE]}&2\leq 1.0749542<4\\\mbox{[TRUE]}&0.125>0.01&x&=&1.0749542^2&=&1.1555266\\&&b&=&\frac{0.125}{2}&=&0.0625\\\\\mbox{[FALSE]}&2\leq 1.1555266<4\\\mbox{[TRUE]}&0.0625>0.01&x&=&1.1555266^2&=&1.3352417\\&&b&=&\frac{0.0625}{2}&=&0.03125\\\\\mbox{[FALSE]}&2\leq 1.3352417<4\\\mbox{[TRUE]}&0.03125>0.01&x&=&1.3352417^2&=&1.7828705\\&&b&=&\frac{0.0625}{2}&=&0.015625\\\\\mbox{[FALSE]}&2\leq 1.7828705<4\\\mbox{[TRUE]}&0.015625>0.01&x&=&1.7828705^2&=&3.1786274\\&&b&=&\frac{0.015625}{2}&=&0.0078125\\\\\mbox{[TRUE]}&2\leq 3.1786274<4&x&=&\frac{3.1786274}{2}&=&1.5893137\\&&a&=&-1.75+0.0078125&=&-1.7421875\\\mbox{[FALSE][STOP]}&0.0078125>0.01\end{array}

Hasil akhir

Dengan demikian log_2(0.3)\approx -1.7421875

2. Contoh menghitung log_2(1.4)

Nilai x=1.4

Ambil err=10^{-2}=0.01

Periksa rentang :

\begin{array}{rr}\text{[FALSE]}&0<1.4<1\\\text{[TRUE]}&1\leq 1.4<2\\\text{[FALSE]}&2\leq 1.4\end{array}

Menghitung bagian bulat

Nilai a=0

Menghitung bagian tidak bulat

Nilai b=1

\begin{array}{rrrllll}\text{[FALSE]}&2\leq 1<4\\\text{[TRUE]}&1>0.01&x&=&1.4^2&=&1.96\\&&b&=&\frac{1}{2}&=&0.5\\\\\text{[FALSE]}&2\leq 1.96<4\\\text{[TRUE]}&0.5>0.01&x&=&1.96^2&=&3.8416\\&&b&=&\frac{0.5}{2}&=&0.25\\\\\text{[TRUE]}&2\leq 3.8416<4&x&=&\frac{3.8416}{2}&=&1.9208\\&&a&=&0+0.25&=&0.25\\\text{[TRUE]}&0.25>0.01&x&=&1.9208^2&=&3.6894726\\&&b&=&\frac{0.25}{2}&=&0.125\\\\\text{[TRUE]}&2\leq 3.6894726<4&x&=&\frac{3.6894726}{2}&=&1.8447363\\&&a&=&0.25+0.125&=&0.375\\\text{[TRUE]}&0.125>0.01&x&=&1.8447363^2&=&3.403052\\&&b&=&\frac{0.125}{2}&=&0.0625\\\\\text{[TRUE]}&2\leq 3.403052<4&x&=&\frac{3.403052}{2}&=&1.701526\\&&a&=&0.375+0.0625&=&0.4375\\\text{[TRUE]}&0.0625>0.01&x&=&1.701526^2&=&2.8951908\\&&b&=&\frac{0.0625}{2}&=&0.03125\\\\\text{[TRUE]}&2\leq 2.8951908<4&x&=&\frac{2.8951908}{2}&=&1.4475954\\&&a&=&0.4375+0.03125&=&0.46875\\\text{[TRUE]}&0.03125>0.01&x&=&1.4475954^2&=&2.0955325\\&&b&=&\frac{0.0625}{2}&=&0.015625\\\\\text{[TRUE]}&2\leq 2.0955325<4&x&=&\frac{2.0955325}{2}&=&1.0477662\\&&a&=&0.46875+0.015625&=&0.484375\\\text{[TRUE]}&0.015625>0.01&x&=&1.0477662^2&=&1.0978141\\&&b&=&\frac{0.015625}{2}&=&0.0078125\\\\\text{[FALSE]}&2\leq 1.0978141<4\\\text{[FALSE][STOP]}&0.0078125>0.01\end{array}

Hasil akhir

Dengan demikian log_2(1.4)\approx 0.484375

3. Contoh menghitung log_2(11)

Nilai x=11

Ambil err=10^{-2}=0.01

Periksa rentang :

\begin{array}{rr}\text{[FALSE]}&0<11<1\\\text{[FALSE]}&1\leq 11<2\\\text{[TRUE]}&2\leq 11\end{array}

Menghitung bagian bulat :

Nilai a=0

\begin{array}{rrrllll}\text{[TRUE]}&11\geq 2&x&=&\frac{11}{2}&=&5.5\\&&a&=&0+1&=&1\\\\\text{[TRUE]}&5.5\geq 2&x&=&\frac{5.5}{2}&=&2.75\\&&a&=&1+1&=&2\\\\\text{[TRUE]}&2.75\geq 2&x&=&\frac{2.75}{2}&=&1.375\\&&a&=&2+1&=&3\\\\\text{[FALSE]}&1.375\geq 2\end{array}

Menghitung bagian tidak bulat :

Nilai b=1

\begin{array}{rrrllll}\text{[FALSE]}&2\leq 1<4\\\text{[TRUE]}&1>0.01&x&=&1.375^2&=&1.890625\\&&b&=&\frac{1}{2}&=&0.5\\\\\text{[FALSE]}&2\leq 1.890625<4\\\text{[TRUE]}&0.5>0.01&x&=&1.890625^2&=&3.5744628\\&&b&=&\frac{0.5}{2}&=&0.25\\\\\text{[TRUE]}&2\leq 3.5744628<4&x&=&\frac{3.5744628}{2}&=&1.7872314\\&&a&=&3+0.25&=&3.25\\\text{[TRUE]}&0.25>0.01&x&=&1.7872314^2&=&3.1941962\\&&b&=&\frac{0.25}{2}&=&0.125\\\\\text{[TRUE]}&2\leq 3.1941962<4&x&=&\frac{3.1941962}{2}&=&1.5970981\\&&a&=&3.25+0.125&=&3.375\\\text{[TRUE]}&0.125>0.01&x&=&1.5970981^2&=&2.5507224\\&&b&=&\frac{0.125}{2}&=&0.0625\\\\\text{[TRUE]}&2\leq 2.5507224<4&x&=&\frac{2.5507224}{2}&=&1.2753612\\&&a&=&3.375+0.0625&=&3.4375\\\text{[TRUE]}&0.0625>0.01&x&=&1.2753612^2&=&1.6265461\\&&b&=&\frac{0.0625}{2}&=&0.03125\\\\\text{[FALSE]}&2\leq 1.6265461<4\\\text{[TRUE]}&0.03125>0.01&x&=&1.6265461^2&=&2.6456525\\&&b&=&\frac{0.0625}{2}&=&0.015625\\\\\text{[TRUE]}&2\leq 2.6456525<4&x&=&\frac{2.6456525}{2}&=&1.3228262\\&&a&=&3.4375+0.015625&=&3.453125\\\text{[TRUE]}&0.015625>0.01&x&=&1.3228262^2&=&1.7498693\\&&b&=&\frac{0.015625}{2}&=&0.0078125\\\\\text{[FALSE]}&2\leq 1.7498693<4\\\text{[FALSE][STOP]}&0.0078125>0.01\end{array}

Hasil akhir :

Dengan demikian log_2(11)\approx 3.453125

Atas nama kerapihan, angka-angka pada perhitungan di atas telah “dipotong” dari angka yang sebenarnya. Pembaca mungkin akan mendapatkan angka yang berbeda jika meng-implementasi dan menjalnkan algoritma ini di dalam komputer ataupun kalkulator.

Hasil perhitungan-perhitungan di atas menggunakan ketelitian 0.01 dari hasil sebenarnya, sehingga ketika di-cross check akan memberikan angka yang tidak terlalu tepat.

Sebagai masukan, penulis biasanya menggunakan ketelitian 10^{-20} agar mendapatkan hasil yang cukup dekat dengan hasil yang sebenarnya. Selain itu, ketelitian tersebut masih sangat mungkin dilakukan pada tipe data “floating point” pada komputer 32 bit yang sehari-harinya penulis gunakan. Di dalam artikel ini, penulis secara sengaja menggunakan ketelitian 10^{-2} agar contoh eksekusi algoritma tidak terlalu panjang.

Sekali lagi, untuk mencari logaritma dalam basis lain dapat menggunakan invarian log_a(b)=\frac{log_2(b)}{log_2(a)}. Selamat mencoba.

Real Programmers Code in Binary

Tinggalkan sebuah Komentar »

Belum ada komentar.

RSS feed for comments on this post. TrackBack URI

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

Buat situs web atau blog gratis di WordPress.com.

%d blogger menyukai ini: