Karatsuba Multiplication

This is a Non-traditional way of multiplication .But due to its better time efficiency in computer application It can use as better way of multiplication in computer program.

Note : let we have to find X*Y then Karatsuba Multiplication is applicable if and only if both X &Y have same number of digits .
Ex : x=2345  & y =4535 both have 4 digits

Algorithm for Karatsuba Multiplication :

Let x=5678 and y =1234
X and y , Both have 4 digits so Karatsuba Multiplication  is applicable  .

Now Fallow steps as shown in figure :

---

Python Code for Karatsuba Multiplication  :

1.  # Karatsuba Multiplication
2.  # Python 2.7
3.  # http://beginer2cs.blogspot.com
5. '''
6.  This Karatsuba Multiplication algorithm is only applicable if number of digit in X
7.  is equal to number of digit of Y
8. '''
9. def Karatsuba_Mult(x,y):
10.     #convert x & y to string
11.     m=str(x)
12.     n=str(y)
13.    
14.     # find length of string
15.     lm=len(m)
16.     ln=len(n)
17.     if(lm != ln):
18.         return '\n This algo is only applicable if number of digit in both x and y is same :'
19.        
20.    
21.     #find value of a,b,c,d by slice string then convert to int
22.     a=int(m[0:lm/2])
23.     b=int(m[lm/2:])
24.     c=int(n[0:ln/2])
25.     d=int(n[ln/2:])
26.    
28.     # solving expression of this algorithm and return
29.     if(lm%2 ==0): # if length is even (why this ??? think)
30.         return (10**(lm))*a*c + (10**(lm/2))*(a*d +b*c) + b*d
31.     else: # when legth of number is odd (why this ??? think)
32.         return (10**(lm+1))*a*c + (10**((lm/2)+1))*(a*d +b*c) + b*d
33.        
34.    
37. #################### MAIN ####################
38. #taking Input
39. x =int(raw_input("Enter value of X : "))
40. y =int(raw_input("Enter value of Y : "))
41. #Print result
42. print 'X*Y using Karatsuba Multiplication :- ',Karatsuba_Mult(x,y)
43. 
    

---

Output Demo: