大整数乘法.ppt

算法分析题2 5 在用分治法求两个n位大整数u和v的乘积时 将u和v都分割为长度为n 3的3段 证明可以用5次n 3位整数的乘法求得uv的值 按此思想设计一个求两个大整数乘积的分治方法 并分析算法的计算复杂性 提示 n位的大整数除以一个常数k可以在 n 时间完成 符号 所隐含的常数可能依赖于k 分析 这个题目要求对大整数3等分 我们先讨论对于这个问题更一般性的解答 即将n位的大整数m等分 可以用 2m 1 次n m位的整数的乘法求得两个大整数的乘积 设x 2n m 可以将u和v及其乘积w uv表示为 U U0 U1X U2X2 Um 1Xm 1V V0 V1X V2X2 Vm 1Xm 1W UV W0 W1X W2X2 W2m 2X2m 2将U V和W都看作关于变量X的多项式 并取2m 1个不同的数x1 x2 x2m 1代入多项式可得U Xi U0 U1Xi U2Xi2 Um 1Xim 1V Xi V0 V1Xi V2Xi2 Vm 1Xim 1W Xi U Xi V Xi W0 W1Xi W2Xi2 W2m 2Xi2m 2 可以用矩阵表示为 W x1 1x1x12 x12m 2w0W x2 1x2x22 x22m 2w1 W x2m 1 1x2m 1x2m 1 x2m 12m 2w2m 2 设1x1x12 x12m 21x2x22 x22m 2 B 1x2m 1x2m 12 x2m 12m 2 则w0w x1 w1w x2 B 1 w2m 2w 2m 2 其中 多项式W xi U xi V xi 是两个n m位数的乘法运算 共有2m 1个乘法 其余均为加减法或数乘运算 解 设x 2n 3 那么U V及其乘积W UV可以表示为 U U0 U1X U2X2V V0 V1X V2X2W UV W0 W1X W2X2 W3X3 W4X4取5个数x1 x2 x5 它们的值为 x1 0 x2 1 x3 1 x4 2 x5 2代入多项式 得 a W 0 U0V0b W 1 U0 U1 U2 V0 V1 V2 c W 1 U0 U1 U2 V0 V1 V2 d W 2 U0 2U1 4U2 V0 2V1 4V2 e W 2 U0 2U1 4U2 V0 2V1 4V2 a10000W0b11111W1c 1 11 11W2d124816W3e1 24 816W4 W010000 1aW111111bW2 1 11 11cW3124816dW41 24 816e 解得W0 aW1 b c 4 d e 6a 24W2 b c 2 d e 12W3 b c 16 d e 30a 24W4 b c 8 d e 12 程序的实现流程 1 用数组获取两个 n 1 位的大整数U V 第一位为符号位 2 计算符号位 3 将U V3等分 计算出U0 U1 U2及V0 V1 V2的值 4 计算出a b c d e的值 5 计算出W0 W1 W2 W3 W4的值 6 移位 计算出乘积W的值 算法复杂度分析 按照此算法计算大整数乘积需要5次n 3位整数乘法 大整数分割 移位 加减法和数乘运算时间为O n 设T n 是算法所需的计算时间 有O 1 n 1T n 5T n 3 O n n 1 当n 1时 T n 5T n 3 O n O n 5 O n 3 5T n 32 O n 5 O n 3 5 O n 32 5T n 33 1 5 3 5 3 i cn 5i 1T n 3i 1 当3i 1 n 即i 1 3