Multiply strings-Leetcode using Karatsuba algorithm with Python

Question

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself. You must not use any built-in BigInteger library or convert the inputs to integer directly.

There are many different approaches to this problem .One of them is by using Karatsuba algorithm .

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        if len(num1)==1 or len(num2)==1:
            return str(int(num1)*int(num2))
        m=max(len(num1),len(num2))
        m2=m//2   

        num1=int(num1)
        num2=int(num2)
        a=num1//10**m2
        b=num1%10**m2
        c=num2//10**m2
        d=num2%10**m2
        
        z0=self.multiply(str(b),str(c))
        z1=self.multiply(str(a+b),str(c+d))-a*c-b*d
        z2=self.multiply(str(a), str(c))
        
        return (z2 * 10**(2*m2)) + ((z1 - z2 - z0) * 10**(m2)) + (z0)

The Pseudocode applied is correct as but the code is suffering due to repetitive conversion between strings and integer .What can I do to improve upon this ? And is this the correct approach for this problem ? Thanks in advance

Here is the reference link which helped me-https://pythonandr.com/2015/10/13/karatsuba-multiplication-algorithm-python-code/

All you're supposed to do is implement grade school multiplication. Also, *"you must not [...] convert the inputs to integer directly"* means that you aren't allowed to do this: `num1 = int(num1)` — user3386109, Jun 23 '20 at 05:37
@ user3386109 but then it gives me the error -string division is not valid .What am I supposed to do ? — kirti purohit, Jun 23 '20 at 06:00
You can convert the strings to lists of digits, e.g. `num1 = "123"` `digits = [int(n) for n in num1]` `print digits` — user3386109, Jun 23 '20 at 06:17
I do not code in python but from mine point of view the code is wrong as it converts your string s to numbers. That is either using bigints internaly or overflow used datatype depending on used lenvironment. The first one contradicts the assignment and the latter corrupts the result. You need to do all the math operations on strings instead. So you need to implement basic math operations like `+,-,*=10,/=10,...` on strings. And then build on that. However there are other alternatives to karatsuba see [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214) — Spektre, Jun 23 '20 at 07:55

score 0 · Accepted Answer · edited Jul 03 '20 at 08:43

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        def mul(num1, num2):
            if len(num1) == 1 or len(num2) == 1:
                return int(num1) * int(num2)
            m = min(len(num1), len(num2)) // 2
            a, b = num1[:len(num1) - m], num1[len(num1) - m:]
            c, d = num2[:len(num2) - m], num2[len(num2) - m:]
            z0 = mul(b, d)
            z2 = mul(a, c)
            z1 = mul(str(int(a) + int(b)), str(int(c) + int(d))) - z2 - z0
            return (10 ** (2 * m)) * z2 + (10 ** m) * z1 + z0

        return str(mul(num1, num2))

Originally I was the person who asked the same question, later when I figured it out I'm posting the solution.

Multiply strings-Leetcode using Karatsuba algorithm with Python

The length of both num1 and num2 is < 110. Both num1 and num2 contain only digits 0-9. Both num1 and num2 do not contain any leading zero, except the number 0 itself. You must not use any built-in BigInteger library or convert the inputs to integer directly.

1 Answers1