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

Oktober 19, 2010

Faktor Persekutuan Terbesar (FPB) & Kelipatan Persekutuan Terkecil (KPK)

Filed under: Algoritma, Matematika, Teori Bilangan — Hendra Jaya @ 7:34 am

Faktor Persekutuan Terbesar

Faktor Persekutuan Terbesar (FPB) di dalam bahasa Inggris disebut dengan Greatest Common Divisor (GCD). Untuk membiasakan pembaca dengan istilah yang umum dipakai di dalam matematika, artikel ini akan menggunakan GCD alih-alih FPB.

Definisi : GCD dari dua buah bilangan bulat tidak nol a dan b adalah bilangan bulat positif terbesar d yang habis membagi baik a maupun b.
Secara matematis : gcd(a,b)=max\{d|a\text{ dan }d|b,d\in\mathbb{Z_+}\}
Secara komputatif : gcd(a,b)=d

Contoh 1 :
Faktor-faktor positif (positive divisors) dari 12 adalah : 1, 2, 3, 4, 6, 12
Faktor-faktor positif (positive divisors) dari 18 adalah : 1, 2, 3, 6, 9, 18
Faktor bersama (common divisors) dari 12 dan 18 adalah : 1, 2, 3, 6.
Faktor bersama yang paling besar (Greatest Common Divisor) dari 12 dan 18 adalah : 6.
gcd(12,18)=6
gcd(18,12)=6

Pada contoh di atas, 12 dan 18 memiliki beberapa faktor yang sama. Faktor-faktor tersebut adalah 1, 2, 3, dan 6. Dari ke-empat faktor bersama ini, tentu saja ada yang terbesar. Yang terbesar adalah 6. Faktor bersama yang terbesar inilah yang disebut dengan Greatest Common Divisor (GCD). Dalam contoh ini, dapat disimpulkan bahwa gcd(12,18)=6.

Contoh 2 :
Faktor-faktor positif (positive divisors) dari 15 adalah : 1, 3, 5, 15
Faktor-faktor positif (positive divisors) dari 20 adalah : 1, 2, 4, 5, 10, 20
Faktor bersama (common divisors) dari 15 dan 20 adalah : 1, 5
Faktor bersama yang paling besar (Greatest Common Divisor) dari 15 dan 20 adalah : 5.
gcd(15,20)=5
gcd(20,15)=5

Contoh 3 :
Faktor-faktor positif (positive divisors) dari 6 adalah : 1, 2, 3, 6
Faktor-faktor positif (positive divisors) dari 24 adalah : 1, 2, 3, 4, 6, 8, 12, 24
Faktor bersama (common divisors) dari 6 dan 24 adalah : 1, 2, 3, 6
Faktor bersama yang paling besar (Greatest Common Divisor) dari 6 dan 24 adalah : 6.
gcd(6,24)=6
gcd(24, 6)=6

Contoh 4 :
Faktor-faktor positif (positive divisors) dari 10 adalah : 1, 2, 5, 10
Faktor-faktor positif (positive divisors) dari 7 adalah : 1, 7
Faktor bersama (common divisors) dari 10 dan 7 adalah : 1
Faktor bersama yang paling besar (Greatest Common Divisor) dari 10 dan 7 adalah : 1.
gcd(10,7)=1
gcd(7,10)=1

Contoh 5 :
Faktor-faktor positif (positive divisors) dari 15 adalah : 1, 3, 5, 15
Faktor-faktor positif (positive divisors) dari 10 adalah : 1, 2, 5, 10
Faktor bersama (common divisors) dari 15 dan 10 adalah : 1, 5
Faktor bersama yang paling besar (Greatest Common Divisor) dari 15 dan 10 adalah : 5.
gcd(15,10)=5
gcd(10,15)=5

Contoh 6 :
Faktor-faktor positif (positive divisors) dari 4 adalah : 1, 2, 4
Faktor-faktor positif (positive divisors) dari 9 adalah : 1, 3, 9
Faktor bersama (common divisors) dari 4 dan 9 adalah : 1
Faktor bersama yang paling besar (Greatest Common Divisor) dari 4 dan 9 adalah : 1.
gcd(4,9)=1
gcd(9,4)=1

