凑数的,仅供参考。
1 文本格式
/// <summary>
/// 《小白学程序》第二十六课:大数(BigInteger)的Toom-Cook 3乘法
/// Toom-Cook 3-Way Multiplication
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static string toom_cook3_multiply(string a, string b)
{
int n = Math.Max(a.Length, b.Length);
int[] ra = string_to_digitals(a, n);
int[] rb = string_to_digitals(b, n);
toom_cook3_process_00(ra, rb, out int[] rz);
toom_cook3_carry(rz, n * 2);
return digitals_to_string(rz);
}
/// <summary>
/// 短数字的乘法(常规乘法,小学生算法)
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <param name="z"></param>
private static void toom_cook3_normal(int[] a, int[] b, ref int[] z)
{
int n = a.Length;
for (int j = 0; j < n; j++)
{
for (int i = 0; i < n; i++)
{
z[j + i] += a[i] * b[j];
}
}
}
/// <summary>
/// 完全按原始C++代码改写;运行成功;
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <param name="z"></param>
private static void toom_cook3_process_01(int[] a, int[] b, out int[] z)
{
int n = a.Length;
int n1 = n * 1 / 3;
int n2 = n * 2 / 3;
int n3 = n * 3 / 3;
int n4 = n * 4 / 3;
z = new int[n * 2];
if (n <= 9)
{
toom_cook3_normal(a, b, ref z);
return;
}
// int *a0 = &a[0];
// Multiplicand / right side array pointer
int a0 = 0;
// int *a1 = &a[tLen / 3];
// Multiplicand / central array pointer
int a1 = n1;
// int *a2 = &a[tLen * 2/ 3];
// Multiplicand / left side array pointer
int a2 = n2;// n * 2 / 3;
// int *b0 = &b[0];
// Multiplier / right side array pointer
int b0 = 0;
// int *b1 = &b[tLen / 3];
// Multiplier / central array pointer
int b1 = n1;
// int *b2 = &b[tLen * 2 / 3];
// Multiplier / left side array pointer
int b2 = n2;// n * 2 / 3;
// int *c0 = &z[(tLen / 3) * 0];
int[] c0 = new int[n2];
int[] c1 = new int[n2];
// int *c2 = &z[(tLen / 3) * 2];
int[] c2 = new int[n2];
int[] c3 = new int[n2];
// int *c4 = &z[(tLen / 3) * 4];
int[] c4 = new int[n2];
int[] a_m2 = new int[n1]; // a(-2)
int[] a_m1 = new int[n1]; // a(-1)
int[] a_0 = new int[n1]; // a(0)
int[] a_1 = new int[n1]; // a(1)
int[] a_inf = new int[n1]; // a(inf)
int[] b_m2 = new int[n1]; // b-2)
int[] b_m1 = new int[n1]; // b-1)
int[] b_0 = new int[n1]; // b(0)
int[] b_1 = new int[n1]; // b(1)
int[] b_inf = new int[n1]; // b(inf)
// ==== a(-2) = 4 * a2 - 2 * a1 + a0, b(-2) = 4 * b2 - 2 * b1 + b0
for (int i = 0; i < n1; i++)
{
a_m2[i] = (a[a2 + i] << 2) - (a[a1 + i] << 1) + a[a0 + i];
b_m2[i] = (b[b2 + i] << 2) - (b[b1 + i] << 1) + b[b0 + i];
}
// ==== c(-2) = a(-2) * b(-2)
toom_cook3_process_01(a_m2, b_m2, out int[] c_m2);
// ==== a(-1) = a2 - a1 + a0, b(-1) = b2 - b1 + b0
for (int i = 0; i < n1; i++)
{
a_m1[i] = a[a2 + i] - a[a1 + i] + a[a0 + i];
b_m1[i] = b[b2 + i] - b[b1 + i] + b[b0 + i];
}
// ==== c(-1) = a(-1) * b(-1)
toom_cook3_process_01(a_m1, b_m1, out int[] c_m1);
// ==== a(0) = a0, b(0) = b0
for (int i = 0; i < n1; i++)
{
a_0[i] = a[a0 + i];
b_0[i] = b[b0 + i];
}
// ==== c(0) = a(0) * b(0)
toom_cook3_process_01(a_0, b_0, out int[] c_0);
// ==== a(1) = a2 + a1 + a0, b(1) = b2 + b1 + b0
for (int i = 0; i < n1; i++)
{
a_1[i] = a[a2 + i] + a[a1 + i] + a[a0 + i];
b_1[i] = b[b2 + i] + b[b1 + i] + b[b0 + i];
}
// ==== c(1) = a(1) * b(1)
toom_cook3_process_01(a_1, b_1, out int[] c_1);
// ==== a(inf) = a2, b(inf) = b2
for (int i = 0; i < n1; i++)
{
a_inf[i] = a[a2 + i];
b_inf[i] = b[b2 + i];
}
// ==== c(inf) = a(inf) * b(inf)
toom_cook3_process_01(a_inf, b_inf, out int[] c_inf);
// ==== c4 = 6 * c(inf) / 6
for (int i = 0; i < n2; i++)
{
c4[i] = c_inf[i];
}
// ==== c3 = -c(-2) + 3 * c(-1) - 3 * c(0) + c(1) + 12 * c(inf) / 6
for (int i = 0; i < n2; i++)
{
c3[i] = -c_m2[i];
c3[i] += (c_m1[i] << 1) + c_m1[i];
c3[i] -= (c_0[i] << 1) + c_0[i];
c3[i] += c_1[i];
c3[i] += (c_inf[i] << 3) + (c_inf[i] << 2);
c3[i] /= 6;
}
// ==== c2 = 3 * c(-1) - 6 * c(0) + 3 * c(1) - 6 * c(inf) / 6
for (int i = 0; i < n2; i++)
{
c2[i] = (c_m1[i] << 1) + c_m1[i];
c2[i] -= (c_0[i] << 2) + (c_0[i] << 1);
c2[i] += (c_1[i] << 1) + c_1[i];
c2[i] -= (c_inf[i] << 2) + (c_inf[i] << 1);
c2[i] /= 6;
}
// ==== c1 = c(-2) - 6 * c(-1) + 3 * c(0) + 2 * c(1) - 12 * c(inf) / 6
for (int i = 0; i < n2; i++)
{
c1[i] = c_m2[i];
c1[i] -= (c_m1[i] << 2) + (c_m1[i] << 1);
c1[i] += (c_0[i] << 1) + c_0[i];
c1[i] += (c_1[i] << 1);
c1[i] -= (c_inf[i] << 3) + (c_inf[i] << 2);
c1[i] /= 6;
}
// ==== c0 = 6 * c(0) / 6
for (int i = 0; i < n2; i++)
{
c0[i] = c_0[i];
}
// ==== z = c4 * x^4 + c3 * x^3 + c2 * x^2 + c1 * x + c0
for (int i = 0; i < n2; i++)
{
z[i + n4] += c4[i];
z[i + n3] += c3[i];
z[i + n2] += c2[i];
z[i + n1] += c1[i];
z[i] += c0[i];
}
}
/// <summary>
/// 乘积和的进位计算
/// </summary>
/// <param name="a"></param>
/// <param name="n"></param>
/// <exception cref="Exception"></exception>
private static void toom_cook3_carry(int[] a, int n)
{
int cr = 0;
for (int i = 0; i < n; i++)
{
a[i] += cr;
if (a[i] < 0)
{
cr = -(-(a[i] + 1) / 10 + 1);
}
else
{
cr = a[i] / 10;
}
a[i] -= cr * 10;
}
if (cr != 0)
{
// Overflow
throw new Exception("OVERFLOW! cr=" + cr);
}
}
2 代码格式
/// <summary>
/// 《小白学程序》第二十六课:大数(BigInteger)的Toom-Cook 3乘法
/// Toom-Cook 3-Way Multiplication
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static string toom_cook3_multiply(string a, string b)
{int n = Math.Max(a.Length, b.Length);int[] ra = string_to_digitals(a, n);int[] rb = string_to_digitals(b, n);toom_cook3_process_00(ra, rb, out int[] rz);toom_cook3_carry(rz, n * 2);return digitals_to_string(rz);
}/// <summary>
/// 短数字的乘法(常规乘法,小学生算法)
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <param name="z"></param>
private static void toom_cook3_normal(int[] a, int[] b, ref int[] z)
{int n = a.Length;for (int j = 0; j < n; j++){for (int i = 0; i < n; i++){z[j + i] += a[i] * b[j];}}
}/// <summary>
/// 完全按原始C++代码改写;运行成功;
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <param name="z"></param>
private static void toom_cook3_process_01(int[] a, int[] b, out int[] z)
{int n = a.Length;int n1 = n * 1 / 3;int n2 = n * 2 / 3;int n3 = n * 3 / 3;int n4 = n * 4 / 3;z = new int[n * 2];if (n <= 9){toom_cook3_normal(a, b, ref z);return;}// int *a0 = &a[0];// Multiplicand / right side array pointerint a0 = 0;// int *a1 = &a[tLen / 3];// Multiplicand / central array pointerint a1 = n1;// int *a2 = &a[tLen * 2/ 3];// Multiplicand / left side array pointerint a2 = n2;// n * 2 / 3;// int *b0 = &b[0];// Multiplier / right side array pointerint b0 = 0;// int *b1 = &b[tLen / 3];// Multiplier / central array pointerint b1 = n1;// int *b2 = &b[tLen * 2 / 3];// Multiplier / left side array pointerint b2 = n2;// n * 2 / 3;// int *c0 = &z[(tLen / 3) * 0];int[] c0 = new int[n2];int[] c1 = new int[n2];// int *c2 = &z[(tLen / 3) * 2];int[] c2 = new int[n2];int[] c3 = new int[n2];// int *c4 = &z[(tLen / 3) * 4];int[] c4 = new int[n2];int[] a_m2 = new int[n1]; // a(-2)int[] a_m1 = new int[n1]; // a(-1)int[] a_0 = new int[n1]; // a(0)int[] a_1 = new int[n1]; // a(1)int[] a_inf = new int[n1]; // a(inf)int[] b_m2 = new int[n1]; // b-2)int[] b_m1 = new int[n1]; // b-1)int[] b_0 = new int[n1]; // b(0)int[] b_1 = new int[n1]; // b(1)int[] b_inf = new int[n1]; // b(inf)// ==== a(-2) = 4 * a2 - 2 * a1 + a0, b(-2) = 4 * b2 - 2 * b1 + b0for (int i = 0; i < n1; i++){a_m2[i] = (a[a2 + i] << 2) - (a[a1 + i] << 1) + a[a0 + i];b_m2[i] = (b[b2 + i] << 2) - (b[b1 + i] << 1) + b[b0 + i];}// ==== c(-2) = a(-2) * b(-2)toom_cook3_process_01(a_m2, b_m2, out int[] c_m2);// ==== a(-1) = a2 - a1 + a0, b(-1) = b2 - b1 + b0for (int i = 0; i < n1; i++){a_m1[i] = a[a2 + i] - a[a1 + i] + a[a0 + i];b_m1[i] = b[b2 + i] - b[b1 + i] + b[b0 + i];}// ==== c(-1) = a(-1) * b(-1)toom_cook3_process_01(a_m1, b_m1, out int[] c_m1);// ==== a(0) = a0, b(0) = b0for (int i = 0; i < n1; i++){a_0[i] = a[a0 + i];b_0[i] = b[b0 + i];}// ==== c(0) = a(0) * b(0)toom_cook3_process_01(a_0, b_0, out int[] c_0);// ==== a(1) = a2 + a1 + a0, b(1) = b2 + b1 + b0for (int i = 0; i < n1; i++){a_1[i] = a[a2 + i] + a[a1 + i] + a[a0 + i];b_1[i] = b[b2 + i] + b[b1 + i] + b[b0 + i];}// ==== c(1) = a(1) * b(1)toom_cook3_process_01(a_1, b_1, out int[] c_1);// ==== a(inf) = a2, b(inf) = b2for (int i = 0; i < n1; i++){a_inf[i] = a[a2 + i];b_inf[i] = b[b2 + i];}// ==== c(inf) = a(inf) * b(inf)toom_cook3_process_01(a_inf, b_inf, out int[] c_inf);// ==== c4 = 6 * c(inf) / 6for (int i = 0; i < n2; i++){c4[i] = c_inf[i];}// ==== c3 = -c(-2) + 3 * c(-1) - 3 * c(0) + c(1) + 12 * c(inf) / 6for (int i = 0; i < n2; i++){c3[i] = -c_m2[i];c3[i] += (c_m1[i] << 1) + c_m1[i];c3[i] -= (c_0[i] << 1) + c_0[i];c3[i] += c_1[i];c3[i] += (c_inf[i] << 3) + (c_inf[i] << 2);c3[i] /= 6;}// ==== c2 = 3 * c(-1) - 6 * c(0) + 3 * c(1) - 6 * c(inf) / 6for (int i = 0; i < n2; i++){c2[i] = (c_m1[i] << 1) + c_m1[i];c2[i] -= (c_0[i] << 2) + (c_0[i] << 1);c2[i] += (c_1[i] << 1) + c_1[i];c2[i] -= (c_inf[i] << 2) + (c_inf[i] << 1);c2[i] /= 6;}// ==== c1 = c(-2) - 6 * c(-1) + 3 * c(0) + 2 * c(1) - 12 * c(inf) / 6for (int i = 0; i < n2; i++){c1[i] = c_m2[i];c1[i] -= (c_m1[i] << 2) + (c_m1[i] << 1);c1[i] += (c_0[i] << 1) + c_0[i];c1[i] += (c_1[i] << 1);c1[i] -= (c_inf[i] << 3) + (c_inf[i] << 2);c1[i] /= 6;}// ==== c0 = 6 * c(0) / 6for (int i = 0; i < n2; i++){c0[i] = c_0[i];}// ==== z = c4 * x^4 + c3 * x^3 + c2 * x^2 + c1 * x + c0for (int i = 0; i < n2; i++){z[i + n4] += c4[i];z[i + n3] += c3[i];z[i + n2] += c2[i];z[i + n1] += c1[i];z[i] += c0[i];}
}/// <summary>/// 乘积和的进位计算/// </summary>/// <param name="a"></param>/// <param name="n"></param>/// <exception cref="Exception"></exception>private static void toom_cook3_carry(int[] a, int n){int cr = 0;for (int i = 0; i < n; i++){a[i] += cr;if (a[i] < 0){cr = -(-(a[i] + 1) / 10 + 1);}else{cr = a[i] / 10;}a[i] -= cr * 10;}if (cr != 0){// Overflowthrow new Exception("OVERFLOW! cr=" + cr);}}