Catatan si Jay

November 12, 2010

3 Pangkat 2 Pangkat n

Filed under: Barisan Bilangan, Matematika — Hendra Jaya @ 12:58 pm

Problem

Hitunglah nilai dari

\frac{1}{3+1}+\frac{2}{3^2+1}+\frac{4}{3^4+1}+\ldots+\frac{2^{2009}}{3^{2^{2009}}+1}+\frac{2^{2010}}{3^{2^{2010}}+1}

Sumber

Post dari silvergrashopper di www.olimpiade.org. Soal aslinya telah sedikit dimodifikasi

Pra-Pembahasan

Sekedar menyegarkan ingatan, perhatikan beberapa sifat berikut :

  • {(x^a)}^b=x^{ab} untuk sembarang a,b,x\in\mathbb{R}
  • x^a.x^b=x^{a+b} untuk sembarang a,b,x\in\mathbb{R}
  • (x-y).(x+y)=x^2-y^2 untuk sembarang x,y\in\mathbb{R}

Misalkan kita ambil

x=3

a=2^n

b=2^1=2

Maka kita peroleh {(3^{2^n})}^2=3^{2^n.2}

Sekarang, karena 2^n.2=2^n.2^1=2^{n+1}

Maka nilai dari {(3^{2^n})}^2 dapat dituliskan sebagai :

{(3^{2^n})}^2=3^{2^n.2}=3^{2^{n+1}}

Pembahasan

Salah satu trik yang sangat ampuh dalam problem jenis ini adalah mengubah f(n) menjadi bentuk g(n)-g(n+1).

Pada problem ini, secara eksplisit dalam soal, diberitahu bahwa f(n)=\frac{2^n}{3^{2^n}+1}

Agar, tidak terlalu “ribet”, kita mulai manipulasi f(n) dari \frac{1}{3^{2^n}+1}

Melalui aljabar kita peroleh :

\begin{array}{rcll}\frac{1}{3^{2^n}-1}-\frac{1}{3^{2^n}+1}&=&\frac{(3^{2^n}+1)-(3^{2^n}-1)}{{(3^{2^n})}^2-1^2}\\\\&=&\frac{3^{2^n}+1-3^{2^n}+1}{3^{2^{n+1}}-1}\\\\&=&\frac{2}{3^{2^{n+1}}-1}\end{array}

Dengan demikian :

\begin{array}{ccccll}\frac{1}{3^{2^n}-1}&-&\frac{1}{3^{2^n}+1}&=&\frac{2}{3^{2^{n+1}}-1}\\\\\frac{1}{3^{2^n}-1}&-&\frac{2}{3^{2^{n+1}}-1}&=&\frac{1}{3^{2^n}+1}\\\\\frac{2^n}{3^{2^n}-1}&-&\frac{2^n.2}{3^{2^{n+1}}-1}&=&\frac{2^n}{3^{2^n}+1}&\mbox{Kalikan kedua sisi dengan }2^n\\\\\frac{2^n}{3^{2^n}-1}&-&\frac{2^{n+1}}{3^{2^{n+1}}-1}&=&\frac{2^n}{3^{2^n}+1}\end{array}

Bentuk di atas sungguh merupakan bentuk yang sangat sempurna untuk di-eksploitasi :wink:

Yaitu f(n)=\frac{2^n}{3^{2^n}+1} dapat ditulis ulang sebagai g(n)-g(n+1) dimana g(n)=\frac{2^n}{3^{2^n}-1}

Sekarang waktunya menjawab soal :

\begin{array}{lcl}N&=&\frac{1}{3+1}+\frac{2}{3^2+1}+\frac{4}{3^4+1}+\ldots+\frac{2^{2009}}{3^{2^{2009}}+1}+\frac{2^{2010}}{3^{2^{2010}}+1}\\\\&=&(\frac{2^0}{3^{2^0}-1}-\frac{2^1}{3^{2^1}-1})+(\frac{2^1}{3^{2^1}-1}-\frac{2^2}{3^{2^2}-1})+(\frac{2^2}{3^{2^2}-1}-\frac{2^3}{3^{2^3}-1})+\ldots+(\frac{2^{2009}}{3^{2^{2009}}-1}-\frac{2^{2010}}{3^{2^{2010}}-1})+(\frac{2^{2010}}{3^{2^{2010}}-1}-\frac{2^{2011}}{3^{2^{2011}}-1})\\\\&=&\frac{2^0}{3^{2^0}-1}+(\frac{2^1}{3^{2^1}-1}-\frac{2^1}{3^{2^1}-1})+(\frac{2^2}{3^{2^2}-1}-\frac{2^2}{3^{2^2}-1})+(\frac{2^3}{3^{2^3}-1}-\frac{2^3}{3^{2^3}-1})+\ldots+(\frac{2^{2010}}{3^{2^{2010}}-1}-\frac{2^{2010}}{3^{2^{2010}}-1})-\frac{2^{2011}}{3^{2^{2011}}-1}\\\\&=&\frac{2^0}{3^{2^0}-1}-\frac{2^{2011}}{3^{2^{2011}}-1}\\\\&=&\frac{1}{2}-\frac{2^{2011}}{3^{2^{2011}}-1}\end{array}