Intermezzo : Pada contoh ke-4 dan ke-6, GCD dari 10 dan 7 dan juga GCD dari 4 dan 9 adalah 1. Di dalam dunia matematika, jika GCD dari dua buah bilangan bulat a dan b bernilai 1 maka  kedua bilangan tersebut dikatakan relatif prima (relatively prime). Ada juga yang menyebutnya koprima (coprime). Blog ini menggunakan istilah koprima. Tentang “mengapa” matematikawan menggunakan istilah relatif prima/koprima, tentu ada sebabnya. Hal itu belum akan kita bahas di artikel ini. Sebagai gambaran saja, hal ini memang erat kaitannya dengan bilangan prima.

Dalam teori himpunan, a dan b dikatakan koprima jika himpunan faktor-faktor a dan himpunan faktor-faktor b saling lepas. Seperti pada gambar berikut :

coprime

Perhatikan bahwa GCD bersifat komutatif, yaitu gcd(a,b)=gcd(b,a). Penulis kira hal ini sudah cukup jelas, sehingga tidak perlu disediakan ruang khusus untuk membahasnya.

Teknik Menghitung GCD

Sebelum masuk ke dalam teknik menghitung GCD. Kita akan mundur sebentar ke dalam algoritma pembagian.

Misalkan gcd(a,b)=d. Sesuai dengan definisi, d pasti habis membagi a dan juga habis membagi b. Jika definisi ini kita tuangkan ke dalam algoritma pembagian, kita akan memperoleh :
a=x.d
b=y.d

Menurut algoritma pembagian, a dapat dituliskan sebagai a=q.b+r. Arti dari persamaan ini adalah “jika a dibagi dengan b, maka kita akan memperoleh sisa bagi (remainder) r yang memenuhi 0\leq r<|b|“.

Dengan men-substitusikan persamaan a=q.b+r, kita memperoleh q.b+r=x.d

Karena kita tahu bahwa b=y.d, kita substitusikan persamaan ini sehingga mendapatkan q.y.d+r=x.d

Tidak perlu diragukan lagi, sisi kanan dari persamaan, yaitu x.d, pasti habis dibagi dengan d. Begitu pula dengan q.y.d.

Lantas, apakah r pasti habis dibagi d? Karena “temannya” r, yaitu q.y.d sudah memberikan kepastian bahwa dia pasti habis dibagi oleh d, maka mau tidak mau r pasti habis juga dibagi d. Karena r habis dibagi oleh d, berarti d adalah divisor (faktor) dari r.

Bagaimana jika d tidak habis membagi r? Itu artinya d bukan gcd dari a dan b (kontradiktif). Habis perkara.

Di paragraf sebelumnya, secara logis kita telah menyimpulkan bahwa d adalah salah satu dari sekian banyak faktor (divisor) dari r. Pertanyaan logis berikutnya adalah “Faktor (divisor) yang mana?”. Lagi-lagi, karena kita bicara soal faktor terbesar (greatest divisor), jawabannya adalah “sebesar mungkin”.

Misalkan r memiliki sekian banyak faktor positif, sebut saja r_1,r_2,r_3,...r_n. Faktor mana yang akan kita pilih? Karena kita berusaha mencari “faktor terbesar yang mungkin”, kita akan lakukan pemeriksaan mulai dari yang paling kanan, yaitu r_n,r_{n-1},...r_3,r_2,r_1. Kita akan memeriksa apakah sebuah faktor, sebut saja r_i, habis membagi b.

Pemeriksaan berakhir jika r_i alias d terbukti habis membagi b.

Mengapa hanya b? Mengapa a tidak? Kita hanya memeriksa b karena itu sudah cukup (syarat cukup) untuk menjamin bahwa a juga pasti habis dibagi oleh d. Penjelasannya adalah sebagai berikut :

Perhatikan persamaan q.b+r=a.

Karena r_i adalah faktor dari r, maka kita boleh menulis persamaan di atas menjadi q.b+n.r_i=a. Tidak perlu pusing dengan variabel-variabel “dummy” seperti q dan n. Kita tidak tertarik untuk membahasnya.

Sekarang, jika r_i habis membagi b, maka persamaan dapat kita tulis ulang menjadi q.m.r_i+n.r_i=a. Sekali lagi, abaikan semua variabel-variabel tidak penting seperti q, m dan n.

Dengan memanfaatkan sifat distributif perkalian, kita memperoleh r_i.(q.m+n)=a.

Nah, sekarang jelas terlihat bahwa a juga pasti habis dibagi oleh r_i. Dengan demikian, pemeriksaan terhadap b sudah cukup (syarat cukup) untuk meyakinkan kita bahwa a tidak perlu diperiksa lagi.

