Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas teknik perhitungan lanjutan dalam perkalian bilangan bulat dengan metode divide and conquer. Proses ini dapat diterapkan pada bilangan bulat besar dengan membagi bilangan menjadi blok, mengalikan, dan menggabungkannya kembali. Selain itu, teknik ini juga dapat digunakan dalam perkalian matriks untuk mengurangi jumlah operasi yang diperlukan. Dengan menggunakan algoritma divide and conquer, jumlah operasi dapat dikurangi sehingga mempercepat proses perhitungan. Metode ini menghasilkan hasil yang lebih efisien dibandingkan dengan metode perkalian konvensional.

Proses ini juga sama kalau kita mau mengalikan integers,

dalam hal ini integers yang dikalikan itu gede sekali dengan catatan ini gedenya bukan cuman ribuan atau jutaan

tapi bilangan yang besar sekali karena kalau yang kecil kita pakai kalkulator,

ini untuk yang kalkulatornya sudah tidak bisa, sudah tidak terdefinisi.

Jadi mengalikan bilangan bulat itu menggunakan teknik divide and conquer ceritanya,

jadi ini dia akan membagi 2 n-bit bilangan bulat menjadi 2 blok masing-masing terdiri dari n-bit masing-masing bloknya,

kemudian yang blok pertama itu dikalikan, direduksi,

jadi nanti akhirnya kita gabungkan lagi dengan yang n blok satunya,

jadi misalkan di sini kita punya A dan B 2 bilangan bulat dengan ekspansi binar sepanjang 2n,

kalau misalnya kurang dari panjangnya kurang dari 2n kita tambahkan 0 supaya panjangnya sama,

jadi kita punya A itu A2n-1, A2n-2 sampai A0, kemudian Bnya B2n-1, B2n-2 sampai B1, B0,

ini dua-duanya dalam bentuk binar jadi bilangannya itu direpresentasikan dalam binar dulu.

Jadi misalkan si A nya itu bentuknya adalah seperti ini 2 pangkat n kali A1 ditambah A0 kali A0,

kemudian Bnya itu sama dengan 2 pangkat n B1 ditambah B0,

maka nanti dengan A1 yang seperti ini, kemudian B1nya yang bentuknya seperti ini,

A0nya bentuknya dari An-1 sampai A0, ini diparuhkan ya, dibagi dua maaf,

dibagi dua maka nanti untuk mengalikannya kita akan mendapatkan jumlah yang seperti ini jadi ABnya,

jadi itu dikalikan dulu nanti baru digabungkan.

Nah hasilnya banyaknya operasi yang dilakukan,

3 perkalian dari bilangan bulat n bit itu menggunakan 3 Fn bit operasi,

masing-masing adalah penjumlahan, pengurangan dan pergeseran,

kemudian Cn nya itu banyak total operasi bit menggunakan operasi-operasi ini,

jadi kita bisa lihat bahwa beberapa operasi yang kita bagi modelnya,

itu nanti kita bisa menghitung banyaknya operasi atau kita bisa memprediksi banyaknya operasi yang diperlukan

dengan masing-masing bloknya kemudian kita gabungkan lagi hasilnya kalau sudah ada solusinya.

Begitu juga bisa dipakai untuk perkalian matriks juga untuk perkalian-perkalian yang lain yang membutuhkan hitungan yang banyak,

jadi kalau misalnya matriksnya itu ukurannya n kali n kita punya 2 matriks,

maka kalau kita menggunakan definisi perkalian kita butuhkan n pangkat 3 perkalian dan n kuadrat kali n minus 1 penjumlahan,

kalau menggunakan algoritma divide and conquer maka kita mereduksinya menjadi ukuran n per 2 kali n per 2,

lalu dari sini kita akan punya 15 penjumlahan dari matriks n per 2 kali n per 2,

jadi nanti banyaknya operasinya adalah 7 kali fn per 2 ditambah 15 n kuadrat per 2,

kita lihat bahwa jumlahnya akan lebih kecil dari yang kalau kita menggunakan perkalian dari aslinya,

artinya ukuran n kali n itu kita kalikan nanti ada proses kali, ada ditambah,

tapi nanti diperlukan divide and conquernya itu 7 kali dari fn per 2 nya,

masih ada untuk yang operasi penjumlahannya.

Jadi sekian contoh dari divide and conquer, selanjutnya kita akan bahas tentang BKO nya.