Jadual Kandungan
Aritmetik modular dan pengoptimuman NTT (medan terhingga DFT)
Pernyataan Masalah
Penyelesaian Dioptimumkan
Contoh Pelaksanaan
Tambahan Petua
Rumah pembangunan bahagian belakang C++ 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)?

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 AM

How can I optimize my Number Theoretic Transform (NTT) and modular arithmetic for faster computation, especially with very large numbers (e.g., over 12000 bits)?

Aritmetik 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

  1. 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.
  2. Membuka Gelung: Buka gulungan dalam algoritma NTT untuk mengurangkan overhed yang dikaitkan dengan lelaran gelung. Ini boleh meningkatkan prestasi dengan mengurangkan bilangan arahan cawangan.
  3. 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

class NTT {

public:

    NTT() {

        // Initialize constants

        p = 0xc0000001;

        W = modpow(2, 0x30000000 / n);

        iW = modpow(2, p - 1 - 0x30000000 / n);

        rN = modpow(n, p - 2);

        NN = n &gt;&gt; 1;

 

        // Precompute W and iW powers

        WW = new uint32_t[n];

        iWW = new uint32_t[n];

        WW[0] = 1;

        iWW[0] = 1;

        for (uint32_t i = 1; i &lt; n; i++) {

            WW[i] = modmul(WW[i - 1], W);

            iWW[i] = modmul(iWW[i - 1], iW);

        }

    }

 

    void NTT(uint32_t *dst, uint32_t *src, uint32_t n) {

        if (n &gt; 0) {

            // Reorder even, odd elements

            for (uint32_t i = 0, j = 0; i &lt; NN; i++, j += 2) {

                dst[i] = src[j];

            }

            for (j = 1; i &lt; n; i++, j += 2) {

                dst[i] = src[j];

            }

 

            // Recursive NTT

            NTT(src, dst, NN);  // Even

            NTT(src + NN, dst + NN, NN);  // Odd

 

            // Restore results

            for (uint32_t i = 0, j = NN; i &lt; NN; i++, j++) {

                uint32_t a0 = src[i];

                uint32_t a1 = modmul(src[j], WW[i]);

                dst[i] = modadd(a0, a1);

                dst[j] = modsub(a0, a1);

            }

        }

    }

 

private:

    uint32_t p, n, NN, W, iW, rN;

    uint32_t *WW, *iWW;

 

    // Modular arithmetic operations

    inline uint32_t modadd(uint32_t a, uint32_t b) {

        uint32_t d = a + b;

        if (d &gt;= p) d -= p;

        return d;

    }

 

    inline uint32_t modsub(uint32_t a, uint32_t b) {

        uint32_t d = a - b;

        if (d &gt; a) d += p;

        return d;

    }

 

    inline uint32_t modmul(uint32_t a, uint32_t b) {

        uint32_t m = (uint64_t)a * b;

        return m - (p * (m / p));

    }

 

    inline uint32_t modpow(uint32_t a, uint32_t b) {

        if (b == 0) return 1;

        uint32_t t = modpow(a, b / 2);

        t = modmul(t, t);

        if (b &amp;amp; 1) t = modmul(t, a);

        return t;

    }

};

Salin selepas log masuk

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!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn

Tag artikel panas

Notepad++7.3.1

Notepad++7.3.1

Editor kod yang mudah digunakan dan percuma

SublimeText3 versi Cina

SublimeText3 versi Cina

Versi Cina, sangat mudah digunakan

Hantar Studio 13.0.1

Hantar Studio 13.0.1

Persekitaran pembangunan bersepadu PHP yang berkuasa

Dreamweaver CS6

Dreamweaver CS6

Alat pembangunan web visual

SublimeText3 versi Mac

SublimeText3 versi Mac

Perisian penyuntingan kod peringkat Tuhan (SublimeText3)

Apakah jenis nilai yang dikembalikan oleh fungsi bahasa C? Apa yang menentukan nilai pulangan? Apakah jenis nilai yang dikembalikan oleh fungsi bahasa C? Apa yang menentukan nilai pulangan? Mar 03, 2025 pm 05:52 PM

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

Langkah Format Fungsi Fungsi C Langkah Penukaran Kes Langkah Format Fungsi Fungsi C Langkah Penukaran Kes Mar 03, 2025 pm 05:53 PM

Langkah Format Fungsi Fungsi C Langkah Penukaran Kes

Gulc: Perpustakaan C dibina dari awal Gulc: Perpustakaan C dibina dari awal Mar 03, 2025 pm 05:46 PM

Gulc: Perpustakaan C dibina dari awal

Apakah definisi dan peraturan panggilan fungsi bahasa C dan apakah itu Apakah definisi dan peraturan panggilan fungsi bahasa C dan apakah itu Mar 03, 2025 pm 05:53 PM

Apakah definisi dan peraturan panggilan fungsi bahasa C dan apakah itu

Di manakah nilai pulangan fungsi bahasa C yang disimpan dalam ingatan? Di manakah nilai pulangan fungsi bahasa C yang disimpan dalam ingatan? Mar 03, 2025 pm 05:51 PM

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

Penggunaan dan perkongsian frasa yang berbeza Penggunaan dan perkongsian frasa yang berbeza Mar 03, 2025 pm 05:51 PM

Penggunaan dan perkongsian frasa yang berbeza

Bagaimana Perpustakaan Templat St Standard (STL) berfungsi? Bagaimana Perpustakaan Templat St Standard (STL) berfungsi? Mar 12, 2025 pm 04:50 PM

Bagaimana Perpustakaan Templat St Standard (STL) berfungsi?

Bagaimanakah saya menggunakan algoritma dari STL (jenis, mencari, mengubah, dll) dengan cekap? Bagaimanakah saya menggunakan algoritma dari STL (jenis, mencari, mengubah, dll) dengan cekap? Mar 12, 2025 pm 04:52 PM

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

See all articles