Hal ini sangat menarik. Pemeriksaan yang kita lakukan di beberapa paragraf sebelumnya sebenarnya mencari faktor bersama (common divisor) yang habis membagi baik r, maupun b. Karena pemeriksaan dilakukan dari “kanan”, maka r_i yang memenuhi kriteria ini pastilah faktor bersama yang terbesar (greatest common divisor) yang dimiliki baik oleh r, maupun oleh b.

Apa yang sebenarnya kita lakukan di beberapa paragraf sebelumnya adalah mencari GCD dari r dan b. Aneh bukan? Memang benar bahwa di awal sekali, kita ingin mencari GCD dari a dan b. Tetapi, analisa matematika membuktikan bahwa GCD dari a dan b sebenarnya sama dengan GCD dari r dan b. Dimana r adalah sisa bagi a oleh b :

\begin{array}{ccl} gcd(a, b)& =& gcd(r, b) \\ gcd(a, b)& =& gcd(b, r) \\ gcd(a, b)& =& gcd(b, mod(a, b)) \end{array}

Fenomena ini pertama kali diamati oleh Euclid sekitar 2300 tahun yang lalu dan sampai saat ini masih dipelajari di sekolah-sekolah dan kampus-kampus di seluruh dunia.

Teknik pencarian GCD dari a dan b yang diajukan oleh Euclid adalah sebagai berikut :

  1. Jika b=0, maka GCD dari a dan b adalah a.
  2. Jika b\neq 0, maka :
    1. Carilah r, yaitu sisa bagi a oleh b.
    2. Anggap b sebagai a dan r sebagai b.
    3. Kembali ke step 1

Contoh 1 (lagi) : Menghitung gcd(12,18)

  • a = 12, b = 18.
  • Karena 18 \neq 0, maka :
  • 12 = 0.18 + 12, sehingga r = 12.
    • a = 18, b = 12
    • Karena 12 \neq 0, maka :
    • 18 = 1.12 + 6, sehingga r = 6
      • a = 12, b = 6
      • Karena 6 \neq 0, maka :
      • 12 = 2.6 + 0, sehingga r = 0
        • a = 6, b = 0
        • Karena 0 = 0, maka hasilnya adalah 6.

Secara grafis :

gcd

Contoh 2 (lagi) : Menghitung gcd(15, 20)

  • a = 15, b = 20.
  • Karena 20 \neq 0, maka :
  • 15 = 0.20 + 15, sehingga r = 15.
    • a = 20, b = 15
    • Karena 15 \neq 0, maka :
    • 20 = 1.15 + 5, sehingga r = 5
      • a = 15, b = 5
      • Karena 5 \neq 0, maka :
      • 15 = 3.5 + 0, sehingga r = 0
        • a = 5, b = 0
        • Karena 0 = 0, maka hasilnya adalah 5.

Secara grafis :

gcd

Contoh 3 (lagi) : Menghitung gcd(6, 24)

  • a = 6, b = 24.
  • Karena 24 \neq 0, maka :
  • 6 = 0.24 + 6, sehingga r = 6.
    • a = 24, b = 6
    • Karena 6 \neq 0, maka :
    • 24 = 4.6 + 0, sehingga r = 0
      • a = 6, b = 0
      • Karena 0 = 0, maka hasilnya adalah 6.

Secara grafis :

gcd

Contoh 4 (lagi) : Menghitung gcd(10, 7)

  • a = 10, b = 7.
  • Karena 7 \neq 0, maka :
  • 10 = 1.7 + 3, sehingga r = 3.
    • a = 7, b = 3
    • Karena 3 \neq 0, maka :
    • 7 = 2.3 + 1, sehingga r = 1
      • a = 3, b = 1
      • Karena 1 \neq 0, maka :
      • 3 = 3.1 + 0, sehingga r = 0
        • a = 1, b = 0
        • Karena 0 = 0, maka hasilnya adalah 1.

Secara grafis :

gcd

Contoh 5 (lagi) : Menghitung gcd(15, 10)

  • a = 15, b = 10.
  • Karena 10 \neq 0, maka :
  • 15 = 1.10 + 5, sehingga r = 5.
    • a = 10, b = 5
    • Karena 5 \neq 0, maka :
    • 10 = 2.5 + 0, sehingga r = 0
      • a = 5, b = 0
      • Karena 0 = 0, maka hasilnya adalah 5.

Secara grafis :

gcd

