getting no result but stuck in infinite loop in karatsuba algorithm-CodePudding

I am not getting any result my program stuck in infinite loop. I made a program for four values with same logic which worked great but with three values this is not working

def Karatsuba_Recursive(a, b):
    if not a or not b:
        return "0"
    if len(a) == 1 or len(b) == 1:
        return str(int(a)*int(b))
    else:
        m = max(len(a),len(b))
        m2 = m // 2
        A = a[0:-m2]
        B = a[-m2:len(a)].lstrip("0")
        C = b[0:-m2]
        D = b[-m2:len(b)].lstrip("0")
        val1 = int(Karatsuba_Recursive(A,C))
        val2 = int(Karatsuba_Recursive(B,D))
        val3 = int(Karatsuba_Recursive((str(A B)),str((C D))))
        return str((val1 * (10 **(2*m2)))   ((val3 - val1 - val2) * (10**(m2)))   val2)

CodePudding user response：

The main issue is that A B is a string concatenation, not numeric addition. This should be int(A) int(B). Same for C D.

It is unfortunate that you select m to be max(len(a),len(b)) as that makes it necessary to have that first if not a or not b test, and you would also need to adapt the above fix to work with empty strings.

You can avoid all that by taking min(len(a),len(b)) for m instead.