Introduction to Computer

November 11, 2010

Kejutan!!

Filed under: Barisan Bilangan, Matematika, Puzzle — Hendra Jaya @ 11:52 am

Problem

Hitunglah nilai dari

\begin{array}{l}\sqrt{1+\frac{1}{1^2}+\frac{1}{2^2}}+\sqrt{1+\frac{1}{2^2}+\frac{1}{3^2}}+\sqrt{1+\frac{1}{3^2}+\frac{1}{4^2}}+\ldots+\sqrt{1+\frac{1}{2008^2}+\frac{1}{2009^2}}+\sqrt{1+\frac{1}{2009^2}+\frac{1}{2010^2}}\end{array}

Sumber

Post dari aldo di www.olimpiade.org. Soal aslinya telah sedikit di-modifikasi

Pembahasan

Penulis akui bahwa penulis sedikit bingung apakah hasil perhitungan berupa bilangan rasional atau irasional. Tetapi, secara psikologis penulis yakin bahwa hasil akhirnya pasti berupa bilangan rasional.

Berangkat dari sini, manipulasi aljabar akan sangat dibutuhkan. Masalahnya adalah “Manipulasi yang seperti apa?”

Beberapa cara akan kita coba. Identitas aljabar yang perlu diingat pertama kali adalah (x+y+z)^2=x^2+y^2+z^2+2xy+2xz+2yz

Dengan identitas ini diharapkan terjadi ‘keajaiban’ bahwa manipulasi aljabar akan dapat menyingkirkan tanda akar (\sqrt{}) yang sangat mengganggu.

Dari sini, kita coba aljabar pertama, yaitu :

\begin{array}{lll}(1+\frac{1}{a}+\frac{1}{b})^2&=&1+\frac{1}{a^2}+\frac{1}{b^2}+\frac{2}{a}+\frac{2}{b}+\frac{2}{ab}\\\\&=&1+\frac{1}{a^2}+\frac{1}{b^2}+\frac{2(a+b+1)}{ab}\end{array}

Cukup mirip dengan yang kita inginkan, tetapi belum sesuai. Mari kita coba aljabar kedua :

\begin{array}{lll}(1+\frac{1}{a}-\frac{1}{b})^2&=&1+\frac{1}{a^2}+\frac{1}{b^2}+\frac{2}{a}-\frac{2}{b}-\frac{2}{ab}\\\\&=&1+\frac{1}{a^2}+\frac{1}{b^2}+\frac{2(b-a-1)}{ab}\end{array}

Sepertinya aljabar yang terakhir memang aljabar yang kita inginkan. Agar bentuk yang terakhir sama persis dengan apa yang kita inginkan, kita ambil :

b=a+1 sehingga :

\begin{array}{lll}(1+\frac{1}{a}-\frac{1}{(a+1)})^2&=&1+\frac{1}{a^2}+\frac{1}{(a+1)^2}+\frac{2}{a}-\frac{2}{(a+1)}-\frac{2}{a(a+1)}\\\\&=&1+\frac{1}{a^2}+\frac{1}{(a+1)^2}+\frac{2(a+1-a-1)}{a(a+1)}\\\\&=&1+\frac{1}{a^2}+\frac{1}{(a+1)^2}+\frac{2.0}{a(a+1)}\\\\&=&1+\frac{1}{a^2}+\frac{1}{(a+1)^2}\end{array}

Voila! Persis dengan yang kita inginkan. Suatu bentuk ‘ajaib’ yang bisa meng-eliminasi tanda akar (\sqrt{})dengan mudah :wink:

Dari sini kita peroleh :

\begin{array}{rll}1+\frac{1}{a^2}+\frac{1}{(a+1)^2}&=&(1+\frac{1}{a}-\frac{1}{(a+1)})^2\\\\\sqrt{1+\frac{1}{a^2}+\frac{1}{(a+1)^2}}&=&1+\frac{1}{a}-\frac{1}{(a+1)}\end{array}

Dengan memanfaatkan sepenuh-penuhnya bentuk terakhir, kita dapat menjawab soal dengan mudah :

latex

Exit Interview

November 9, 2010

Menghitung Kemunculan Karakter ’1′ Pada Bilangan n-Digit

Filed under: Matematika, Peluang, Puzzle — Hendra Jaya @ 1:12 pm

Problem

  • Kemunculan karakter ’1′ pada angka 10 adalah 1
  • Kemunculan karakter ’1′ pada angka 51 adalah 1
  • Kemunculan karakter ’1′ pada angka 11 adalah 2
  • Kemunculan karakter ’1′ pada angka 121 adalah 2
  • Kemunculan karakter ’1′ pada angka 1141 adalah 3
  • dst…

Pertanyaannya :

  • Diketahui A=\{1,2,3,\ldots,999,1000\}.
    • Berapa banyak bilangan di dalam himpunan tersebut yang mengandung karakter ’1′?
    • Berapa kali karakter ’1′ muncul di dalam himpunan A?
  • Misalkan N=\{n_1,n_2,n_3,\ldots,n_k\} adalah himpunan seluruh bilangan n-digit.
    • Berapa banyak bilangan di dalam himpunan N yang mengandung karakter 1?
    • Berapa kali karakter ’1′ muncul pada himpunan tersebut?