Contoh 6 (lagi) : Menghitung gcd(4, 9)

  • a = 4, b = 9.
  • Karena 9 \neq 0, maka :
  • 4 = 0.9 + 4, sehingga r = 4.
    • a = 9, b = 4
    • Karena 4 \neq 0, maka :
    • 9 = 2.4 + 1, sehingga r = 1
      • a = 4, b = 1
      • Karena 1 \neq 0, maka :
      • 4 = 4.1 + 0, sehingga r = 0
        • a = 1, b = 0
        • Karena 0 = 0, maka hasilnya adalah 1.

Secara grafis :

gcd

Better Luck Next Year

Satu pertanyaan yang paling sering dilontarkan adalah : “Mengapa b dianggap a dan r dianggap b?”.

Sebenarnya, teknik asli yang dilontarkan oleh Euclid mengharuskan a \geq b. Jika ternyata ditemukan bahwa a < b, maka Euclid mengharuskan kedua bilangan itu dipertukarkan. Ingat bahwa gcd adalah sebuah fungsi yang komutatif dimana gcd(a,b)=gcd(b,a) sehingga mempertukarkan posisi a dengan b tidak akan mengubah hasil perhitungan.

Akan tetapi, dengan majunya ilmu komputasi, “penganggapan” b sebagai a dan r sebagai b, terbukti lebih efisien karena kita tidak perlu pusing-pusing memeriksa apakah a \geq b.
Hal ini dapat dijelaskan melalui algoritma pembagian yang telah memberikan kepastian bahwa 0\leq r<|b|. Sehingga, step untuk memeriksa invarian (relasi) a\geq b tidak perlu dilakukan lagi.

Bagaimana jika salah satu atau keduanya dari a dan b adalah bilangan negatif?

Hal ini juga sangat sering ditanyakan. Pembahasan tentang pertanyaan ini akan kita tunda dulu. Pembahasan lengkapnya akan kita bahas di artikel “Sifat-sifat GCD dan LCM”. Ide utamanya adalah bilangan negatif merupakan suatu perkalian bilangan positif dengan -1.

Kelipatan Persekutuan Terkecil

Kelipatan Persekutuan Terkecil (KPK) di dalam bahasa Inggris dikenal dengan nama Least Common Multiple (LCM). Sama seperti GCD, blog ini akan membiasakan pembaca untuk menggunakan istilah yang lazim dipakai. Oleh karena itu blog ini akan menggunakan istilah LCM.

Definisi : LCM dari dua buah bilangan bulat a dan b adalah bilangan bulat positif terkecil yang merupakan kelipatan bersama dari a dan b.
Secara matematis : lcm(a,b)=\frac{|a.b|}{gcd(a, b)}
Secara komputatif : lcm(a, b)=\frac{abs(a.b)}{gcd(a, b)}
Catatan : definisi asli dari LCM menggunakan “bilangan rasional”. Artikel ini menyederhanakan definisi tersebut ke dalam “bilangan bulat” agar lebih mudah dipahami.

Contoh 1 :
Kelipatan (multiple) dari 12 adalah : 12, 24, 36, 48, 60, 72, 84, 96, 108, …
Kelipatan (multiple) dari 18 adalah : 18, 36, 54, 72, 90, 108, …
Kelipatan bersama (common multiple) dari 12 dan 18 adalah : 36, 72, 108, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 12 dan 18 adalah : 36.
lcm(12,18)=36
lcm(18,12)=36

Pada contoh di atas, 12 dan 18 memiliki banyak kelipatan yang sama. Kelipatan-kelipatan tersebut adalah 36, 72, 108, …. Dari semua kelipatan-kelipatan ini, yang terkecil adalah 36. Kelipatan bersama yang terkecil inilah yang disebut dengan Least Common Multiple (LCM). Dalam contoh ini, terlihat bahwa lcm(12,18)=36.

Contoh 2 :
Kelipatan (multiple) dari 15 adalah : 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, 165, 180, 195, …
Kelipatan (multiple) dari 20 adalah : 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, …
Kelipatan bersama (common multiple) dari 15 dan 20 adalah : 60, 120, 180, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 15 dan 20 adalah : 60.
lcm(15,20)=60
lcm(20,15)=60

Contoh 3 :
Kelipatan (multiple) dari 6 adalah : 6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, …
Kelipatan (multiple) dari 24 adalah : 24, 48, 72, 96, 120, 144, 168, 192, …
Kelipatan bersama (common multiple) dari 6 dan 24 adalah : 24, 48, 72, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 6 dan 24 adalah : 24.
lcm(6,24)=24
lcm(24,6)=24

