Bagaimana Kita Boleh Mencapai Pengiraan Kuasa Dua Pantas Nombor Besar?

Pengiraan Kuasa Pantas Nombor Besar

Masalah:
Diberikan bignum yang diwakili sebagai tatasusunan dinamik DWORD yang tidak ditandatangani, tugasnya adalah untuk mencari kuasa dua bignum secepat mungkin tanpa kehilangan ketepatan.

Pendekatan Penyelesaian:

Algoritma yang disediakan secara cekap mengira kuasa dua bignum dengan mengoptimumkan pendaraban menggunakan pendekatan bahagi-dan-takluk.

Karatsuba Dioptimumkan Pendaraban:

Selepas tweak dan pengoptimuman, pendaraban Karatsuba lebih pantas daripada pendaraban klasik O(N^2) untuk saiz input melebihi 32*98 bit. Untuk nombor yang lebih kecil, kaedah kuasa dua pantas kekal lebih cekap.

Pendaraban Schönhage-Strassen Diubah Suai untuk Pelaksanaan Kuasa Dua:

Transformasi FFT dan NTT telah diterokai untuk mempercepatkan, tetapi mereka kehilangan ketepatan dan kerumitan pelaksanaan menjadikannya kurang sesuai.

NTT Pengoptimuman:

Pengoptimuman intensif NTT menghasilkan prestasi yang lebih baik, dengan ambang untuk NTT sqr ditetapkan pada 31032 bit dan NTT mul pada 139632 bit.

Kesimpulan:

Untuk nombor yang lebih kecil, kaedah kuasa dua pantas terbukti sebagai pilihan terpantas. Selepas ambang, pendaraban Karatsuba menjadi lebih cekap. Walau bagaimanapun, pencarian alternatif yang lebih cekap kepada Karatsuba diteruskan.

Atas ialah kandungan terperinci Bagaimana Kita Boleh Mencapai Pengiraan Kuasa Dua Pantas Nombor Besar?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!