1

I am implementing karatsuba multiplication.In my assignment, I have to calculate the multiplication of 2 64 digit numbers.

but while implementing it I am getting the error-

RecursionError: maximum recursion depth exceeded while calling a Python object

So my question is is the error due to my laptops limitation or is karatsuba not applicable for such large numbers?

My code is-

def karatsuba(num1,num2):

    if (len(str(num1))==1 and len(str(num2))==1):
        return num1*num2

    else:
        print(num1,num2)
        a,b=int(str(num1)[:len(str(num1))//2]),int(str(num1)[len(str(num1))//2:])
        c,d=int(str(num2)[:len(str(num2))//2]),int(str(num2)[len(str(num2))//2:])
        #print(a,b,c,d)


        res1=karatsuba(a,c)
        res2=karatsuba(b,d)
        res3=karatsuba(a+b,c+d)
        res4=res3-res2-res1
        #print(res1,res2,res4)

        n=max(len(str(num1)),len(str(num2)))
        #print(n)
        final_result=math.pow(10,n)*res1+math.pow(10,n/2)*res4+res2
    return final_result

edit-The code works for small numbers but for large numbers it gives the error-

ValueError: invalid literal for int() with base 10: ''
ubuntu_noob
  • 2,305
  • 6
  • 23
  • 64
  • 3
    If your arguments `num1` and `num2` are floats, their string representation will never have length 1. For example, `str(float(1))` is `1.0` rather than `1`. This is why your code always enters the `else` clause and always starts more recursive calls. – Mikhail Burshteyn Sep 15 '18 at 16:49
  • @MikhailBurshteyn if I dont do that I get ValueError: invalid literal for int() with base 10: '' – ubuntu_noob Sep 15 '18 at 16:59
  • you are using `pow` which is floating point and also way more complex than multiplication and will always pose a treat of rounding errors. Why when you can do stuff directly on strings without any transform to number and back ... the pow in your case just adds zeros to the string ... – Spektre Sep 15 '18 at 19:50
  • @Spektre i also used 10**n but still for numbers greater than 2 digits the answer is close but not exact..can you tell why? – ubuntu_noob Sep 15 '18 at 19:56
  • @ubuntu_noob Becuase you are computing karatsuba multiplication by higher math operations (which btw also involves multiplication) and also because you limit the results and sub-results to variable datatype limits as you convert between `string/float/int`. There are two approaches either compute all on strings only (easy) or do it on array of unsigned ints instead (fast) but then you need to implement the low level operations on it. I do not code in python but here C++ example of this and more: [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214) – Spektre Sep 15 '18 at 21:26

0 Answers0