Contoh 4 :
Kelipatan (multiple) dari 10 adalah : 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 160, 170, 180, 190, 200, 210, …
Kelipatan (multiple) dari 7 adalah : 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84, 91, 98, 105, 112, 119, 126, 133, 140, 147, …
Kelipatan bersama (common multiple) dari 10 dan 7 adalah : 70, 140, 210, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 10 dan 7 adalah : 70.
lcm(10,7)=70
lcm(7,10)=70

Contoh 5 :
Kelipatan (multiple) dari 15 adalah : 15, 30, 45, 60, 75, 90, 105, 120, 135, 150, …
Kelipatan (multiple) dari 10 adalah : 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, …
Kelipatan bersama (common multiple) dari 15 dan 10 adalah : 30, 60, 90, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 15 dan 10 adalah : 30.
lcm(15,10)=30
lcm(10,15)=30

Contoh 6 :
Kelipatan (multiple) dari 4 adalah : 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48, 52, 56, 60, 64, 68, 72, 76, 80, 84, 88, 92, …
Kelipatan (multiple) dari 9 adalah : 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99, 108, 117, 126, …
Kelipatan bersama (common multiple) dari 4 dan 9 adalah : 36, 72, 108, …
Kelipatan bersama yang paling kecil (Least Common Multiple) dari 4 dan 9 adalah : 36.
lcm(4,9)=36
lcm(9,4)=36

Sama seperti GCD, LCM juga bersifat komutatif (dapat dipertukarkan tanpa mengurangi kebenarannya). Yaitu lcm(a,b)=lcm(b,a).

Secara matematis, untuk menghitung LCM dari dua buah bilangan bulat a dan b dapat dilakukan dengan mengikuti rumus lcm(a,b)=\frac{|a.b|}{gcd(a,b)}
Hal ini sangat mudah dilakukan karena sebelumnya kita telah mengetahui teknik pencarian gcd(a,b) ala Euclid.

Secara komputatif, untuk menghitung LCM dilakukan dengan invarian lcm(a,b)=\frac{abs(a.b)}{gcd(a,b)}

Contoh 1 (lagi) :
lcm(12,18)=\frac{|12.18|}{gcd(12,18)}=\frac{216}{6}=36

Contoh 2 (lagi) :
lcm(15,20)=\frac{|15.20|}{gcd(15,20)}=\frac{300}{5}=60

Contoh 3 (lagi) :
lcm(6,24)=\frac{|6.24|}{gcd(6,24)}=\frac{144}{6}=24

Contoh 4 (lagi) :
lcm(10,7)=\frac{|10.7|}{gcd(10,7)}=\frac{70}{1}=70

Contoh 5 (lagi) :
lcm(15,10)=\frac{|15.10|}{gcd(15,10)}=\frac{150}{5}=30

Contoh 6 (lagi) :
lcm(4,9)=\frac{|4.9|}{gcd(4,9)}=\frac{36}{1}=36

Sebenarnya penulis tidak terlalu tertarik untuk membahas asal muasal datangnya rumus LCM ini. Tetapi, untuk mengantisipasi keingintahuan pembaca. Berikut akan dipaparkan asal muasal rumus LCM.

Misalkan gcd(a,b)=d dan lcm(a,b)=e.
Maka a dan b bisa ditulis ulang menjadi :

a=x.d

b=y.d

gcd(x,y)=1

Intermezzo : Mengapa gcd(x,y)=1?
Untuk menjawabnya, penulis akan membuktikan dengan metode kontradiktif. Asumsikan gcd(x,y)=n, dimana n>1. Sehingga :

x=t.n

y=u.n

akibatnya,

a=x.d=t.n.d

b=y.d=u.n.d

dan dengan demikian, gcd(a,b)=n.d

Kalimat di atas secara langsung mengatakan bahwa GCD dari a dan b bukanlah d, melainkan n.d. Dimana n.d>d karena n>1.
Suatu kontradiktif yang mengakibatkan asumsi kita salah.

Dengan demikian gcd(x,y) haruslah 1. Dalam diagram venn dinyatakan sebagai himpunan yang saling lepas.

Sekarang kita lanjutkan ke pembahasan asal muasal rumus LCM…

Nilai e terkecil yang habis membagi x.d dan y.d adalah x.y.d. Mengapa x.y.d? Sukar untuk dijelaskan dengan kata-kata. Biarkan diagram venn di bawah ini yang berbicara 😀

x adalah yang berwarna cyan (telor asin)

