algorithm - 乘以多项式

Question

• 展示如何仅使用三个乘法将两个线性多项式 $ax+b$ 和 $cx+d$ 相乘。

• 给出一个分而治之的算法，用于乘以时间为 Θ(n^(lg3) 的度界 n 的两个多项式。该算法应将输入多项式系数分为高半部分和低半部分一半。

• (ax+b)(cx+d)=ac x^2+((a+b)(c+d)-ac-bd)x+bd

• 我们设 p 和 q 分别为第一和第二多项式 P 和 Q 的系数向量。

  我们假设这两个向量的长度都是 n=max{ length(P), length(Q)} 并且我们让 m=ceil(n/2)。

  则P=A x^m+B，其中A=p_m+p_(m+1) x+ .... + p_(n-1) x^(n-1-m), B=p_0+ p_1 x+ ...s+p_(m-1)x^(m-1) 和 Q=Cx^m+D，其中 C=q_m+q_(m+1) x+ ...+ q_(n-1 ) x^(n-1-m) 和 D=q_0+q_1 x+ ... + q_(n-1) x^(n-1)=q_0+q_1 x+ ... + q_(m-1) x ^(m-1).

利用前面的结果，它认为 (Ax^m+B)(Cx^m+D)=AC x^(2m)+((A+B)(C+D)-AC-BD) x ^m+BD (1)$.

我找到了以下算法 ( link )

Algorithm(p,q){
   n=size(p)
   m=ceil(n/2)
   if n==1 return p*q
   else{
         a=p[m,n-1]
         b=p[0,m-1]
         c=q[m,n-1]
         d=q[0,m-1]
         tmp1=Algorithm(a+b,c+d)
         tmp2=Algorithm(a,c)
         tmp3=Algorithm(b,d)
   return tmp2<<n+(tmp1-tmp2-tmp3)<<m+tmp3

所以我们假设 a,b,c,d 是向量，对吗？

你能解释一下为什么我们要进行这些递归调用吗:

 tmp1=Algorithm(a+b,c+d)
 tmp2=Algorithm(a,c)
 tmp3=Algorithm(b,d)

我还没有真正理解它......另外，我们怎么能将数字向左移动特定位数呢？

Answer 1

假设您有两个最大次数为 n 的多项式，并且您想要找到它们的乘积的多项式。此外，您想使用分而治之的方法来优化您的解决方案。

我们如何将两个 n 次多项式相乘的问题分解为涉及较少工作量的类似子问题？好吧，我们可以把它们变成更多的更小的多项式。给定一个 n 次多项式，您可以按照以下推理将它变成两个更小的多项式。

给定一个 n 次多项式 P，如下所示:

让:

我们可以从多项式的“后半部分”中分解出 x^m。或者，继续我们的符号:

或者，如果我们让:

我们有:

我们已经设法用 两个 个更小的 m 次多项式来表达我们的 n 次多项式。为什么这有用？

好吧，让我们暂时回到最初的问题。回想一下，我们有两个多项式来求乘积，让我们按照上面的方式拆分它们。令 A、B 表示第一个多项式 P 的第一和第二“一半”，令 C、D 表示第二个多项式 Q 的两个一半。*

重新排列 P 和 Q 的乘积:

太棒了!我们已经设法将两个大多项式的乘积表示为三个较小的……嗯……多项式的乘积之和。那不是很好，是吗？因此，当您想要计算 AC、BD 或 (A+C)(B+D) 时，您会遇到与开始时相同的问题:“取这两个多项式并将它们相乘”。

但这正是我们要解决的问题!假设我们的方法正确实现以返回两个多项式的乘积(的系数向量)，我们可以将需要计算的三个乘积传递给它。这就是为什么您对 Algorithm 进行了三次递归调用，分别针对 A、C、B、D 和 A+B， C+D.

最后，关于左移:我相当确定这是指在系数向量内向左移动，而不是按位左移。由于系数向量中的索引表示系数适用的项的 x 次方，我们可以通过将其系数向量中的项向左移动相应的量来表示某些多项式乘以给定的 x 次方。

*请注意，两个多项式被视为具有完全相同的次数，即 P 和 Q 中高阶多项式的次数。其他多项式中所有缺失项的系数均为零。