Apakah Algoritma Terpantas untuk Menduakan Integer Besar yang Diwakili sebagai Tatasusunan DWORD?

Pengiraan kuasa dua besar bignum yang pantas

Artikel ini bertujuan untuk menentukan kaedah terpantas untuk pengiraan y = x^2 untuk bigints yang dinyatakan sebagai tatasusunan dinamik DWORD yang tidak ditandatangani.

Pernyataan masalah

Memandangkan perwakilan x besar sebagai tatasusunan DWORD:

DWORD x[n+1] = { LSW, ......, MSW };

di mana:

• n 1 ialah bilangan DWORD yang digunakan
• x = x[0] x[1] <<32 ... x[N]<<32*(n)

Cari nilai y = x^2 secepat mungkin tanpa kehilangan ketepatan.

Andaian:

• Pengiraan dilakukan menggunakan C dan aritmetik integer 32-bit dengan carry.

Pendekatan naif (O(n^2) pendaraban)

Pendekatan naif melibatkan pendaraban x dengan sendirinya, yang mengambil masa O(n^2). Ini boleh dinyatakan sebagai:

y = x * x
y = (x0 + x1 + x2 + ...xn)*(x0 + x1 + x2 + ...xn)

Memperluas produk, kami mendapat:

y0     = x0*x0
y1     = x1*x0 + x0*x1
y2     = x2*x0 + x1*x1 + x0*x2
y3     = x3*x0 + x2*x1 + x1*x2
...
y(2n-3) = xn(n-2)*x(n  ) + x(n-1)*x(n-1) + x(n  )*x(n-2)
y(2n-2) = xn(n-1)*x(n  ) + x(n  )*x(n-1)
y(2n-1) = xn(n  )*x(n  )

Pendaraban Karatsuba

Algoritma Karatsuba boleh digunakan untuk mempercepatkan pendaraban kepada O(n^log2(3)). Walaupun nampaknya menjanjikan, sifat rekursif algoritma boleh memperkenalkan overhed prestasi yang ketara untuk nombor yang besar.

Pendaraban Schönhage-Strassen Dioptimumkan

Algoritma Schönhage-Strassen menawarkan pendaraban yang lebih pantas pada O( nlog(n)(log(log(n)))) menggunakan pendekatan bahagi-dan-takluk. Walau bagaimanapun, algoritma ini mempunyai had praktikal kerana isu limpahan dan keperluan untuk aritmetik modular pada integer tidak bertanda.

Kesimpulan

Untuk nombor yang lebih kecil, pendekatan pendaraban O(n^2) yang mudah ialah paling cekap. Untuk nombor yang lebih besar, algoritma pendaraban Karatsuba disyorkan. Pengoptimuman lanjut boleh diterokai untuk meningkatkan prestasi, seperti menggunakan FFT (Fast Fourier Transform) atau NTT (Number Theoretic Transform).

Atas ialah kandungan terperinci Apakah Algoritma Terpantas untuk Menduakan Integer Besar yang Diwakili sebagai Tatasusunan DWORD?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!