d adalah yang berwarna pink (merah jambu)

y adalah yang berwarna purple (ungu)

lcm

Nilai e setidak-tidaknya harus dapat membagi x, y, dan d. Sehingga e haruslah merupakan perkalian ketiganya, yaitu x.y.d

\begin{array}{lll}lcm(a,b)&=&x.y.d\\&=&\frac{x.y.d^2}{d}\\&=&\frac{x.d.y.d}{gcd(a,b)}\\&=&\frac{a.b}{gcd(a,b)}\end{array}

Mengingat lcm(a,b) adalah bilangan bulat positif, maka sisi kanan haruslah positif juga.

Karena penyebut dari sisi kanan, yaitu gcd(a,b), pasti bilangan positif, maka ke-positif-an pembilangnya harus dipastikan dengan fungsi abs(x).

\therefore lcm(a,b)=\frac{abs(a.b)}{gcd(a,b)}

Obat Ngantuk

  1. BintangBintang Rancanglah algoritma untuk mencari GCD dari himpunan bilangan bulat S={a,b,c,d,...}, dimana |S|\geq 2.
    Notasi |S| menyatakan kardinalitas (jumlah elemen) dari himpunan.
  2. BintangBintang Rancanglah algoritma untuk mencari LCM dari himpunan bilangan bulat S={a,b,c,d,...}, dimana |S|\geq 2.
    Notasi |S| menyatakan kardinalitas (jumlah elemen) dari himpunan.

You Don't Trust Management

September 20, 2010

Algoritma Pembagian 2 : Pembahasan FakPos

Filed under: Algoritma, Matematika, Puzzle, Teori Bilangan — Hendra Jaya @ 6:53 am

Obat ngantuk 1

Jika dituliskan ke dalam bentuk perkalian faktor (a . b), 24 dapat dituliskan sebagai :

\begin{array}{rcrcl}\text{index}&|&a&.&b\\---&|&-&-&-\\1&|&1&.&24\\2&|&2&.&12\\3&|&3&.&8\\4&|&4&.&6\end{array}

Perhatikan bahwa dalam bentuk perkalian di atas (a . b),  terdapat beberapa pola :

  1. a\leq b
  2. a_1<a_2<a_3<a_4 ...
  3. b_1>b_2>b_3>b_4 ...

Dan jika dihitung, maka pada data di atas terdapat 4 buah baris dan 2 buah kolom. Sehingga siapapun dapat menghitung dengan cepat banyaknya elemen dalam “tabel”. Tinggal kalikan jumlah baris dan jumlah kolom maka akan diperoleh banyaknya elemen, yaitu 8.

Dengan cara yang sama, 84 juga dapat dituliskan ke dalam bentuk perkalian faktor (a . b) :

\begin{array}{rcrcl}\text{index}&|&a&.&b\\---&|&-&-&-\\1&|&1&.&84\\2&|&2&.&42\\3&|&3&.&28\\4&|&4&.&21\\5&|&6&.&14\\6&|&7&.&12\end{array}

Sehingga banyaknya elemen dalam “tabel” juga dapat diperoleh dengan mengalikan jumlah baris dan jumlah kolom. Untuk 84, terdapat 6 baris dan “so pasti” 2 kolom. Sehingga banyaknya elemen yang ada di dalam “tabel” adalah 12.

Karena “2 kolom” adalah suatu keterjadian (hal yang mutlak), maka – jika direpresentasikan ke dalam bentuk tabel perkalian faktor semua bilangan pasti memiliki jumlah elemen dalam bentuk 2 . baris, yaitu suatu bilangan genap. Sayangnya, jumlah elemen di dalam tabel tidak merepresentasikan jumlah faktor yang sebenarnya. Karena, tabel “perkalian faktor” ini tidak menjamin keunikan/uniqueness dari elemen-elemen yang ada.

“Mengapa setiap faktor harus unik?”
Untuk memahaminya, silahkan bayangkan jika anda diperbolehkan untuk menuliskan faktor secara tidak unik. Untuk angka 24, anda dapat menuliskan faktornya sebagai 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3, …. 24. Totalnya ada tidak terhingga banyaknya faktor.

Setelah memahami sifat “unik” dari setiap faktor dengan faktor lainnya, sebuah pertanyaan kritis akan muncul.

“Apakah mungkin elemen-elemen pada tabel perkalian faktor tidak unik?”
Mungkin saja, yaitu ketika a=b. Sebagai contoh, angka 25, jika direpresentasikan ke dalam tabel perkalian faktor adalah sebagai berikut :