Sumber : Nanda Daiva Putra

Referensi : 10th Binomial Transform dan Number of “9ish numbers” with n digits

Dear Diary

Pra-Pembahasan 1 (Leading Zero)

Normalnya, awalan 0 (leading zero) tidak diperbolehkan dalam menulis angka. Sebagai contoh :

  • Penulisan 06 dianggap tidak valid, yang valid adalah 6
  • Penulisan 029 dianggap tidak valid, yang valid adalah 29

Sehingga :

Banyaknya bilangan 1 digit yang dapat dibentuk adalah 9
Banyaknya bilangan 2 digit yang dapat dibentuk adalah 9 . 10 = 90
Banyaknya bilangan 3 digit yang dapat dibentuk adalah 9 . 10 . 10 = 900
dst..

Namun, seandainya leading zero diperbolehkan, yaitu setiap karakter pada himpunan C=\{0,1,2,3,4,5,6,7,8,9\} boleh dipakai, maka :

Banyaknya bilangan 1 digit yang dapat dibentuk adalah 10
Banyaknya bilangan 2 digit yang dapat dibentuk adalah 10 . 10 = 100
Banyaknya bilangan 3 digit yang dapat dibentuk adalah 10 . 10 . 10 = 1000
dst…

Dari sini kita dapat menyimpulkan bahwa :

  1. Banyaknya bilangan n-digit yang dapat dibentuk jika awalan 0 tidak diperbolehkan (non-leading zero) adalah 9.10^{n-1}
  2. Banyaknya bilangan n-digit yang dapat dibentuk jika awalan 0 (leading zero) diperbolehkan adalah 10^{n}

Pra-Pembahasan 2 (Kemunculan Karakter ’1′ pada Leading Zero)

Jika awalan 0 (non-leading zero) tidak diperbolehkan, maka :

Bilangan-bilangan 1 digit yang mengandung karakter ’1′ adalah \{1\}
Banyaknya bilangan 1 digit yang mengandung karakter ’1′ adalah 1 buah.
Total kemunculan karakter ’1′ pada bilangan 1 digit adalah 1 kali.

Bilangan-bilangan 2 digit yang mengandung karakter ’1′ adalah \{10,11,12,13,14,15,16,17,18,19,21,31,41,51,61,71,81,91\}
Banyaknya bilangan 2 digit yang mengandung karakter ’1′ adalah 18 buah.
Total kemunculan karakter ’1′ pada bilangan 2 digit adalah 19 kali.

Jika awalan 0 (leading zero) diperbolehkan, maka :

Bilangan-bilangan 1 digit yang mengandung karakter ’1′ adalah \{1\}
Banyaknya bilangan 1 digit yang mengandung karakter ’1′ adalah 1 buah.
Total kemunculan karakter ’1′ pada bilangan 1 digit adalah 1 kali.

Bilangan-bilangan 2 digit yang mengandung karakter ’1′ adalah \{01,10,11,12,13,14,15,16,17,18,19,21,31,41,51,61,71,81,91\}
Banyaknya bilangan 2 digit yang mengandung karakter ’1′ adalah 19 buah.
Total kemunculan karakter ’1′ pada bilangan 2 digit adalah 20 kali.

Mengapa terdapat perbedaan antara kasus leading zero dan kasus non-leading zero?

Jawabannya terletak pada leading zero itu sendiri.

Pada kasus non-leading zero, bilangan 1 tidak akan muncul pada bilangan 2-digit karena bilangan 1 hanya terdiri dari 1 buah digit. Selamanya begitu. Tidak bisa “naik pangkat” menjadi bilangan 2-digit.

Sebaliknya, pada kasus leading zero, bilangan 1 akan muncul pada bilangan 2-digit. Yaitu dengan memberikan awalan 0 (leading zero) pada bilangan 1, maka akan dihasilkan bilangan baru 01 yang panjangnya 2 digit. Kita katakan “1 naik pangkat menjadi bilangan 2-digit”.

Dari logika ini, semua bilangan 1-digit akan naik pangkat menjadi bilangan 2-digit, lalu naik pangkat menjadi bilangan 3-digit, dan seterusnya sampai menjadi bilangan n-digit.
Dari logika yang sama, semua bilangan 2-digit akan naik pangkat menjadi bilangan 3-digit, lalu naik pangkat menjadi bilangan 4-digit, dan seterusnya sampai menjadi bilangan n-digit.
dst..
Begitu pula dengan bilangan (n-1)-digit. Bilangan ini akan naik pangkat menjadi bilangan n-digit.

Lantas, apa hubungan antara bilangan non-leading zero dan leading zero?

Misalkan :

  • f(n) adalah fungsi yang menghitung banyaknya kemunculan ’1′ pada seluruh bilangan n-digit non-leading zero.
  • g(n) adalah fungsi yang menghitung banyaknya kemunculan ’1′ pada seluruh bilangan n-digit leading zero.

Secara intuitif kita tahu bahwa g(n) pasti lebih besar dari f(n). Hal ini cukup jelas juga secara matematis, mengingat bilangan-bilangan yang leading zero boleh menggunakan 0, sementara bilangan-bilangan yang non-leading zero tidak.

