


Bagaimanakah Saya Boleh Mengoptimumkan Transformasi Teoritik Nombor (NTT) dan Aritmetik Modular Saya untuk Kuadrat Pantas Nombor Sangat Besar?
Dec 18, 2024 pm 04:56 PMAritmetik modular dan pengoptimuman NTT (medan terhingga DFT)
Masalah: Saya ingin menggunakan NTT untuk kuasa dua pantas (lihat pengiraan kuasa dua besar Bignum Cepat), tetapi hasilnya adalah perlahan walaupun untuk benar-benar nombor besar .. lebih daripada 12000 bit.
Jadi soalan saya ialah:
- Adakah cara untuk mengoptimumkan transformasi NTT saya?
Saya tidak bermaksud untuk mempercepatkannya dengan selari (benang); ini adalah lapisan aras rendah sahaja. - Adakah terdapat cara untuk mempercepatkan aritmetik modular saya?
Ini ialah kod sumber saya (sudah dioptimumkan) dalam C untuk NTT (ia lengkap dan 100% bekerja dalam C tanpa sebarang keperluan untuk lib pihak ketiga dan juga harus selamat untuk thread. Awas tatasusunan sumber digunakan sebagai sementara!!!, Ia juga tidak boleh mengubah tatasusunan kepada dirinya sendiri).
//--------------------------------------------------------------------------- class fourier_NTT // Number theoretic transform { public: DWORD r,L,p,N; DWORD W,iW,rN; fourier_NTT(){ r=0; L=0; p=0; W=0; iW=0; rN=0; } // main interface void NTT(DWORD *dst,DWORD *src,DWORD n=0); // DWORD dst[n] = fast NTT(DWORD src[n]) void INTT(DWORD *dst,DWORD *src,DWORD n=0); // DWORD dst[n] = fast INTT(DWORD src[n]) // Helper functions bool init(DWORD n); // init r,L,p,W,iW,rN void NTT_fast(DWORD *dst,DWORD *src,DWORD n,DWORD w); // DWORD dst[n] = fast NTT(DWORD src[n]) // Only for testing void NTT_slow(DWORD *dst,DWORD *src,DWORD n,DWORD w); // DWORD dst[n] = slow NTT(DWORD src[n]) void INTT_slow(DWORD *dst,DWORD *src,DWORD n,DWORD w); // DWORD dst[n] = slow INTT(DWORD src[n]) // DWORD arithmetics DWORD shl(DWORD a); DWORD shr(DWORD a); // Modular arithmetics DWORD mod(DWORD a); DWORD modadd(DWORD a,DWORD b); DWORD modsub(DWORD a,DWORD b); DWORD modmul(DWORD a,DWORD b); DWORD modpow(DWORD a,DWORD b); }; //--------------------------------------------------------------------------- void fourier_NTT:: NTT(DWORD *dst,DWORD *src,DWORD n) { if (n>0) init(n); NTT_fast(dst,src,N,W); // NTT_slow(dst,src,N,W); } //--------------------------------------------------------------------------- void fourier_NTT::INTT(DWORD *dst,DWORD *src,DWORD n) { if (n>0) init(n); NTT_fast(dst,src,N,iW); for (DWORD i=0;i<N;i++) dst[i]=modmul(dst[i],rN); // INTT_slow(dst,src,N,W); } //--------------------------------------------------------------------------- bool fourier_NTT::init(DWORD n) { // (max(src[])^2)*n < p else NTT overflow can ocur !!! r=2; p=0xC0000001; if ((n<2)||(n>0x10000000)) { r=0; L=0; p=0; W=0; iW=0; rN=0; N=0; return false; } L=0x30000000/n; // 32:30 bit best for unsigned 32 bit // r=2; p=0x78000001; if ((n<2)||(n>0x04000000)) { r=0; L=0; p=0; W=0; iW=0; rN=0; N=0; return false; } L=0x3c000000/n; // 31:27 bit best for signed 32 bit // r=2; p=0x00010001; if ((n<2)||(n>0x00000020)) { r=0; L=0; p=0; W=0; iW=0; rN=0; N=0; return false; } L=0x00000020/n; // 17:16 bit best for 16 bit // r=2; p=0x0a000001; if ((n<2)||(n>0x01000000)) { r=0; L=0; p=0; W=0; iW=0; rN=0; N=0; return false; } L=0x01000000/n; // 28:25 bit N=n; // size of vectors [DWORDs] W=modpow(r, L); // Wn for NTT iW=modpow(r,p-1-L); // Wn for INTT rN=modpow(n,p-2 ); // scale for INTT return true; } //--------------------------------------------------------------------------- void fourier_NTT:: NTT_fast(DWORD *dst,DWORD *src,DWORD n,DWORD w) { if (n<=1) { if (n==1) dst[0]=src[0]; return; } DWORD i,j,a0,a1,n2=n>>1,w2=modmul(w,w); // reorder even,odd for (i=0,j=0;i<n2;i++,j+=2) dst[i]=src[j]; for ( j=1;i<n ;i++,j+=2) dst[i]=src[j]; // recursion NTT_fast(src ,dst ,n2,w2); // even NTT_fast(src+n2,dst+n2,n2,w2); // odd // restore results for (w2=1,i=0,j=n2;i<n2;i++,j++,w2=modmul(w2,w)) { a0=src[i]; a1=modmul(src[j],w2); dst[i]=modadd(a0,a1); dst[j]=modsub(a0,a1); } } //--------------------------------------------------------------------------- void fourier_NTT:: NTT_slow(DWORD *dst,DWORD *src,DWORD n,DWORD w) { DWORD i,j,wj,wi,a,n2=n>>1; for (wj=1,j=0;j<n;j++) { a=0; for (wi=1,i=0;i<n;i++) { a=modadd(a,modmul(wi,src[i])); wi=modmul(wi,wj); } dst[j]=a; wj=modmul(wj,w); } } //--------------------------------------------------------------------------- void fourier_NTT::INTT_slow(DWORD *dst,DWORD *src,DWORD n,DWORD w) { DWORD i,j,wi=1,wj=1,a,n2=n>>1; for (wj=1,j=0;j<n;j++) { a=0; for (wi=1,i=0;i<n;i++) { a=modadd(a,modmul(wi,src[i])); wi=modmul(wi,wj); } dst[j]=modmul(a,rN); wj=modmul(wj,iW); } } //---------------------------------------------------------------------------
Atas ialah kandungan terperinci Bagaimanakah Saya Boleh Mengoptimumkan Transformasi Teoritik Nombor (NTT) dan Aritmetik Modular Saya untuk Kuadrat Pantas Nombor Sangat Besar?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Alat AI Hot