\begin{array}{rcrcl}\text{index}&|&a&.&b\\---&|&-&-&-\\1&|&1&.&25\\2&|&5&.&5\end{array}

Jumlah elemen pada tabel perkalian faktor adalah 4 (genap dan akan selalu genap) sementara jumlah faktor yang sebenarnya adalah 3, yaitu 1, 5, dan 25.

Pertanyaan berikutnya yang mungkin muncul adalah “Berapa kali kasus a = b muncul?”
Konstrain a_1<a_2<a_3<a_4<... secara implisit mengatakan bahwa b_1>b_2>b_3>b_4...  Sekarang, misalkan kasus a=b pertama kali terjadi di baris ke-lima, yaitu pada a_5=b_5 .

Apakah mungkin di baris-baris berikutnya kasus a=b terulang kembali?
Setelah baris ke-lima kita tentu menemui baris ke-enam. Di baris ke-enam akan muncul a_6 yang lebih besar dari a_5, yakni a_6>a_5. Dan akan muncul pula b_6 yang lebih kecil dari b_5, yakni b_5>b_6.

Karena a_5=b_5=m , maka a_6>m>b_6. Suatu hal yang tidak boleh kita lakukan karena di setiap baris kita sudah menyepakati bahwa a\leq b. Dengan demikian, jika kasus a=b terjadi di baris ke-lima dapat dipastikan tidak akan ada baris lagi di bawah baris ke-lima. Atau secara umum dapat kita katakan kasus a=b hanya bisa terjadi maksimal satu kali, dan jika hal itu terjadi di baris ke-n maka pasti n adalah baris terbawah.

Dengan demikian, dapat disimpulkan bahwa kasus ketidak-unikan elemen yang menyebabkan keganjilan jumlah faktor hanya akan muncul di saat baris terbawah dari tabel perkalian faktor-nya dalam bentuk a=b.

Sekarang, apa makna dari a=b? Makna dari a=b adalah bilangan yang dimaksud (c) dapat dituliskan ke dalam bentuk c=a.b=a.a=b.b=a^2=b^2 . Yaitu sebuah bilangan kuadrat. Dengan demikian, kasus keganjilan jumlah faktor hanya akan muncul pada saat c adalah sebuah bilangan kuadrat.

Tour Accounting

Obat Ngantuk 2

Faktor-faktor untuk 1 dapat dituliskan sebagai :

1 = 1

Faktor-faktor untuk 2, yakni 2^1, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\end{array}

Faktor-faktor untuk 4, yakni {2}^{2}, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\end{array}

Faktor-faktor untuk 8, yakni {2}^{3}, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\\8&=&1.2^3\end{array}

Faktor-faktor untuk 24, yakni 2^3.3^1, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\\8&=&1.2^3\\3&=&1.3^1\\6&=&1.2^1.3^1\\12&=&1.2^2.3^1\\24&=&1.2^3.3^1\end{array}

Faktor-faktor untuk 72, yakni {2}^{3}.{3}^{2}, dapat dituliskan sebagai :

\begin{array}{rcl}1&=&1\\2&=&1.2^1\\4&=&1.2^2\\8&=&1.2^3\\3&=&1.3^1\\6&=&1.2^1.3^1\\12&=&1.2^2.3^1\\24&=&1.2^3.3^1\\9&=&1.3^2\\18&=&1.2^1.3^2\\36&=&1.2^2.3^2\\72&=&1.2^3.3^2\end{array}

Catatan : Penulisan faktor di atas dilakukan terurut berdasarkan “kedatangan” faktor prima dan pangkatnya.

Apakah ada pola-nya?
Ada, yaitu :

  • Tentukan 1 sebagai awalan (origin of species)
  • Ketika 2^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 2^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2^1
  • Ketika 2^3 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2^1 ataupun 2^2
  • Ketika 3^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 3^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3^1
  • dst..

Tanpa mengurangi kebenarannya, kita modifikasi sedikit menjadi :

  • Tentukan 1 sebagai awalan (origin of species)
  • Ketika 2^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 2^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 2^3 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 3^1 datang, kalikan dengan semua faktor yang ada.
  • Ketika 3^2 datang, kalikan dengan semua, kecuali dengan bilangan yang mengandung 3
  • dst..

Sekarang, kita tambahkan sedikit logika.