Cukup jelas juga bahwa selisih antara g(n) dan f(n) berasal dari bilangan-bilangan yang “naik pangkat”.

Lantas, berapa banyak bilangan-bilangan yang “naik pangkat”?

Semua bilangan-bilangan berdigit lebih kecil dari n akan naik pangkat. Mulai dari berdigit 1 sampai berdigit n-1.

Banyaknya bilangan berdigit 1 yang naik pangkat adalah f(1)
Banyaknya bilangan berdigit 2 yang naik pangkat adalah f(2)
Banyaknya bilangan berdigit 3 yang naik pangkat adalah f(3)
dst…
Banyaknya bilangan berdigit n-1 yang naik pangkat adalah f(n-1)

Sehingga, total bilangan yang naik pangkat adalah f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)

Jika dikembalikan ke relasi antara g(n) dan f(n), maka akan kita peroleh :

\begin{array}{rcl}g(n)-f(n)&=&f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)\\g(n)&=&f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)+f(n)\end{array}

Pra-Pembahasan 3 (Sebaran Bilangan yang Mengandung karakter ’1′ Pada Bilangan n-digit Leading Zero)

Misalkan pada seluruh bilangan n-digit leading zero, terdapat :

  • x buah bilangan yang mengandung karakter ’1′
  • y buah bilangan yang tidak mengandung karakter ’1′
  • g(n)=z buah kemunculan karakter ’1′.

Jelas sekali bahwa relasi antara x dan y adalah x+y=10^n

Selanjutnya, kita asumsikan :

  • Ada a_1 buah bilangan yang mengandung 1 buah karakter ’1′
  • Ada a_2 buah bilangan yang mengandung 2 buah karakter ’1′
  • Ada a_3 buah bilangan yang mengandung 3 buah karakter ’1′
  • dst…
  • Ada a_{n-1} buah bilangan yang mengandung n-1 buah karakter ’1′
  • Ada a_n buah bilangan yang mengandung n buah karakter ’1′

Banyaknya bilangan yang mengandung karakter ’1′ adalah a_1+a_2+a_3+\ldots+a_{n-1}+a_n alias x.
Sehingga kita peroleh invarian x=a_1+a_2+a_3+\ldots+a_{n-1}+a_n

Sebaliknya, banyaknya kemunculan karakter ’1′ adalah 1.a_1+2.a_2+3.a_3+\ldots+(n-1).a_{n-1}+n.a_n alias z.
Sehingga kita peroleh invarian lainnya, yakni g(n)=z=1.a_1+2.a_2+3.a_3+\ldots+(n-1).a_{n-1}+n.a_n

Bagaimana dengan y, adakah cara untuk menghitungnya?

Untuk mencari nilai y tidak terlalu sulit. Cukup menggunakan “pohon kemungkinan”.

Karena terdiri dari n-digit dan leading zero, maka setiap digit-nya boleh menggunakan bilangan-bilangan pada himpunan \{0,2,3,4,5,6,7,8,9\} yang banyaknya (kardinalitas) ada 9 buah. Sehingga :

y=9.9.9\ldots 9.9=9^n

Knuth Mistakes

Pembahasan

Misalkan \overline{ABCDE\ldots} adalah sebuah bilangan n digit.

Bilangan ini dapat kita pecah menjadi 2 bagian yaitu \overline{A} dan \overline{BCDE\ldots} dimana :

  • \overline{A} jelas merupakan bilangan 1 digit dan tidak boleh dimulai dengan 0 (non-leading zero).
    Sehingga himpunan bilangan yang mungkin untuk \overline{A} adalah \{1,2,3,4,5,6,7,8,9\}.
  • Sedikit berbeda, \overline{BCDE\ldots} merupakan bilangan (n-1)-digit yang boleh dimulai dari 0.
    Sehingga himpunan bilangan yang mungkin untuk \overline{B},\overline{C},\overline{D},\overline{E},\ldots adalah \{0,1,2,3,4,5,6,7,8,9\}.

Secara intuitif, kita dapat menyadari bahwa munculnya karakter ’1′ hanya mungkin terjadi dalam 3 buah kasus, yaitu :

  1. Karakter ’1′ hanya disumbangkan oleh \overline{A}
  2. Karakter ’1′ hanya disumbangkan oleh \overline{BCDE\ldots}
  3. Karakter ’1′ disumbangkan oleh kedua pihak, yaitu \overline{A} dan \overline{BCDE\ldots}

Kasus 1

Karena karakter ’1′ hanya disumbangkan oleh \overline{A}, berarti :

  • Hanya ada 1 buah nilai yang mungkin untuk \overline{A}
  • Ada y buah nilai yang mungkin untuk \overline{BCDE\ldots}

Sehingga :

  • Banyaknya bilangan yang mengandung ’1′ pada kasus 1 adalah 1.y=y
  • Banyaknya kemunculan karakter ’1′ ada sebanyak y kali

Catatan : Walaupun \overline{BCDE\ldots} tidak memiliki satupun karakter ’1′, namun \overline{BCDE\ldots} berjumlah y buah. Ketika dipasangkan dengan \overline{A} maka akan muncul y buah karakter ’1′ yang baru.

