#C1.txt: Jan. 23, 2014. How to multiply two integers Help:=proc(): print(` M(a,b), K(a,b) `): end: M:=proc(a,b) local d,a1,a2,b1,b2: if a<10 and b<10 then RETURN(a*b): fi: #If a had 2d digits, let's write as a=10^d*a1+a2 and ditto for b #where a1 and a2 have d digits d:=log[10](max(a,b)): if type(d,integer) then d:=d+1: else d:=ceil(d): fi: if d mod 2=1 then d:=(d+1)/2: else d:=d/2: fi: a2:=a mod 10^d: b2:=b mod 10^d: a1:=(a-a2)/10^d: b1:= (b-b2)/10^d: # a*b=(10^d*a1 +a2)* (10^d*b1+b2)= #(10^d)^2*a1*b1+10^d*a1*b2+a2*10^d*b1+a2*b2 M(a1,b1)*100^d+ ( M(a1,b2)+M(a2,b1))*10^d + M(a2,b2): end: #Karatsuba's version K:=proc(a,b) local d,a1,a2,b1,b2: option remember: if a<10 and b<10 then RETURN(a*b): fi: #If a had 2d digits, let's write as a=10^d*a1+a2 and ditto for b #where a1 and a2 have d digits d:=log[10](max(a,b)): if type(d,integer) then d:=d+1: else d:=ceil(d): fi: if d mod 2=1 then d:=(d+1)/2: else d:=d/2: fi: a2:=a mod 10^d: b2:=b mod 10^d: a1:=(a-a2)/10^d: b1:= (b-b2)/10^d: # a*b=(10^d*a1 +a2)* (10^d*b1+b2)= #(10^d)^2*a1*b1+10^d*a1*b2+a2*10^d*b1+a2*b2 #(10^d)^2*a1*b1+10^d*(a1*b2+a2*b1)+a2*b2 #a1*b2+a2*b2=(a1+a2)*(b1+b2)-a1*b1-a2*b2: K(a1,b1)*100^d+ (K(a1+a2,b1+b2)- K(a1,b1)-K(a2,b2))*10^d + K(a2,b2): end: