Metode Baru Dalam Perkalian

“Setiap orang pada dasarnya berfikir bahwa metode yang dipelajari di sekolah adalah yang terbaik, padahal faktanya itu merupakan salah satu […]

“Setiap orang pada dasarnya berfikir bahwa metode yang dipelajari di sekolah adalah yang terbaik, padahal faktanya itu merupakan salah satu area dalam penelitian”, 

– Joris Van der Hoeven, matematikawan asal Perancis.

Bagaimana cara kita melakukan perkalian?

Bagaimana cara kita melakukan perkalian? Tentu saja mudah bukan? seperti yang sudah diajarkan di sekolah dasar cara mengalikan 2 buah bilangan adalah dengan mengalikan tiap digit bilangan yang satu dengan setiap digit dari bilangan yang lainnya, namun pertanyaannya adalah apakah benar hanya itu cara melakukannya? Apakah tidak ada metode lain yang lebih cepat daripada itu?. Pada Maret 2018, David Harvey dan Joris van der Hoeven, berhasil menemukan metode baru yang dapat mengalikan 2 buah bilangan bulat lebih cepat daripada metode tradisional dan metode ini merupakan metode yang terbaik dalam mengalikan 2 buah bilangan.

Baca juga: Faktor-Faktor yang Mempengaruhi Pembelajaran Matematika: Sebuah Tinjauan Teori Beban Pikir (Cognitive Load Theory)

Berapa banyak Operasi perkalian yang dibutuhkan untuk mengalikan 25*2? 2 operasi perkalian yaitu 20*2 + 5*2, bagaimana dengan 123*325? 9 operasi perkalian, 6423*2442? 16 operasi perkalian, dan begitu seterusnya hingga jika seandainya kita memiliki 2 buah bilangan dengan panjang digit n, kita akan mendapatkan n^2 buah operasi perkalian. Inilah banyaknya operasi perkalian yang dibutuhkan untuk menyelesaikan perkalian antara dua buah bilangan bulat, dari sini dapat kita lihat bahwa semakin besar nilai n maka akan semakin besar jumlah operasi perkalian yang dibutuhkan akan bertambah dengan drastis.

Pertumbuhan jumlah operasi perkalian yang dilakukan dengan metode tradisional mendorong para matematikawan untuk menemukan suatu metode atau algoritma baru yang dapat menyelesaikan perkalian 2 buah bilangan bulat dengan menggunakan operasi perkalian yang lebih sedikit daripada n^2.

Anatoly Karatsuba, matematikawan asal rusia di usia ke 23 tahunnya menemukan suatu metode yang dapat mengalikan 2 buah bilangan dengan n^1.58 operasi, ia melakukannya dengan cara membagi dua bilangan lalu mengalikan dan menjumlahkan nya dengan aturan tertentu, sebagai contoh adalah 25 * 63

Beberapa dekade setelah penemuan Anatoly, berbagai hasil riset dalam perkalian dua buah bilangan bulat mulai bermunculan, salah satunya adalah hasil riset yang dipublikasikan oleh Arnold Schönhage dan Volker Strassen, mereka menemukan metode ini dengan cara mengimplementasikan fast fourier transform (FFT), metode ini dapat menyelesaikan perkalian dua buah bilangan bulat n digit dengan n*log(n)*log(log(n)) operasi perkalian.

Algoritma Pemercepat Metode Perkalian

Metode ini memberikan jumlah operasi perkalian yang jauh lebih sedikit daripada metode tradisional. Ambil saja contoh mengalikan dua buah bilangan dengan panjang digit 10^10 jika menggunakan metode tradisional akan dibutuhkan setidaknya 10^20 operasi perkalian, sedangkan dengan menggunakan algoritma yang dibuat oleh Arnold Schönhage dan Volker Strassen kita dapat melakukannya hanya dengan 10^11 operasi perkalian. Ini lebih  cepat 10^9 kali dari metode tradisional.

Penemuan yang dilakukan oleh Arnold Schönhage dan Volker Strassen tak membuat mereka mempercayai bahwa metode mereka adalah metode yang paling cepat, mereka menduga bahwa ada suatu metode yang dapat menyelesaikan perkalian dua buah bilangan bulat hanya dengan n*log(n) buah operasi perkalian. Dugaan ini dibuktikan oleh David Harvey dan Joris van der Hoeven. Metode yang mereka dapatkan terinspirasi dari pekerjaan orang-orang sebelum mereka. Mereka menggunakan beberapa kali transformasi fourier dan juga mengubah beberapa perkalian menjadi penjumlahan dan pengurangan.

Mungkin anda akan bertanya-tanya lalu kenapa? Apa manfaatnya jika kita dapat menemukan metode yang lebih cepat dari sebelumnya?. Salah satu manfaat penemuan dari metode ini adalah pengefisienan waktu yang digunakan untuk mendapatkan public key dalam algoritma RSA, Kriptografi. seperti yang kita ketahui algoritma RSA terdiri dari 2 kunci yaitu private key dan public key. Public key  dibuat berdasarkan perkalian 2 bilangan prima yang setidaknya paling terdiri dari 512 digit. Bayangkan saja jika 512 digit tersebut digunakan diselesaikan dengan menggunakan metode tradisional maka akan didapatkan 262144, sedangkan dengan metode yang ditemukan oleh David Harvey dan Joris van der Hoeven dapat menyelesaikan hanya dengan 1388 operasi perkalian, itu lebih cepat 188 kali dari metode tradisional.

Refrensi Utama:

  1. https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-to-multiply-20190411/. Diakses pada tanggal 4 Oktober 2019
  2. https://www.independent.co.uk/news/science/maths-multiplication-multiply-algorithm-large-numbers-new-method-a8875236.html. Diakses pada tanggal 4 Oktober 2019
  3. https://www.di-mgt.com.au/rsa_alg.html. Diakses pada tanggal 5 Oktober 2019
  4. http://doctrina.org/How-RSA-Works-With-Examples.html. Diakses pada tanggal 5 Oktober 2019
  5. https://www.math.tamu.edu/~rojas/furerfastmult.pdf. Diakses pada tanggal 12 Oktober 2019

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top