首页 文章

乘法多项式

提问于
浏览 次
0

  • 显示如何仅使用三次乘法将两个线性多项式$ 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)

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

algorithm multiplication polynomial-math

2 回答

  • 3

    假设您有两个最大度为n的多项式，并且您希望找到作为其乘积的多项式 . 此外，您希望使用分而治之的方法来优化您的解决方案 .

    我们如何打破将n次多项式乘以类似的子问题的问题呢？好吧，我们可以把它们变成更多的更小的多项式 . 给定n次多项式，可以按照下面的推理将其转换为两个较小的多项式 .

    给定n次多项式P如下：

    enter image description here

    让：

    enter image description here

    我们可以从多项式的“后半部分”中分解x ^ m . 或者，继续我们的表示法：

    enter image description here

    或者，如果我们让：

    enter image description here

    enter image description here

    我们有：

    enter image description here

    我们已经设法用两个较小的多项式来表达n次多项式，其次数为m . 为什么这有用？

    好吧，让我们回到原来的问题一秒钟 . 回顾我们给出了两个多项式来找到它们的乘积，让我们如上所述拆分它们 . 设A，B表示第一多项式P的第一和第二“半”，并且让C，D表示第二多项式Q的两半 . *

    重新排列P和Q的乘积：

    enter image description here

    真棒！我们设法将两个大多项式的乘积表示为三个较小......井...多项式的乘积之和 . 这不是那么好，是吗 . 因此，当你想要计算AC，BD或（A C）（B D）时，你会遇到同样的问题：“取这两个多项式并乘以它们” .

    但这是我们正在解决的问题！假设我们的方法被正确地实现以返回两个多项式的乘积（系数向量），我们可以将它们传递给我们需要计算的三个产品 . 这就是为 A, C ， B, D 和 A+B, C+D 分别对 Algorithm 进行三次递归调用的原因 .

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

    *注意，在P和Q中，两个多项式都被视为具有完全相同的度数，即高阶多项式的次数 . 另一个多项式中的所有缺失项具有系数零 .

    回复于
  • 0

    递归调用用于多项式乘法，必须在计算 AC 等时进行，以便计算公式 AC x^n ，其中 AC 是多项式 . （如果需要，你应该考虑用更大的偶数替换 n ，在这种情况下，多项式的前导系数可能是 0 . 然后你总是有 n=2m . ）只需用二次多项式的乘积来遍历它;这应该是显而易见的 .

    至于移位运算符，它是伪代码，所以在解释上有一定的自由度 . 对于多项式，移位运算符 << n 表示乘以 x^n ，这也对应于左移位系数向量 .

    这里使用移位运算符的原因是因为真正有趣的部分是我们在整数乘法的上下文中解释它 . 我们可以将整数表示为多项式;例如， 6 = 1 * 2^2 + 1 * 2^1 + 0 * 2^0 ，对应于对应 x=2 下的多项式 1 * x^2 + 1 * x^1 + 0 * x^0 . 然后整数乘法对应于多项式乘法（但是对于进位），乘以 x 对应于乘以 2 ，其对应于左移 . （我们不会在整数加法的上下文中由 + 运算符处理 . ）

    回复于

相关问题