Undress AI Tool
Gambar buka pakaian secara percuma

Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik

AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.

Clothoff.io
Penyingkiran pakaian AI

Video Face Swap
Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!

Artikel Panas

Alat 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

Polimorfisme dalam C dilaksanakan melalui fungsi maya dan kelas abstrak, meningkatkan kebolehgunaan semula dan fleksibiliti kod. 1) Fungsi maya membolehkan kelas yang diperoleh untuk mengatasi kaedah kelas asas, 2) kelas abstrak menentukan antara muka, dan kelas yang diperolehi untuk melaksanakan kaedah tertentu. Mekanisme ini menjadikan kod ini lebih fleksibel dan berskala, tetapi perhatian harus dibayar kepada kemungkinan peningkatan dalam runtime overhead dan kerumitan kod.

Ya, kelebihan fungsi adalah bentuk polimorfik dalam C, khususnya polimorfisme kompilasi masa. 1. Kelebihan fungsi membolehkan pelbagai fungsi dengan nama yang sama tetapi senarai parameter yang berbeza. 2. Pengkompil memutuskan yang berfungsi untuk memanggil pada masa penyusunan berdasarkan parameter yang disediakan. 3.

Pemusnah dalam C digunakan untuk membebaskan sumber yang diduduki oleh objek. 1) Mereka secara automatik dipanggil pada akhir kitaran hayat objek, seperti meninggalkan skop atau menggunakan padam. 2) Pengurusan sumber, pengoptimuman keselamatan dan pengoptimuman prestasi harus dipertimbangkan semasa reka bentuk. 3) Elakkan membuang pengecualian dalam pemusnah dan gunakan mod RAII untuk memastikan pelepasan sumber. 4) Tentukan pemusnah maya di kelas asas untuk memastikan objek kelas yang diperolehi dimusnahkan dengan betul. 5) Pengoptimuman prestasi boleh dicapai melalui kolam objek atau penunjuk pintar. 6) Pastikan benang pemusnah selamat dan ringkas, dan fokus pada pelepasan sumber.

C mempunyai dua jenis polimorf utama: polimorfisme kompilasi masa dan polimorfisme jangka masa. 1. Polimorfisme masa kompilasi dilaksanakan melalui fungsi overloading dan templat, memberikan kecekapan yang tinggi tetapi boleh menyebabkan kod kembung. 2. Polimorfisme runtime dilaksanakan melalui fungsi maya dan warisan, memberikan fleksibiliti tetapi overhead prestasi.

Melaksanakan polimorfisme dalam C boleh dicapai melalui langkah -langkah berikut: 1) Gunakan Warisan dan Fungsi Maya, 2) Tentukan kelas asas yang mengandungi fungsi maya, 3) menulis semula fungsi maya ini dengan kelas yang diperolehi, dan 4) panggil fungsi -fungsi ini menggunakan petunjuk kelas atau rujukan. Polimorfisme membolehkan pelbagai jenis objek dianggap sebagai objek jenis asas yang sama, dengan itu meningkatkan fleksibiliti dan pemeliharaan kod.

Ya, polimorfisme di C sangat berguna. 1) Ia menyediakan fleksibiliti untuk membolehkan penambahan mudah jenis baru; 2) Menggalakkan penggunaan semula kod dan mengurangkan pertindihan; 3) Memudahkan penyelenggaraan, menjadikan kod lebih mudah untuk berkembang dan menyesuaikan diri dengan perubahan. Walaupun terdapat cabaran pengurusan prestasi dan memori, kelebihannya amat penting dalam sistem yang kompleks.

C destructorscanleadtoSeveralCommonerrors.toavoidthem: 1) pencegahandoubledeletionbysettingpointerstonullptrorusingsmartpointers.2)

Polimorfisme dalam C dibahagikan kepada polimorfisme runtime dan polimorfisme kompilasi masa. 1. Polimorfisme runtime dilaksanakan melalui fungsi maya, yang membolehkan kaedah yang betul dipanggil secara dinamik pada masa runtime. 2. Polimorfisme masa kompilasi dilaksanakan melalui fungsi overloading dan templat, memberikan prestasi dan fleksibiliti yang lebih tinggi.
