3

I have recently learned Karatsuba multiplication. In order to fully understand this concept, I have attempted to write the code in Python and compared the running time against classical multiplication. Although the results are equal, the execution time of karatsuba is still the lowest, despite I am using recursive calls. What's wrong with my approach? Some helps would definitely allow me to understand more about algorithm design.

Best

JP

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)
Kleenex
  • 75
  • 1
  • 2
  • 7

2 Answers2

7

  1. Karatsuba multiplication has bigger overhead then classical binary multiplication

    the complexity is better but the overhead cause that karatsuba is faster for bigger numbers. The better is Karatsuba coded the less the treshold operands size.

  2. I see in your code that you convert number to string to get digit count

    that is very slow operation especially for big numbers use logarithms (constant binary to decadic digits ratio) and binary bit count instead. Look here for ideas on how to code Karatsuba faster (code is in C++)

  3. usage of pow

    another slow down use table of powers of 10 instead

  4. what are you comparing it to? (originally asked by Padraic Cunningham)

    Karatsuba is faster because it does operations on lower bit-count variables !!! I do not code in Phyton at all so I can missing something (like arbitrary int) but I do not see anywhere you lower the data-type with lowering the bit-count so you will be always slower !!!. Also nice will be to add example of slow multiplication you are comparing the times to like binary or radix multiplication ... (add what you use). If you use just * operator then if you are on some bigint lib then it is possible you are comparing Karatsuba with Karatsuba or even Schönhage-Strassen

  5. time measurement

    how do you measure time ? The times should be bigger then 10ms if not loop the computations N times and measure the whole thing to avoid accuracy problems. Also take in mind scheduling granularity of OS look here if you have no idea what I am writing about

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
2

Your algorithm should multiply numbers if the are < 10:

 if int(len_x) < 10 or int(len_y) < 10:

karatsuba1 is your original code. karatsuba is using if int(len_x) < 10 or int(len_y) < 10

In [17]: %timeit karatsuba1(999,999)
100000 loops, best of 3: 13.3 µs per loop

In [18]: %timeit karatsuba(999,999)
1000000 loops, best of 3: 1.77 µs per loop
Padraic Cunningham
  • 176,452
  • 29
  • 245
  • 321