Integer multiplication in 5T(n/3)

2019-08-29 10:48发布

x and y has n bits

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

now 9 multiplication of n/3 bit numbers running time 9T(n/3) which is O(n^2)

with little trick like Karatsuba's multiplication

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 Recursively solve the 6 subproblems and combine them with 7 additions on O(n)-digit numbers. total it takes now 6 multiplication of of n/3 bit numbers running time 6T(n/3)

how can I reduce this to 5 multiplication instead of 6 ?

0条回答
登录 后发表回答