naive 2

naive比较慢,略

Karatsuba 1.585

对于固定长度的Karatsuba来说,由于它有几个bit的空间开销,能储存的量不如int64,略.

Toom-3 1.463

机器限制,只能用五个i64 mult拼成一个i84 mult -> i168.

设原先两个数是(A=a_2 n^2 + a_1 n + a_0)与(B=b_2 n^2+b_1 n+b_0).((0le a_2...b_0 < n))

设(f_a(n)=a_2 n^2 + a_1 n + a_0),我们称这个操作为一次^量词插值.

设(f(n)=f_a(n)f_b(n)).

(显然,此时我们可以把一个数(a)看成一个多项式(f_a),结果为多项式(f_w),次数为相乘的两个数的多项式的次数之和,那么乘法就几乎是它们的卷积).

考虑如何卷积.

我们可以对5个点插值:

[egin{align*}f(0)&= &a_0b_0 \ f(1)&= &(a_2+a_1+a_0)(b_2+b_1+b_0) \ f(-1)&= &(a_2-a_1+a_0)(b_2-b_1+b_0) \ f(2)&= &(4a_2+2a_1+a_0)(4b_2+2b_1+b_0) \ f(infty)&= &a_2b_2end{align*} ]

对于w,这个插值类似这样:

[egin{align*} && && && && w_0&=f(0) \ w_4& +& w_3& +& w_2& +& w_1& +& w_0&=f(1) \ w_4& -& w_3& +& w_2& -& w_1& +& w_0&=f(-1) \ 16w_4& +& 8w_3& +& 4w_2& +& 2w_1& +& w_0&=f(2) \ w_4&&&&&&&&&=f(infty) end{align*} ]

我们可以把这个方程解出来,那么:

[egin{align}w_0&=f(0)\ w_4&=f(4)\ w_2&=frac{f(1)+f(2)}{2}-(w_0+w_4)\ w_3&=frac{f(2)+3f(0)-3f(1)+f(-1)-12f(infty)}{6}\ w_1&=f(1)-w_0-w_2-w_3-w_4end{align} ]

这里使用了5次乘法,一次除三(O(n)),好多次加减法(O(n)),总复杂度(T(n)=5T(n/3)+O(n)=n^{log_3{5}}approx n^{1.463})