Dengan memecah angka besar menjadi angka kecil, para peneliti melampaui batas kecepatan matematika dasar
Empat ribu tahun yang lalu, penduduk
Babilonia menemukan penggandaan. Dan pada bulan Maret tahun ini, matematikawan memperbaikinya.
Pada 18 Maret 2019, dua peneliti
menggambarkan metode yang paling cepat diketahui untuk mengalikan dua angka yang sangat besar. Pekerjaan ini menandai puncak dari pencarian jangka panjang untuk prosedur yang paling efisien untuk melakukan salah satu operasi dasar matematika.
“Semua orang berpikir bahwa metode penggandaan yang mereka ajarkan di sekolah adalah yang terbaik, tetapi pada kenyataannya, penelitian aktif sedang dilakukan di bidang ini,” kata
Joris van der Hoeven , seorang ahli matematika di Pusat Penelitian Ilmiah Nasional Prancis, salah satu rekan penulis karya tersebut.
Kompleksitas banyak masalah komputasi, mulai dari penghitungan angka baru number hingga menemukan bilangan prima yang besar, berkurang hingga tingkat penggandaan. Van der Hoeven menggambarkan hasil mereka sebagai penugasan semacam batas kecepatan matematika untuk memecahkan banyak masalah lainnya.
"Dalam fisika, ada konstanta penting seperti kecepatan cahaya yang memungkinkan Anda menggambarkan semua jenis fenomena," kata van der Hoeven. "Jika Anda ingin tahu seberapa cepat komputer dapat memecahkan masalah matematika tertentu, maka penggandaan bilangan bulat muncul dalam bentuk beberapa blok bangunan dasar, sehubungan dengan mana Anda dapat mengekspresikan kecepatan seperti itu."
Hampir setiap orang belajar mengalikan angka dengan cara yang sama. Kami menulis angka dalam kolom, mengalikan angka teratas dengan setiap digit bagian bawah (dengan memperhitungkan angka) dan menambahkan hasilnya. Ketika Anda mengalikan dua angka dua digit, Anda harus melakukan empat perkalian yang lebih kecil untuk mendapatkan hasil akhir.
Metode "
transfer " sekolah membutuhkan n
2 langkah, di mana n adalah jumlah digit di masing-masing angka yang dikalikan. Perhitungan dengan angka tiga digit membutuhkan sembilan perkalian, dan dengan angka satu digit, 10.000.
Metode transfer berfungsi dengan baik dengan angka yang terdiri dari beberapa digit, namun, ia mulai tergelincir ketika mengalikan angka yang terdiri dari jutaan atau milyaran digit (yang dilakukan komputer ketika menghitung secara akurat π atau ketika
mencari bilangan prima
besar di seluruh dunia ). Untuk mengalikan dua angka dengan satu miliar digit, Anda perlu menghasilkan satu miliar kuadrat, atau 10
18 , perkalian - ini akan memakan waktu sekitar 30 tahun untuk komputer modern.
Selama beberapa milenium, diyakini bahwa angka tidak dapat dikalikan lebih cepat. Kemudian pada tahun 1960, ahli matematika Soviet dan Rusia berusia 23 tahun
Anatoly Alekseevich Karatsuba menghadiri seminar yang diadakan oleh
Andrei Nikolayevich Kolmogorov , seorang ahli matematika Soviet, salah satu ahli matematika terhebat abad ke-20. Kolmogorov menyatakan bahwa tidak ada metode penggandaan umum yang membutuhkan kurang dari operasi n2. Karatsuba memutuskan bahwa ada metode seperti itu - dan setelah seminggu mencari dia menemukan itu.
Anatoly Alekseevich KaratsubaPenggandaan Karatsuba terdiri dari memecah angka-angka dan menggabungkannya kembali dengan cara baru, yang memungkinkan alih-alih sejumlah besar perkalian untuk melakukan penambahan dan pengurangan lebih sedikit. Metode ini menghemat waktu, karena penambahan hanya membutuhkan 2n langkah alih-alih n
2 .
Metode perkalian tradisional 25x63 membutuhkan empat perkalian satu digit dan beberapa tambahan
Penggandaan Karatsuba 25x63 membutuhkan tiga perkalian dengan satu angka dan beberapa penambahan dan pengurangan.
a) pecahkan angkanya
b) kalikan puluhan
c) mengalikan unit
d) menjumlahkan angkanya
e) gandakan jumlah ini
f) pertimbangkan e - b - c
g) mengumpulkan total b, c dan fKarena jumlah karakter dalam jumlah meningkat, metode Karatsuba dapat digunakan secara rekursif.
Metode tradisional untuk mengalikan 2531x1467 membutuhkan 16 perkalian dengan satu digit.
Perkalian Karatsuba 2531x1467 membutuhkan 9 perkalian."Penambahan di sekolah terjadi setahun sebelumnya, karena jauh lebih sederhana, berjalan dalam waktu linier, dengan kecepatan membaca angka dari kiri ke kanan," kata
Martin Fuhrer , seorang ahli matematika dari Pennsylvania State University, yang menciptakan algoritma multiplikasi tercepat pada 2007.
Ketika berhadapan dengan angka besar, penggandaan Karatsuba dapat diulang secara berulang, memecah angka asli menjadi bagian yang hampir sama banyaknya seperti ada tanda-tanda di dalamnya. Dan dengan setiap partisi, Anda mengubah perkalian, yang membutuhkan banyak langkah, untuk penambahan dan pengurangan, yang membutuhkan langkah yang jauh lebih sedikit.
"Beberapa perkalian dapat diubah menjadi penambahan, mengingat bahwa komputer akan dapat melakukan ini lebih cepat," kata
David Harvey , seorang ahli matematika di University of New South Wales dan penulis pendamping dari karya baru tersebut.
Metode Karatsuba memungkinkan untuk melipatgandakan angka hanya dengan menggunakan n
1,58 perkalian dengan satu digit. Kemudian, pada tahun 1971, Arnold Schönhage dan Volker Strassen menerbitkan metode untuk mengalikan angka besar dengan n × log n × log (log n) perkalian kecil. Untuk mengalikan dua angka dari satu miliar karakter, setiap metode Karatsuba akan membutuhkan 165 triliun langkah.
Joris van der Hoeven, ahli matematika di Pusat Nasional Perancis untuk Penelitian IlmiahMetode Schönhage-Strassen digunakan oleh komputer untuk melipatgandakan jumlah besar, dan telah menyebabkan dua konsekuensi penting lainnya. Pertama, ia memperkenalkan teknik dari bidang pemrosesan sinyal yang disebut
Fast Fourier Transform . Sejak itu, teknik ini telah menjadi dasar dari semua algoritma multiplikasi cepat.
Kedua, dalam karya yang sama, Schönhage dan Strassen menyarankan kemungkinan algoritma yang lebih cepat - metode yang hanya membutuhkan n × log dan perkalian dengan satu tanda - dan bahwa algoritma seperti itu akan menjadi yang tercepat yang mungkin. Asumsi ini didasarkan pada perasaan bahwa untuk operasi fundamental seperti perkalian, pembatasan operasi harus ditulis entah bagaimana lebih elegan daripada n × log n × log (log n).
"Paling umum sepakat bahwa penggandaan merupakan operasi dasar yang sangat penting sehingga, dari sudut pandang estetika murni, perlu pembatasan kompleksitas yang indah," kata Führer. "Dari pengalaman, kita tahu bahwa matematika hal-hal dasar selalu berakhir dengan anggun."
Pembatasan canggung Schönhage dan Strassen, n × log n × log (log n), berlangsung selama 36 tahun. Pada 2007,
Führer memecahkan rekor ini, dan itu semua terjadi. Selama dekade terakhir, matematikawan telah menemukan algoritma perkalian yang semakin cepat, yang masing-masing secara bertahap merangkak ke tanda n × log n, tidak cukup mencapainya. Kemudian pada bulan Maret tahun ini, Harvey dan van der Hoeven mencapainya.
Metode mereka adalah peningkatan dari pekerjaan hebat yang dilakukan sebelum mereka. Dia membagi angka menjadi tanda-tanda, menggunakan versi yang ditingkatkan dari transformasi Fourier cepat, dan mengambil keuntungan dari terobosan lain yang dibuat selama 40 tahun terakhir. "Kami menggunakan transformasi cepat Fourier jauh lebih kasar, menggunakannya beberapa kali, bukan hanya satu, dan mengganti bahkan lebih banyak perkalian dengan penambahan dan pengurangan," kata van der Hoeven.
Algoritma Harvey dan van der Hooven membuktikan bahwa multiplikasi dapat dilakukan dalam langkah-langkah n × log. Namun, ia tidak membuktikan tidak adanya metode yang lebih cepat. Akan jauh lebih sulit untuk menetapkan bahwa pendekatan mereka secepat mungkin. Pada akhir Februari, sebuah tim ilmuwan komputer dari Universitas Aarhus
menerbitkan sebuah makalah yang menyatakan bahwa jika salah satu teorema yang tidak terbukti ternyata benar, maka metode ini memang akan menjadi cara tercepat untuk berkembang biak.
Dan meskipun secara teori algoritma baru ini sangat penting, dalam praktiknya tidak akan banyak berubah, karena hanya sedikit mengalahkan algoritma yang sudah digunakan. "Yang bisa kita harapkan hanyalah akselerasi tiga kali lipat," kata van der Hoeven. "Tidak ada yang melampaui."
Selain itu, sirkuit peralatan komputer telah berubah. Dua puluh tahun yang lalu, komputer melakukan penambahan jauh lebih cepat daripada multiplikasi. Kesenjangan dalam tingkat penggandaan dan penambahan sejak itu telah menurun secara serius, sebagai akibatnya, pada beberapa chip, perkalian bahkan dapat menyalip penambahan. Menggunakan jenis peralatan tertentu, "Anda dapat mempercepat penambahan dengan memaksa komputer untuk melipatgandakan angka, dan ini semacam kegilaan," kata Harvey.
Peralatan berubah seiring waktu, tetapi algoritma terbaik di kelasnya bertahan selamanya. Tidak peduli bagaimana komputer terlihat di masa depan, algoritma Harvey dan van der Hooven masih akan menjadi cara paling efisien untuk melipatgandakan angka.