Kasus 2

Dalam kasus ini, karakter ’1′ hanya disumbangkan oleh \overline{BCDE\ldots}, yang berarti :

  • Ada 8 buah nilai yang mungkin untuk \overline{A}, yaitu \{2,3,4,5,6,7,8,9\}
  • Ada x buah nilai yang mungkin untuk \overline{BCDE\ldots}
  • Ada z buah kemunculan karakter ’1′ pada \overline{BCDE\ldots}

Sehingga :

  • Banyaknya bilangan yang mengandung ’1′ pada kasus 2 adalah 8.x=8x
  • Banyaknya kemunculan karakter ’1′ ada sebanyak 8.z=8z kali

Kasus 3

Kasus ini adalah kasus yang paling tricky. Perhatikan bahwa :

  • Ada 1 buah nilai yang mungkin untuk \overline{A}
  • Ada x buah nilai yang mungkin untuk \overline{BCDE\ldots}
  • Ada z buah kemunculan karakter ’1′ pada \overline{BCDE\ldots}

Sebaran dari z adalah 1.a_1+2.a_2+3.a_3+\ldots+(n-1).a_{n-1}+n.a_n
Ketika digabungkan dengan \overline{A}, sebarannya akan naik menjadi 2.a_1+3.a_2+4.a_3+\ldots+n.a_{n-1}+(n+1).a_n.

Catatan : Kenaikan sebaran terjadi karena terjadi penggabungan (concatenation) dengan karakter ’1′ yang berasal dari \overline{A}.  Sebagai contoh, bilangan 31216 semula memiliki 2 buah karakter ’1′. Ketika dibubuhi prefix ’1′ akan menjadi 131216 yang mengandung 3 buah karakter ’1′.

Jika disederhanakan, bentuk di atas akan menjadi :

\begin{array}{rcl}2.a_1+3.a_2+4.a_3+\ldots+n.a_{n-1}+(n+1).a_n&=&(1.a_1+2.a_2+3.a_3+\ldots+(n-1).a_{n-1}+n.a_n)+(a_1+a_2+a_3+\ldots+a_{n-1}+a_n)\\&=&z+x\end{array}

Sehingga :

  • Banyaknya bilangan yang mengandung ’1′ pada kasus 3 adalah 1.x=x
  • Banyaknya kemunculan karakter ’1′ ada sebanyak x+z kali

Rumus Umum Untuk Menghitung Banyaknya Bilangan n-digit yang Mengandung Karakter ’1′

Untuk mencari rumus umum banyaknya bilangan pengandung karakter ’1′ akan kita gabungkan ketiga kasus :

\begin{array}{lll}p(n)&=&(y)+(8x)+(x)\\&=&9x+y\\&=&9(10^{n-1}-y)+y\\&=&9.10^{n-1}-9y+y\\&=&9.10^{n-1}-8y\end{array}

Karena y adalah banyaknya bilangan pada \overline{BCDE\ldots} yang tidak mengandung karakter ’1′, maka nilai dari y adalah 9^{n-1}

Dengan mensubstitusikan y=9^{n-1} kita peroleh :

p(n)=9.10^{n-1}-8.9^{n-1}

Rumus di atas adalah rumus umum untuk mencari banyaknya bilangan n-digit yang mengandung karakter ’1′ di dalamnya.

Rumus Umum Untuk Menghitung Kemunculan Karakter ’1′ Pada Bilangan n-digit

Sama seperti sebelumnya, untuk mencari rumus umum kemunculan, akan kita gabungkan ketiga kasus :

\begin{array}{llll}f(n)&=&\mbox{Kasus 1}+\mbox{Kasus 2}+\mbox{Kasus 3}\\&=&(y)+(8z)+(x+z)\\&=&x+y+9z\\&=&10^{n-1}+9z&\mbox{Karena }x+y=10^{n-1}\\f(n)&=&10^{n-1}+9(f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1))&\mbox{Karena }z=g(n-1)=f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)\end{array}

Kita peroleh rumus umum untuk mencari f(n). Mari kita cicip rumus kita :

\begin{array}{lll}f(1)&=&1\\\\f(2)&=&10^{2-1}+9(f(1))\\&=&10^1+9.1\\&=&19\\\\f(3)&=&10^{3-1}+9(f(1)+f(2))\\&=&10^2+9(1+19)\\&=&280\\\\f(4)&=&10^{4-1}+9(f(1)+f(2)+f(3))\\&=&10^3+9(1+19+280)\\&=&3700\\\\&&\cdots\end{array}

Walaupun rumus ini dapat memberikan hasil perhitungan dengan benar, namun rumus ini kurang ‘pas’ untuk diandalkan karena rumus ini bersifat rekursif dan sangat tergantung pada hasil-hasil perhitungan pada digit-digit sebelumnya.

Sekarang akan kita coba untuk memodifikasi rumus ini menjadi sedikit lebih baik. Perhatikan beberapa aljabar di bawah ini :

\begin{array}{rll}f(1)+f(2)&=&f(1)+10^1+9(f(1))\\&=&10^1+10(f(1))\\&=&10^1(1+f(1))\end{array}

