## Friday, 27 June 2014

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

Output Demo:

1. Hi there, its fastidious post on the topic of media print, we all be familiar with media is a wonderful source of facts.

Also visit my web site; attorney car accidents

2. I really appreciate information shared above. It’s of great help. If someone want to learn Online (Virtual) instructor lead live training in Data Science with Python , kindly contact us http://www.maxmunus.com/contact
MaxMunus Offer World Class Virtual Instructor led training on TECHNOLOGY. We have industry expert trainer. We provide Training Material and Software Support. MaxMunus has successfully conducted 100000+ trainings in India, USA, UK, Australlia, Switzerland, Qatar, Saudi Arabia, Bangladesh, Bahrain and UAE etc.