Bagaimanakah Kita Boleh Mengoptimumkan Transformasi NTT dan Aritmetik Modular untuk Kuasa Dua Bignum yang Lebih Pantas?

Aritmetik modular dan pengoptimuman NTT (medan terhingga DFT)

Masalah:

Dalam projek yang melibatkan kuasa dua menggunakan bignum pantas , pelaksanaan dengan NTT adalah perlahan, walaupun untuk bilangan besar (12000 bit atau lagi).

Soalan:

1. Adakah terdapat cara untuk mengoptimumkan transformasi NTT?
2. Adakah terdapat cara untuk mempercepatkan modular aritmetik?

Penyelesaian:

Transformasi NTT Dioptimumkan

Memisahkan fungsi NTT_fast kepada dua fungsi, satu dengan WW[] dan satu lagi dengan iWW[], membawa kepada kurang satu parameter dalam panggilan rekursi. Ini memberikan peningkatan prestasi yang kecil.

Aritmetik Modular Dioptimumkan

Kod asal menggunakan satu siri pemeriksaan cawangan dan keselamatan, yang boleh dihapuskan dengan menggunakan helah bit dan menyusun semula gelung utama. Kod pemasangan untuk modmul juga telah diubah suai untuk kecekapan.

Kod Baharu

class fourier_NTT
{
    // ...
    // Modular arithmetics (optimized, but it works only for p >= 0x80000000!!!)
    inline uint32 modadd(uint32 a, uint32 b)
    {
        uint32 d;
        //d = a + b;
        //!if (d < a)
        //    d -= p;
        //!if (d >= p)
        //    d -= p;
         __asm {
            mov eax, a;
            add eax, b
        }
        return d;
    }

    inline uint32 modsub(uint32 a, uint32 b)
    {
        uint32 d;
        //d = a - b;
        //!if (a < b)
        // a - b < 0 when a < b, so no need to check
        //!    d += p;
        __asm {
            mov eax, a;
            sub eax, b
        }
        return d;
    }

    inline uint32 modmul(uint32 a, uint32 b)
    {
        uint32 _a = a;
        uint32 _b = b;   

        __asm
        {
        mov eax, a;
        mul b;
        mov ebx, eax;
        mov eax, 2863311530;
        mov ecx, edx;
        mul edx;
        shld edx, eax, 1;
        mov eax, 3221225473;

        mul edx;
        sub ebx, eax;
        mov eax, 3221225473;
        sbb ecx, edx;
        jc addback;

            neg ecx;
            and ecx, eax;
            sub ebx, ecx;

        sub ebx, eax;
        sbb edx, edx;
        and eax, edx;
            addback:
        add eax, ebx;          
        };  
    }
    // ...
};

Kesimpulan

Pengoptimuman ini menghasilkan kelajuan 1.35x transformasi NTT dan aritmetik modular. Kod disediakan dalam C dan pemasangan sebaris.

Atas ialah kandungan terperinci Bagaimanakah Kita Boleh Mengoptimumkan Transformasi NTT dan Aritmetik Modular untuk Kuasa Dua Bignum yang Lebih Pantas?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!