\begin{array}{rll}f(1)+f(2)+f(3)&=&f(1)+f(2)+10^2+9(f(1)+f(2))\\&=&10^2+10(f(1)+f(2))\\&=&10^2+10.10^1(1+f(1))\\&=&10^2+10^2(1+f(1))\\&=&10^2(1+1+f(1))\end{array}

\begin{array}{rll}f(1)+f(2)+f(3)+f(4)&=&f(1)+f(2)+f(3)+10^3+9(f(1)+f(2)+f(3))\\&=&10^3+10(f(1)+f(2)+f(3))\\&=&10^3+10.10^2(1+1+f(1))\\&=&10^3+10^3(1+1+f(1))\\&=&10^3(1+1+1+f(1))\end{array}

dst…

\begin{array}{rll}f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1)&=&10^{n-2}(1+1+1+\ldots+1+1+f(1))\\&=&10^{n-2}(n-2+f(1))\\&=&10^{n-2}(n-2+1)\\&=&10^{n-2}(n-1)\end{array}

Catatan : Aljabar di atas bukan pembuktian matematika yang sah. Walaupun demikian, pola aljabar di atas akan terus berulang-ulang dan hasilnya akan sama seperti yang ada di atas. Pembuktian matematis yang sah diserahkan kepada pembaca.

Sekarang, kita dapat menghitung f(n) dengan mudah, tanpa harus rekursif lagi

\begin{array}{lll}f(n)&=&10^{n-1}+9(f(1)+f(2)+f(3)+\ldots+f(n-2)+f(n-1))\\&=&10^{n-1}+9.10^{n-2}.(n-1)\\&=&10.10^{n-2}+9.10^{n-2}.(n-1)\\&=&10^{n-2}(10+9.(n-1))\\&=&10^{n-2}(10+9n-9)\\f(n)&=&10^{n-2}(9n+1)\end{array}

Rumus yang terakhir ini adalah rumus yang kita inginkan. Rumus ini mampu “loncat” langsung ke digit yang kita inginkan tanpa harus menghitung satu persatu setiap digit mulai dari 1, 2, 3, …, sampai n-1.

Jawaban Atas Pertanyaan

Terkait dengan pertanyaan yang diajukan di awal artikel.

  1. Banyaknya bilangan di dalam himpunan tersebut yang mengandung karakter ’1′ ada sebanyak :
    \begin{array}{lll}p(1)+p(2)+p(3)+1&=&(9.10^0-8.9^0)+(9.10^1-8.9^1)+(9.10^2-8.9^2)+1\\&=&(9.1-8.1)+(9.10-8.9)+(9.100-8.81)+1\\&=&(9-8)+(90-72)+(900-648)+1\\&=&1+18+252+1\\&=&272\end{array}
  2. Banyaknya kemunculan karakter ’1′ ada sebanyak :
    \begin{array}{lll}f(1)+f(2)+f(3)+1&=&(10^{1-2}.(9.1+1))+(10^{2-2}.(9.2+1))+(10^{3-2}.(9.3+1))+1\\&=&(10^{-1}.(9+1))+(10^0.(18+1))+(10^1.(27+1))+1\\&=&(10^{-1}.10)+(1.19)+(10.28)+1\\&=&1+19+280+1\\&=&301\end{array}

Catatan : Perhatikan bahwa dalam soal di atas penulis mengasumsikan bahwa 1 dan 1000 diikutsertakan dalam perhitungan (inclusive). Dengan demikian rentang 1-1000 melibatkan 3 buah digit, yaitu digit 1, digit 2, dan digit 3 plus angka 1000 itu sendiri.

Angka 1 pada perhitungan di atas datang dari angka 1000 yang banyaknya ada 1 dan jelas sekali mengandung karakter ’1′ di dalamnya.

The Code giveth, The Code Taketh away

November 8, 2010

[Mengapa oh Mengapa] Sulap Tanggal Lahir

Filed under: Brain Teaser, Matematika — Hendra Jaya @ 8:02 am

Sulap tanggal lahir adalah sulap matematis yang sangat populer. Sulap ini biasanya meminta “korban” untuk melakukan beberapa operasi matematika sederhana terkait dengan tanggal/bulan/tahun lahirnya. Di akhir sulap, korban akan diminta untuk memberikan angka hasil perhitungannya. Setelah menerima angka tersebut, abrakadabra pun terjadi. Sang pesulap mampu menebak dengan tepat tanggal/bulan/tahun lahir korban.

Artikel ini ditulis untuk menjelaskan, secara matematis tentunya, mengapa “Sulap Tanggal Lahir” dapat dilakukan.

Referensi

Ada banyak sekali metode untuk melakukan sulap tanggal lahir. Berikut ini penulis sajikan dua buah di antaranya.

Sulap 1

  • Kalikan tanggal lahir anda dengan 4, simpan hasilnya.
  • Tambahkan angka tersebut dengan 13, simpan hasilnya.
  • Kalikan angka tersebut dengan 25, simpan hasilnya.
  • Kurangi angka tersebut dengan 200, simpan hasilnya.
  • Tambahkan bulan lahir anda pada angka tersebut, simpan hasilnya.
  • Kalikan angka tersebut dengan 2, simpan hasilnya.
  • Kurangi angka tersebut dengan 40, simpan hasilnya.
  • Kalikan angka tersebut dengan 50, simpan hasilnya.
  • Tambahkan dua digit tahun kelahiran anda pada angka tersebut, simpan hasilnya

