Addition of big integer Multiplication of big integers n Can you ever do a plus for big integers? ■A=a123+a a can you do a plus for small integers which is ■B=b12325+b 32-bits or less? a Where r=A length/2, s=B length/2, hence th a How to divide the big integers summation to a size of a1. a2 are half size of a it is similar fo series of small integers summations? B, b, b2 a How to combine it together? ■AB=a1b1232++b1a2325+a1b223+a2b2 a How many steps do you use in your algorithm? Complexity analysis The above performance can be obtained by a directed method IT(n, m)the steps used for multiplication of a a Can you give a naIve algorithm for 32n-bits and 32m-bits integers multiplication of big integers? I T(n, m)=4T(n/2, m/2)+e(m+n) ■Letn= m then ■T(n)=4T(n/2)+e) ■T(n)=e(n2) An improved algorithm We need only 3 multiplications ■A=a123+a2 ■U=a1b1 ■B=b1232+b2 I Let n=A length= B length and r=n/2, (b1a2+a1b2)=(a1+a2)(b1+b2)uv m AB=a, b,264+(b, a2 +a, b2)232+a2 b2 a We needs only 3 multiplications to get: a We can converge the multiplication to 4 smaller integers multiplications and 3 a,b,,a2 b2,(b,a2 +a, b2) summations ■ Can we do better? 身手武学城制8 清华大学 宋斌恒 43 Addition of big integer n Can you ever do a plus for big integers? n can you do a plus for small integers which is 32-bits or less? n How to divide the big integers summation to a series of small integers summations? n How to combine it together? n How many steps do you use in your algorithm? 清华大学 宋斌恒 44 Multiplication of big integers n A=a1 232r + a2 n B=b1 232s + b2 n Where r=A.length/2, s=B.length/2, hence the size of a1, a2 are half size of A, it is similar for B, b1 , b2 n AB=a1 b1 232(s+r) +b1 a2 232s +a1 b2 232r +a2 b2 n Converge the multiplication to 4 smaller integers multiplications and summations 清华大学 宋斌恒 45 Complexity analysis n T(n,m)----the steps used for multiplication of a 32n-bits and 32m -bits integers n T(n,m)=4T(n/2,m/2)+Q(m+n) n Result? n Let n=m then n T(n)=4T(n/2)+Q(n) n T(n)= Q( n2 ) 清华大学 宋斌恒 46 The above performance can be obtained by a directed method n Can you give a naïve algorithm for multiplication of big integers? 清华大学 宋斌恒 47 An improved algorithm n A=a1 232r + a2 n B=b1 232r + b2 n Let n=A.length= B.length and r=n/2, n AB=a1 b1 264r +(b1 a2 +a1 b2 ) 232r +a2 b2 n We can converge the multiplication to 4 smaller integers multiplications and 3 summations n Can we do better? 清华大学 宋斌恒 48 We need only 3 multiplications! n u= a1 b1 n v= a2 b2 n (b1 a2 +a1 b2 ) =(a1 + a2 ) (b1 + b2 )-u-v n We needs only 3 multiplications to get: n a1 b1 , a2 b2 , (b1 a2 +a1 b2 )