Algoritma Logaritma

November 7, 2010

Algoritma Logaritma

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

Referensi

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)$ :

Asumsikan bahwa kondisi $x>0$ terpenuhi
Tentukan batas toleransi kesalahan, $err$ , secukupnya.
Bagian bulat :
1. Ambil $a=0$
2. Periksa salah satu rentang nilai yang memenuhi :
  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 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 masih terpenuhi.
    1. Jika masih terpenuhi, kembali ke langkah 3.4
    2. Jika sudah tidak terpenuhi, lompat ke langkah 4
Bagian tidak bulat :
1. Ambil $b=1$
2. Periksa apakah kondisi terpenuhi.
  1. Jika terpenuhi : lanjut ke langkah 4.3
  2. Jika tidak terpenuhi : lompat ke langkah 5
3. Periksa apakah kondisi 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
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.