Pesulap lalu meminta angka tersebut dan melakukan operasi berikut :

  • Angka yang diperoleh dikurangi 10500
  • Sisanya adalah tanggal lahir korban dalam format “ddmmyy”

Sebagai contoh, penulis akan ambil tanggal lahir dedek tersayang :oops: , yaitu 17 Oktober 1985 (Bentuk lain : 17-10-1985)

  • Kalikan tanggal lahir dengan 4. Angka = 17 x 4 = 68
  • Tambahkan dengan 13. Angka = 68 + 13 = 81
  • Kalikan dengan 25. Angka = 81 x 25 = 2025
  • Kurangi dengan 200. Angka = 2025 – 200 = 1825
  • Tambahkan bulan lahir. Angka = 1825 + 10 = 1835
  • Kalikan dengan 2. Angka = 1835 x 2 = 3670
  • Kurangi dengan 40. Angka = 3670 – 40 = 3630
  • Kalikan dengan 50. Angka = 3630 x 50 = 181500
  • Tambahkan 2 digit tahun lahir. Angka = 181500 + 85 = 181585

Korban lalu memberikan angka 181585 ini kepada pesulap dan pesulap pun (secara diam-diam) melakukan :

  • Kurangi dengan 10500. Angka = 181585 – 10500 = 171085
  • Angka ini lalu dipecah-pecah menjadi 3 bagian, yaitu 17-10-85

Abrakadabra pun terjadi. Pesulap tinggal mengatakan “Saudari Nurul, benarkah anda lahir pada tanggal 17, bulan 10 tahun 85?”

Sulap 2

  • Kalikan tanggal lahir anda dengan 5, lalu simpan hasilnya.
  • Tambahkan angka tersebut dengan 5, simpan hasilnya.
  • Kalikan angka tersebut dengan 20, simpan hasilnya.
  • Kurangi angka tersebut dengan 85, simpan hasilnya. (Dimodifikasi sedikit oleh penulis)
  • Tambahkan bulan lahir anda pada angka tersebut, simpan hasilnya.
  • Kalikan angka tersebut dengan 2, simpan hasilnya.
  • Kurangi angka tersebut dengan 60, simpan hasilnya.
  • Kalikan angka tersebut dengan 50, simpan hasilnya.
  • Tambahkan 2 digit terakhir tahun kelahiran anda pada angka tersebut, simpan hasilnya.

Pesulap lalu meminta angka tersebut dan melakukan operasi berikut :

  • Angka yang diperoleh ditambah dengan 1500
  • Sisanya adalah tanggal lahir korban dalam format “ddmmyy”

Catatan : Penulis – dengan sengaja – memodifikasi sulap 2 agar sedikit lebih singkat. Pada versi asli (lih. referensi), dilakukan satu buah “pengurangan dengan 100″ lalu “penambahan dengan 15″. Kedua operasi aritmatika ini penulis sederhanakan menjadi satu buah “pengurangan dengan 85″.

Masih dengan contoh yang sama, yaitu tanggal lahir dedek tersayang :oops: , 17 Oktober 1985 alias 17-10-1985.

  • Kalikan tanggal lahir anda dengan 5. Angka = 17 x 5 = 85
  • Tambahkan dengan 5. Angka = 85 + 5 = 90
  • Kalikan dengan 20. Angka = 90 x 20 = 1800
  • Kurangi dengan 85. Angka = 1800 – 85 = 1715
  • Tambahkan bulan lahir anda. Angka = 1715 + 10 = 1725
  • Kalikan dengan 2. Angka = 1725 x 2 = 3450
  • Kurangi dengan 60. Angka = 3450 – 60 = 3390
  • Kalikan dengan 50. Angka = 3390 x 50 = 169500
  • Tambahkan 2 digit terakhir tahun lahir anda. Angka = 169500 + 85 = 169585

Tanpa curiga, korban memberitahukan angka 169585 ini kepada pesulap dan pesulap pun langsung melakukan :

  • Tambahkan dengan 1500. Angka = 169585 + 1500 = 171085
  • Memecah angka ini menjadi 3 bagian, yaitu 17-10-85

Abrakadabra pun terjadi. Dengan sedikit acting, pesulap berujar “Sepertinya ada kesalahan disini… Tanggal lahir saudari Nurul adalah 17 Oktober 1985. Benarkah begitu?”

Pra-Pembahasan

Tanggal lahir adalah x
Bulan lahir adalah y
Dua digit terakhir tahun lahir adalah z
Angka yang dihitung oleh korban adalah m
Nilai m yang sudah “dimanipulasi” oleh pesulap adalah n

Aljabar Sulap 1

