Anak-anak mempelajari tabel perkalian mereka di sekolah. Hafalkan mereka. Semoga berhasil dengan angka tiga digit. Di situlah algoritma berperan. Anda menumpuk angka-angkanya. Kalikan baris demi baris. Selama ribuan tahun, kami pikir itulah yang terbaik yang bisa kami lakukan. Ini lambat. Sangat lambat untuk data besar. Kemudian pada tahun 1960, seorang pria berusia 23 tahun mengubah segalanya. Misteri kecepatan perkalian masih terbuka lebar.
Mengapa itu penting
Perkalian bukan hanya pekerjaan rumah. Ini menjalankan internet. Enkripsi, AI, pemrosesan audio. Semuanya bersandar pada perkalian. Perkalian berat. Saat Anda mengalikan angka-angka besar jutaan kali per detik, setiap langkah berarti. Sedikit peningkatan efisiensi akan menghemat miliaran dolar.
Lihatlah metode sekolah dasar. Dua digit berarti empat perkalian satu digit. Tiga digit? Sembilan. Ini berskala kuadrat. Gandakan panjangnya, lipat empatkan pekerjaannya. Gandakan lagi, pekerjaan meningkat enam belas kali lipat. Ilmuwan komputer mengabaikan detik. Perangkat keras tetap mempercepat. Mereka menghitung langkah. Kami menyebutnya notasi Big O. Sekolah dasar adalah O(n^2). Kuadrat. Jika jumlah Anda bertambah 1.000, pekerjaan Anda akan meledak satu juta.
Beban kerja berskala berdasarkan kuadrat jumlah digit.
Sejak jaman dahulu, ahli matematika berasumsi bahwa batas kuadrat ini adalah hukum alam. Andrey Kolmogorov, seorang legenda Soviet, mempertaruhkan reputasinya dalam sebuah ceramah tahun 1960. Dia mengatakan kepada para mahasiswa di Universitas Negeri Moskow: “Dibutuhkan O(n^2).” Ini adalah dugaan formal. Sebuah tantangan. Tunggu seseorang untuk membuktikannya atau menghancurkannya.
Butuh waktu seminggu. Anatoly Karatsuba duduk di antara penonton. Dia berusia 23 tahun. Dia kembali dengan bukti bahwa Kolmogorov salah. Profesor itu tercengang. Kolmogorov sebenarnya menulis makalah itu sendiri untuk jurnal bergengsi tetapi mencantumkan nama Karatsuba di dalamnya. Anak itu tidak mengetahuinya sampai cetakan ulangnya tiba melalui pos.
Triknya
Karatsuba menyadari sesuatu yang sederhana namun mendalam. Perkalian itu mahal. Tambahannya murah. Mengapa tidak memperdagangkannya?
Ambil 12×34.
Pisahkan.
12 adalah 10 + 2.
34 adalah 30 + 4.
Secara tradisional, Anda melakukan empat perkalian:
1×3
1×4
2×3
2×4
Karatsuba menemukan cara untuk melakukannya dengan tiga orang.
Hitung bagian pertama: 1×3 = 3.
Hitung bagian terakhir: 2×4 = 8.
Sekarang tengah. Biasanya Anda akan melakukan (1×4) + (2×3). Dua kali lipat. Sebagai gantinya, tambahkan angka pertama: 1+2=3. Tambahkan angka terakhir: 3+4=7. Kalikan jumlah tersebut: 3×7=21. Kurangi bagian yang sudah Anda ketahui. 21 – 3 – 8 = 10.
ledakan. Anda mendapatkan suku tengah dengan satu perkalian tambahan.
Apakah ini sepadan?
Bukan untuk jumlah kecil. Biaya tambahan untuk pemisahan dan penambahan akan membebani Anda.
Tapi untuk 1.234 x 5.678? Bagi menjadi dua. Berulang. Pisahkan bagian itu. Lakukan lagi. Senyawa tabungan.
Algoritme turun menjadi kira-kira O(n^1.585).
Angka seribu digit biasanya membutuhkan satu juta angka multi digit. Sekarang dibutuhkan kurang dari 57,00 langkah. Besar sekali.
Ini bukan hanya teori. Itu dengan Python.
Python menggunakan matematika sekolah standar untuk masukan kecil. Cukup halus.
Setelah Anda mencapai sekitar 63 digit desimal (tergantung pada basis mesin), Python akan menekan tombolnya. Karatsuba mengambil alih. Anda tidak melihatnya terjadi. Tapi itu ada di sana. Menangani kriptografi Anda.
Algoritma Galaksi
Perlombaan berlanjut selama beberapa dekade. Bisakah kita melaju lebih cepat?
Tahun 2019 membawa kejutan terbaru. David Harvey dan Joris van Der Hoeven menerbitkan algoritma yang mengalahkan Karatsuba sejauh satu mil.
HAI(n log n).
Baca itu lagi.
Logaritma tumbuh sangat lambat.
n log n hampir tidak lebih besar dari n.
Pada dasarnya, mengalikan dua bilangan masif kini membutuhkan waktu yang hampir sama dengan membacanya.
Ini mengejutkan. Batasan teoretis tampaknya telah tersentuh.
Atau mungkin tidak.
Inilah hasil tangkapannya.
Ini tidak berlaku untuk angka-angka yang kita pedulikan.
Algoritme Harvey dan Van Der Hoeven hanya menjadi lebih cepat daripada Karatsuba ketika angkanya menjadi sangat besar. Bukan “nomor kartu kredit” yang besar. Galaksi besar.
Dalam ilmu komputer kita mempunyai istilah untuk ini: algoritma galaksi.
Teori yang indah. Tidak ada penggunaan praktis. Jumlah yang dibutuhkan lebih besar daripada gabungan sebagian besar transaksi digital dalam sejarah manusia.
Kita terjebak di tengah.
Menggunakan trik tahun 1960-an untuk sebagian besar komputasi harian kita.
Mengenakan pakaian abad ke-21 di atas matematika abad ke-20.
Apakah kita pernah menggunakan O(n log n) di dunia nyata?
Mungkin saat kita memproses kumpulan data sebesar galaksi.
Sampai saat itu kita menunggu.
Untuk trik selanjutnya.
Atau perangkat keras yang lebih baik untuk menyembunyikan kemalasan kita.
Jawabannya mungkin masih kuadrat.
Ini mungkin linier.
Kami belum tahu.
