Please do both parts for good feedback and full credit. Using python code post c
ID: 3788519 • Letter: P
Question
Please do both parts for good feedback and full credit. Using python code post code and show its working and functional
Exercise: Karatsuba Algorithm Problem statement: In this exercise, you will need to implement 2 different pieces Part 1 Big Integer Addition/Subtraction consists of three lines. In the first line, comes the digits of integer a, separated by space and most significant digit first. In the second line, comes b in the same format. Finally in the third line, comes a character, which is or The output of your program should consist of only one line, listing all the digits of the answer following the same format as input integers. The input is prepared in such a way that the result of subtraction is never negative Part 2: Karatsuba Algorithm In this part, you are reading two integers a and b from the input, and printing the result of a multiplied by b using Karatsuba algorithm. You can (need to) use the function you developed in the first part, as a part of your solution to the second part The input consists of only two lines. First line contains number a and second line contains number b, following the same format of previous part. The output is again only one line, containing the result of multiplication. Note that, the number of digits in the input numbers are at least 1 and at most 10,000 (10A4). Part 1 Input Sample: 948 84 (948 and 84 are the two values you need to add/subtract. The third argument lets you know the operation.)Explanation / Answer
#Python code for given problem statement both parts are implemented.
import sys
def karatsuba(x,y):
"""Function to multiply 2 numbers in a more efficient manner than the grade school algorithm"""
if len(str(x)) == 1 or len(str(y)) == 1:
return x*y
else:
n = max(len(str(x)),len(str(y)))
nby2 = n / 2
a = x / 10**(nby2)
b = x % 10**(nby2)
c = y / 10**(nby2)
d = y % 10**(nby2)
ac = karatsuba(a,c)
bd = karatsuba(b,d)
ad_plus_bc = karatsuba(a+b,c+d) - ac - bd
# this little trick, writing n as 2*nby2 takes care of both even and odd n
prod = ac * 10**(2*nby2) + (ad_plus_bc * 10**nby2) + bd
return prod
print "Enter two numbers and operation to perform on third line "
number_a=input()
number_b=input()
c=raw_input()
if(c=='+'):
print number_a+number_b
elif(c=='-'):
print abs(number_a-number_b)
else:
print karatsuba(number_a,number_b)
Output:
G580:$ python karatsuba.py
Enter two numbers
23
4
-
19
G580:$ python karatsuba.py
Enter two numbers
2
3123
-
3121
G580:$ python karatsuba.py
Enter two numbers
3123
123
384129