\begin{array}{rlll}m&=&4x&\mbox{Kalikan tanggal lahir dengan 4}\\m&=&4x+13&\mbox{Tambahkan dengan 13}\\m&=&25.(4x+13)&\mbox{Kalikan dengan 25}\\&=&100x+325\\m&=&100x+125&\mbox{Kurangi dengan 200}\\m&=&100x+y+125&\mbox{Tambahkan bulan lahir}\\m&=&2.(100x+y+125)&\mbox{Kalikan dengan 2}\\&=&200x+2y+250\\m&=&200x+2y+210&\mbox{Kurangi dengan 40}\\m&=&50.(200x+2y+210)&\mbox{Kalikan dengan 50}\\&=&10000x+100y+10500\\m&=&10000x+100y+z+10500&\mbox{Tambahkan 2 digit terakhir tahun lahir}\\n&=&10000x+100y+z&\mbox{Kurangi dengan 10500}\end{array}

Aljabar Sulap 2

\begin{array}{rlll}m&=&5x&\mbox{Kalikan tanggal lahir dengan 5}\\m&=&5x+5&\mbox{Tambahkan 5}\\m&=&20.(5x+5)&\mbox{Kalikan dengan 20}\\&=&100x+100\\m&=&100x+15&\mbox{Kurangi dengan 85}\\m&=&100x+y+15&\mbox{Tambahkan bulan lahir}\\m&=&2.(100x+y+15)&\mbox{Kalikan dengan 2}\\&=&200x+2y+30\\m&=&200x+2y-30&\mbox{Kurangi dengan 60}\\m&=&50.(200x+2y-30)&\mbox{Kalikan dengan 50}\\&=&10000x+100y-1500\\m&=&10000x+100y+z-1500&\mbox{Tambahkan 2 digit terakhir tahun lahir}\\n&=&10000x+100y+z&\mbox{Tambahkan 1500}\end{array}

Pembahasan

Angka yang saat ini dipegang oleh pesulap, yaitu n, me-representasikan tanggal-bulan-tahun lahir si korban dalam format “ddmmyy”.
Berikut penjelasannya :

Misalkan X adalah sebuah bilangan 2 digit, dimana digit pertama adalah X_1 dan digit kedua adalah X_2. Secara matematis \overline{X}=10.X_1+X_2

Misalkan Y adalah sebuah bilangan 2 digit, dimana digit pertama adalah Y_1 dan digit kedua adalah Y_2. Secara matematis \overline{Y}=10.Y_1+Y_2

Digit pertama pada Z kita namai Z_1 dan digit kedua kita namai Z_2. Secara matematis \overline{Z}=10.Z_1+Z_2

Akan kita peroleh :

\begin{array}{lll}n&=&10000x+100y+z\\n&=&10000(10.x_1+x_2)+100(10.y_1+y_2)+(10.z_1+z_2)\\n&=&100000x_1+10000x_2+1000.y_1+100y_2+10.z_1+z_2\end{array}

Jika di-representasikan dalam penjumlahan akan berbentuk seperti :

\begin{array}{ccccccr}X_1&0&0&0&0&0\\&X_2&0&0&0&0\\&&Y_1&0&0&0\\&&&Y_2&0&0\\&&&&Z_1&0\\&&&&&Z_2\\-&-&-&-&-&-&+\\X_1&X_2&Y_1&Y_2&Z_1&Z_2\end{array}

Sekarang, karena :

\overline{X} adalah tanggal lahir
\overline{Y} adalah bulan lahir
\overline{Z} adalah 2 digit terakhir tahun lahir

Maka nilai n akan secara tegas menyatakan tanggal-bulan-tahun lahir si korban dalam format “ddmmyy”. Pesulap hanya perlu membacakannya dengan sedikit berpura-pura terkejut :)

Bagaimana jika tanggal/bulan/tahun lahir adalah bilangan 1 digit?

Tidak ada masalah

Jika tanggal lahir adalah bilangan 1 digit, maka nilai n yang semula berupa bilangan 6 digit, kini akan berbentuk bilangan 5 digit. Sedikit lebih jauh, jumlah digit pada n hanya bergantung kepada tanggal lahir. Seorang pesulap yang handal pasti sudah menyadari hal ini.

Jika bulan lahir adalah bilangan 1 digit, maka bilangan yang dihasilkan tidak berubah digit-nya. Satu-satunya dampak yang perlu disadari hanyalah digit ke-4 dari kanan, yakni Y_1, bernilai 0.

Jika tahun lahir adalah bilangan 1 digit-pun tidak ada masalah. Sama seperti sebelumnya, satu-satunya efek yang timbul hanyalah digit ke-2 dari kanan, yakni Z_1, bernilai 0.

Untuk tahun lahir kita ambil contoh z=\overline{01}.

Dalam ilmu matematika yang “buta”, kita tidak bisa memastikan apakah \overline{01} bermakna 1801 atau 1901, 2001 dan seterusnya. Hal ini wajar mengingat bilangan-bilangan …, 1801, 1901, 2001,… semuanya kongruen dengan \overline{01} dalam modulo 100. Tetapi, selisih 1 abad jelas memberikan efek fisik yang kuat. Seseorang yang lahir di tahun 1901 jelas akan terlihat “berbeda” dengan orang yang lahir di tahun 2001. Untuk membedakannya tentu bukan perkara yang sulit.

Math Magic

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

Tema: Shocking Blue Green. Blog pada WordPress.com.

Ikuti

Get every new post delivered to your Inbox.