小编Jea*_*ehl的帖子

我最近学会了Karatsuba乘法.为了完全理解这个概念,我试图用Python编写代码,并将运行时间与经典乘法进行比较.虽然结果是相同的,但karatsuba的执行时间仍然是最低的,尽管我使用的是递归调用.我的做法有什么问题？一些帮助肯定会让我更多地了解算法设计.

最好

J.P

print('Karatsuba multiplication in Python')
x=raw_input("first_number=")
y=raw_input("second_number=")
print('------------------------')
x=int(x)
y=int(y)
import math
import time
def karatsuba(x,y):

  x=str(x)
  y=str(y)

  len_x=len(x)
  len_y=len(y)

  if(int(len_x)==1 or int(len_y)==1):    
    return int(x)*int(y)
  else:

    B=10
    exp1=int(math.ceil(len_x/2.0))
    exp2=int(math.ceil(len_y/2.0))
    if(exp1<exp2):
      exp=exp1
    else:
      exp=exp2
    m1=len_x-exp
    m2=len_y-exp
    a=karatsuba(int(x[0:m1]),int(y[0:m2]))
    c=karatsuba(int(x[m1:len_x]),int(y[m2:len_y]))
    b=karatsuba(int(x[0:m1])+int(x[m1:len_x]),int(y[0:m2])+int(y[m2:len_y]))-a-c
    results=a*math.pow(10,2*exp) + b*math.pow(10,exp) + c
    return int(results)

start_time=time.time()
ctrl = x*y
tpt=time.time() - start_time
print x,'*',y,'=',ctrl
print("--- %s seconds ---" % tpt)

start_time=time.time()
output=karatsuba(x,y)
tpt=time.time() - start_time
print 'karatsuba(',x,',',y,')=',output
print("--- %s seconds ---" % tpt)