


Bagaimanakah saya boleh mengoptimumkan Transformasi Teori Nombor (NTT) dan aritmetik modular saya untuk pengiraan yang lebih pantas, terutamanya dengan nombor yang sangat besar (cth., melebihi 12000 bit)?
Dec 16, 2024 am 03:13 AMAritmetik modular dan pengoptimuman NTT (medan terhingga DFT)
Pernyataan Masalah
<p>
Saya mahu menggunakan NTT dengan pantas kuasa dua (lihat pengiraan kuasa dua besar bignum cepat), tetapi hasilnya adalah perlahan walaupun untuk nombor yang sangat besar .. lebih daripada 12000 bit.
</p>
<p>
Jadi soalan saya ialah:
</p>
<ol>
<li>Adakah terdapat cara untuk mengoptimumkan transformasi NTT saya? Saya tidak bermaksud untuk mempercepatkannya dengan selari (benang); ini adalah lapisan aras rendah sahaja.</li>
<li>Adakah terdapat cara untuk mempercepatkan aritmetik modular saya?</li>
</ol>
<p>
Ini adalah kod sumber saya (sudah dioptimumkan) dalam C untuk NTT (ia lengkap dan 100% berfungsi dalam C tanpa memerlukan sebarang lib pihak ketiga dan juga harus selamat untuk benang. Berhati-hati susunan sumber digunakan sebagai sementara!!!, Juga ia tidak boleh mengubah tatasusunan kepada dirinya sendiri).
</p>
Penyelesaian Dioptimumkan
- Menggunakan Prakiraan Kuasa: Prakira dan simpan kuasa W dan iW (akar primitif perpaduan dan songsangnya) untuk mengelakkan pengiraan semula semasa proses NTT. Ini boleh mengurangkan bilangan pendaraban dan pembahagian dengan ketara, yang membawa kepada pengiraan yang lebih pantas.
- Membuka Gelung: Buka gulungan dalam algoritma NTT untuk mengurangkan overhed yang dikaitkan dengan lelaran gelung. Ini boleh meningkatkan prestasi dengan mengurangkan bilangan arahan cawangan.
- Mengoptimumkan Aritmetik Modular: Gunakan operasi bitwise dan bahasa himpunan untuk melaksanakan operasi aritmetik modular (tambah, tolak, darab dan eksponen) dengan cekap . Ini boleh menghapuskan pernyataan bercabang dan bersyarat yang tidak diperlukan, menghasilkan pelaksanaan yang lebih pantas.
Contoh Pelaksanaan
Berikut ialah contoh pelaksanaan NTT yang dioptimumkan dalam C menggunakan kuasa prapengiraan dan operasi bitwise:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 |
|
Tambahan Petua
- Gunakan bahasa peringkat lebih tinggi yang menyokong operasi bitwise dan pemasangan sebaris, seperti C .
- Gunakan profiler untuk mengenal pasti kesesakan dalam kod anda dan menyasarkannya untuk pengoptimuman.
- Pertimbangkan untuk menyelaraskan algoritma NTT menggunakan berbilang urutan atau arahan SIMD.
Atas ialah kandungan terperinci Bagaimanakah saya boleh mengoptimumkan Transformasi Teori Nombor (NTT) dan aritmetik modular saya untuk pengiraan yang lebih pantas, terutamanya dengan nombor yang sangat besar (cth., melebihi 12000 bit)?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Artikel Panas

Alat panas Tag

Artikel Panas

Tag artikel panas

Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6
Alat pembangunan web visual

SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Topik panas

Apakah jenis nilai yang dikembalikan oleh fungsi bahasa C? Apa yang menentukan nilai pulangan?

Langkah Format Fungsi Fungsi C Langkah Penukaran Kes

Gulc: Perpustakaan C dibina dari awal

Apakah definisi dan peraturan panggilan fungsi bahasa C dan apakah itu

Di manakah nilai pulangan fungsi bahasa C yang disimpan dalam ingatan?

Penggunaan dan perkongsian frasa yang berbeza

Bagaimana Perpustakaan Templat St Standard (STL) berfungsi?

Bagaimanakah saya menggunakan algoritma dari STL (jenis, mencari, mengubah, dll) dengan cekap?
