常州网站推广软件信息,国际物流网站模板,免费咨询养生顾问,wordpress免签插件karatsuba乘法 Karatsuba乘法是一种快速乘法。此算法在1960年由Anatolii Alexeevitch Karatsuba 提出#xff0c;并于1962年得以发表。[1]此算法主要用于两个大数相乘。普通乘法的复杂度是n2#xff0c;而Karatsuba算法的复杂度仅为3nlog3≈3n1.585#xff08;log3是以2为底… karatsuba乘法 Karatsuba乘法是一种快速乘法。此算法在1960年由Anatolii Alexeevitch Karatsuba 提出并于1962年得以发表。[1]此算法主要用于两个大数相乘。普通乘法的复杂度是n2而Karatsuba算法的复杂度仅为3nlog3≈3n1.585log3是以2为底的[2]。 目录 1 算法描述 ▪ 步骤简介 ▪ 实例展示 2 效率分析 3 伪代码描述 算法描述 编辑 步骤简介 Karatsuba算法主要应用于两个大数的相乘原理是将大数分成两段后变成较小的数位然后做3次乘法并附带少量的加法操作和移位操作。 现有两个大数xy。 首先将xy分别拆开成为两部分可得x1x0y1y0。他们的关系如下 x x1 * 10m x0 y y1 * 10m y0。其中m为正整数m n且x0y0 小于 10m。 那么 xy (x1 * 10m x0)(y1 * 10m y0) z2 * 102m z1 * 10m z0其中 z2 x1 * y1 z1 x1 * y0 x0 * y1 z0 x0 * y0。 此步骤共需4次乘法但是由Karatsuba改进以后仅需要3次乘法。因为 z1 x1 * y0 x0 * y1 z1 (x1 x0) * (y1 y0) - x1 * y1 - x0 * y0 故z1 便可以由一次乘法及加减法得到。 实例展示 设x 12345y6789令m3。那么有 12345 12 * 1000 345 6789 6 * 1000 789。 下面计算 z2 12 * 6 72 z0 345 * 789 272205 z1 (12 345) * (6 789) - z2 - z0 11538。 然后我们按照移位公式xy z2 * 10 z1 * 10 z0可得 xy 72 * 10002 11538 * 1000 272205 83810205。 效率分析 编辑 对于给定的n位大数算法的复杂度不超过3nlog3 ≈ 3n1.585。 伪代码描述 编辑 1 2 3 4 5 6 7 8 9 10 11 12 13 procedurekaratsuba(num1,num2) if(num110)or(num210) returnnum1*num2 /*calculatesthesizeofthenumbers*/ mmax(size(num1),size(num2)) m2m/2 high1,low1split_at(num1,m2) high2,low2split_at(num2,m2) /*3callsmadetonumbersapproximatelyhalfthesize*/ z0karatsuba(low1,low2) z1karatsuba((low1high1),(low2high2)) z2karatsuba(high1,high2) return(z2*10^(m))(z1-z2-z0*10^(m/2))(z0) 转载于:https://www.cnblogs.com/freeopen/p/5482949.html