Ketika 2^1 datang (step 2), belum ada bilangan yang mengandung 2. Begitu juga ketika 3^1 datang (step 4), belum ada bilangan yang mengandung 3. Sehingga, tanpa mengurangi kebenarannya, pola yang terbentuk dapat kita tulis ulang lagi menjadi :

  • Tentukan 1 sebagai awalan (origin of species)
  • Ketika 2^1 datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 2
  • Ketika 2^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 2^3 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 2
  • Ketika 3^1 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3
  • Ketika 3^2 datang, kalikan dengan semua, kecuali dengan faktor yang mengandung 3
  • dst..

Nah akhirnya terbentuk satu pola yang sangat mudah dibaca. Ketika 2^1 (ataupun keluarganya) datang, semuanya menolak untuk dikalikan dengan bilangan-bilangan yang mengandung 2. Begitu juga ketika 3^1 (ataupun keluarganya) datang, semuanya menolak untuk dikalikan dengan bilangan-bilangan yang mengandung 3.

Sehingga, secara umum, ketika p^1 (ataupun keluarganya) datang, semuanya menolak untuk dikalikan dengan bilangan-bilangan yang mengandung p.

Sekarang kita tulis lagi pola kita :

  • Tentukan 1 sebagai awalan.
  • Ketika 2 (atau keluarganya) datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 2.
  • Ketika 3 (atau keluarganya) datang, kalikan dengan semua faktor yang ada, kecuali dengan faktor yang mengandung 3.
  • dst..

Misalkan “anggota keluarga” 2 ada k buah, maka :

  • Ketika 1 ditentukan sebagai awalan, jumlah faktor = 1
  • Ketika 2^1 datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
  • Ketika 2^2 datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
  • Ketika 2^3 datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1
  • Ketika 2^k datang, dia hanya mau dikalikan dengan satu buah faktor, yaitu 1

Mengapa semua “anggota keluarga” 2 hanya mau dikalikan dengan satu buah faktor, yaitu 1? Karena mereka takut terjadi “incest”, yaitu perkawinan dengan bilangan “sedarah”, yaitu bilangan yang mengandung angka 2. Hanya ada 1 faktor yang pasti tidak “sedarah” dengan mereka, yaitu 1. Karena perkawinan ini terjadi sebanyak k kali, maka total faktor sekarang ada k+1.

Misalkan “anggota keluarga” 3 ada l buah. Serupa dengan 2, semua bilangan “berdarah” 3 mengharamkan “incest” dan dengan demikian :

  • Ketika 3^1 datang, dia hanya mau dikawinkan dengan k+1 buah bilangan,
  • Ketika 3^2 datang, dia hanya mau dikawinkan dengan k+1 buah bilangan,
  • Ketika 3^3 datang, dia hanya mau dikawinkan dengan k+1 buah bilangan,
  • Ketika 3^l datang, dia hanya mau dikawinkan dengan k+1 buah bilangan

Karena terjadi l kali perkawinan, maka total bilangan baru adalah l.(k+1). Dan jika ditambahkan dengan yang sebelumnya, yaitu k+1. Maka total bilangan (faktor) sekarang adalah l.(k+1)+(k+1)=(l+1).(k+1)

Jika dituliskan ulang polanya menjadi :

  • 1 (awalan)
  • k.1+1=(k+1)
  • l.(k+1)+(k+1)=(l+1).(k+1)
  • m.(l+1).(k+1)+(l+1).(k+1)=(m+1).(l+1).(k+1)
  • dst..

Kesimpulan :

  1. Banyaknya faktor dapat dihitung dengan tepat tanpa harus mengetahui faktor-faktornya.
  2. Banyaknya faktor tidak tergantung kepada faktor prima-nya. Alih-alih, tergantung kepada “pangkat” dari faktor prima-nya.

Technical Jibba-Jabba :

Pseudo-Code :

function FakPos([exp], lower, upper)
  result = 1
  for each i in lower to upper exclusive
    result = result * (1 + exp[i])
  return result

Implementasi Java : Ideone
Implementasi C++ : Sabar subur

Validitas algoritma ini cocok dengan fungsi d(n) seperti dijelaskan pada divisor function.

Secara matematis, FakPos(n) atau d(n) dirumuskan sebagai : d(n)=\prod_{i=1}^{r}(e_i + 1) dimana e_i adalah pangkat/eksponen dari faktor prima ke-i dari n.

Number Order

September 15, 2010

Prinsip Inklusi-Eksklusi

Filed under: Algoritma, Himpunan, Matematika — Hendra Jaya @ 6:41 am

Blog di WordPress.com.