两个数字的在6 N / 3比特的6T乘法（N / 3）Karatsuba的 [英] multiplication of two numbers in 6 of n/3 bits 6T(n/3) karatsuba

问题描述

两个数的乘法

x*y ----> x =(x0*10^(n/3)+x1*10^(n/3)+x2) and y=(y0*10^(n/3)+y1*10^(n/3)+y2)

有乘法9 10 ^ N / 3号，以便9T（N / 3），但它可以通过以下的方法减少到5。

It is 9 multiplication of 10^n/3 numbers so 9T(n/3) but it can be reduced to 5 by the following method.

x*y= x0*y0+x1*y1+x2*y2+x0*y1+x0*y2+x1*y0+x1*y3+x2*y0+x2*y1

我可以通过类似的技巧，以减少两个数字的乘法5T（N / 3）像Karatsuba的算法

I am able to reduce the multiplication of two numbers to 5T(n/3) by similar trick like Karatsuba's algorithm

(x0+x1+x2)(y0+y1+y2)-x0*y0-x1*y1-x2*y2= x0*y1+x0*y2+x1*y0+x1*y3+x2*y0+x2*y1

总括5乘N / 3位号码，以便 5T（N / 3）+ O（N），但我该怎么办在6乘象 6T（N / 3）+ O（N）

All and all 5 multiplication of n/3 bits number so 5T(n/3)+O(n) but how can I do in 6 multiplication like 6T(n/3)+O(n)

Q1就可以被减少到6个，而不是5？

修正通过Spektre从老师又问道的问题复制

[edit1] correction copied from the reasked question by Spektre

x和y有n位

x=x0*(10^2n/3)+x1*10^n/3+x2
y=y0*(10^2n/3)+y1*10^n/3+y2
x*y=x2y2+(x2y1+x1y2)10^n/3+(x2y0+x1y1+x0y2)10^2n/3+(x1y0+x0y1)10^n+x0y0*10^4n/3

• 现在，9乘法运行时间9T N / 3位数的（N / 3），这是O（n ^ 2）

用小动作像Karatsuba的的乘法：

with little trick like Karatsuba's multiplication:

• 先计算x0y0，X1Y1和X2Y2这是3乘N / 3位数的
• 然后用x0y0，X1Y1和X2Y2计算出别人遵守：
• X2Y1 + X1Y2 =（X1 + X2）（Y1 + Y2）-x1y1-X2Y2 - >> 1乘N / 3位数
• X2Y1 + X1Y1 + x0y2 =（X0 +​​ X2）（Y0 + Y2）-x0y0-X2Y2 + X1Y1 - >> 1乘N / 3位数
• x1y0 + x0y1 =（X0 +​​ X1）（Y0 + Y1）-x0y0-X1Y1 - >> 1乘N / 3位数
• first calculate x0y0, x1y1 and x2y2 this is 3 multiplication of n/3 bit numbers
• then use x0y0, x1y1 and x2y2 to calculate the others follow:
• x2y1+x1y2=(x1+x2)(y1+y2)-x1y1-x2y2 ->> 1 multiplication of n/3 bit number
• x2y1+x1y1+x0y2=(x0+x2)(y0+y2)-x0y0-x2y2+x1y1 ->> 1 multiplication of n/3 bit number
• x1y0+x0y1=(x0+x1)(y0+y1)-x0y0-x1y1 ->> 1 multiplication of n/3 bit number

递归解决了6子问题

• ，并结合他们增加7对为O（n​​）位数字号码。
• 总花费现在6倍增运行时间6T N / 3位数的（N / 3）

Q2我怎样才能减少到5乘法，而不是6？

• Q1现在已经过时了，由于错误的OP

推荐答案

不是一个答案，但是这将是不可读的评论

Not an answer but this would be unreadable as comment

如果你把数字3组，然后点击樽是对

if you divide digits to 3 groups then greybeard is right

a0=10^(2n/3)
a1=10^(1n/3)
a2=10^(0n/3)
x=x0*a0+x1*a1+x2*a2
y=y0*a0+y1*a1+y2*a2

所以乘看起来像这样：

so multiplication looks like this instead:

x*y=a0(x2*y2+x1*y2+x0*y2)
    +a1(x2*y1+x1*y1+x0*y1)
    +a2(x2*y0+x1*y0+x0*y0)

重写数字：

b0=(x2*y2+x1*y2+x0*y2)
b1=(x2*y1+x1*y1+x0*y1)
b2=(x2*y0+x1*y0+x0*y0)
x*y=a0*b0+a1*b1+a2*b2

现在简化 B0，B1，B2

[提示]

• 你利用？有什么绝招
• 为什么在结果没有数字重量 A0，A1，A2 ？

如果要解决这个问题，然后使用，而不是你的标准符号

低显著的数字要低指数这样：

lower significant digits are lower index so:

a0=10^(0n/3)
a1=10^(1n/3)
a2=10^(2n/3) // this is max wieght for operand
a3=10^(3n/3)
a4=10^(4n/3)
a5=10^(5n/3) // this is max weight for multiplication result
x=x0*a0+x1*a1+x2*a2
y=y0*a0+y1*a1+y2*a2

所以乘看起来像这样：

so multiplication looks like this instead:

x*y=a0(x0*y0+x1*y0+x2*y0)
    +a1(x0*y1+x1*y1+x2*y1)
    +a2(x0*y2+x1*y2+x2*y2)

重写数字：

b0=(x0*y0+x1*y0+x2*y0)
b1=(x0*y1+x1*y1+x2*y1)
b2=(x0*y2+x1*y2+x2*y2)
x*y=a0*b0+a1*b1+a2*b2

粗B0，B1，B2的不在单一的数字的范围 - 相反，他们都是两位数由于乘法

of coarse b0,b1,b2 are not in range of single digit - instead they are all double digit due to multiplication

所以你必须将它们拆分成单数的数字：

so you have to split them into singular digits:

x*y=a0*B0+a1*B1+a2*B2+a3*B3+a4*B4+a5*B5

其中：

B0=(b0/a0)%a1
B1=(b0/a1+b1/a0)%a1
B2=(b0/a2+b1/a1+b2)%a1
B3=(b0/a3+b1/a2+b2/a1)%a1
B4=(b0/a4+b1/a3+b2/a2)%a1
B5=(b0/a5+b1/a4+b2/a3)%a1

• ，也不要忘了处理溢出...

这篇关于两个数字的在6 N / 3比特的6T乘法（N / 3）Karatsuba的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！