快速bignum平方计算
问题:
如何计算 y = x^ 2 使用 C 和整数算术尽可能快且不损失精度(32 位进位)?
解法:
该问题可以使用Karatsuba乘法来解决,其复杂度为O(N^(log2(3))),其中N 是数量
实现:
这里是 Karatsuba 乘法的 C 实现:
void karatsuba(int *a, int *b, int n, int *c) { if (n <= 1) { c[0] = a[0] * b[0]; return; } int half = n / 2; int *a0 = new int[half]; int *a1 = new int[half]; int *b0 = new int[half]; int *b1 = new int[half]; for (int i = 0; i < half; i++) { a0[i] = a[i]; a1[i] = a[i + half]; b0[i] = b[i]; b1[i] = b[i + half]; } int *c0 = new int[half]; int *c1 = new int[half]; int *c2 = new int[n]; karatsuba(a0, b0, half, c0); karatsuba(a1, b1, half, c1); for (int i = 0; i < n; i++) c2[i] = 0; for (int i = 0; i < half; i++) for (int j = 0; j < half; j++) c2[i + j] += a0[i] * b1[j]; for (int i = 0; i < half; i++) for (int j = 0; j < half; j++) c2[i + j + half] += a1[i] * b0[j]; for (int i = 0; i < n; i++) c[i] = c0[i] + c1[i] + c2[i]; delete[] a0; delete[] a1; delete[] b0; delete[] b1; delete[] c0; delete[] c1; delete[] c2; }
这个实现的复杂度为 O(N ^(log2(3))),这比朴素的 O(N^2) 快得多
结论:
使用 Karatsuba 乘法,可以比使用朴素 O(N^2) 算法更快地计算 y = x^2。
以上是如何在 C 中使用整数算术有效地对大整数求平方?的详细内容。更多信息请关注PHP中文网其他相关文章!