Karatsuba multiplication in swift

Question

I was trying to implement Karatsuba multiplication in swift. I wrote the below code and it is working fine for some smaller numbers but as the number gets bigger this code fails to give the correct answer. I have debugged in every possible way I can but could not find the bug. Algorithm wise I think I did correctly write the code. And the code is working fine for smaller numbers. But the final answer is wrong for bigger numbers. If anyone out there can crack down the mistake I'm making, pls do help me

func findMultiplication(x: String, y: String) -> String {
    
    if isZero(str: x) || isZero(str: y) {
        return "0"
    }
    var x = removeLeadingZeros(number: x)
    var y = removeLeadingZeros(number: y)
    if x.count < 2 || y.count < 2 {
        let result = Int(x)!*Int(y)!
        return String(result)
    }
    
    var middleIndexX: String.Index
    var middleIndexY: String.Index
    var middleIndex: Int
    
    if x.count >= y.count {
        y = addLeftPaddingZeros(numberOfZeros: x.count-y.count, for: y)
        middleIndex = x.count / 2
        if x.count % 2 != 0 {
            middleIndex += 1
        }
    } else {
        x = addLeftPaddingZeros(numberOfZeros: y.count-x.count, for: x)
        middleIndex = y.count / 2
        if y.count % 2 != 0 {
            middleIndex += 1
        }
    }
    middleIndexX = x.index(x.startIndex, offsetBy: middleIndex)
    middleIndexY = y.index(y.startIndex, offsetBy: middleIndex)
    
    let a = String(x[x.startIndex..<middleIndexX])
    let b = String(x[middleIndexX..<x.endIndex])
    let c = String(y[y.startIndex..<middleIndexY])
    let d = String(y[middleIndexY..<y.endIndex])
    
    let ac = findMultiplication(x: a, y: c)
    let bd = findMultiplication(x: b, y: d)
    let aPb = Int(a)! + Int(b)!
    let cPd = Int(c)! + Int(d)!
    let gauss = findMultiplication(x: String(aPb), y: String(cPd))
    let thirdItem = String(Int(gauss)! - Int(ac)! - Int(bd)!)
    
    var returnSum = 0
    returnSum += Int(addLeftPaddingZeros(numberOfZeros: x.count, for: ac, isLeft: false)) ?? 0
    returnSum += Int(addLeftPaddingZeros(numberOfZeros: middleIndex, for: thirdItem, isLeft: false)) ?? 0
    returnSum += Int(bd) ?? 0
    return String(returnSum)
}

print(findMultiplication(x: "123400", y: "123711"))

func removeLeadingZeros(number: String) -> String {
    var number = number
    while number.first == "0" {
        number.removeFirst()
    }
    if number == "" {
        return "0"
    }
    return number
}

//The function name is given like this only. BUt his will help to add padding zero in left and right also

func addLeftPaddingZeros(numberOfZeros: Int, for str: String, isLeft: Bool = true) -> String {
    var padding = ""
    for _ in 0 ..< numberOfZeros {
        padding += "0"
    }
    if isLeft {
        return padding+str
    } else {
        return str + padding
    }
    
}

func isZero(str: String) -> Bool {
    for char in str {
        if char != "0" {
            return false
        }
    }
    return true
}

Answer 1

There's an implementation here:
https://victorqi.gitbooks.io/swift-algorithm/content/karatsuba-multiplication.html
Their code reads:

// Karatsuba Multiplication
func karatsuba(_ num1: Int, by num2: Int) -> Int {
  let num1Array = String(num1).characters
  let num2Array = String(num2).characters

  guard num1Array.count > 1 && num2Array.count > 1 else {
    return num1*num2
  }

  let n = max(num1Array.count, num2Array.count)
  let nBy2 = n / 2

  let a = num1 / 10^^nBy2
  let b = num1 % 10^^nBy2
  let c = num2 / 10^^nBy2
  let d = num2 % 10^^nBy2

  let ac = karatsuba(a, by: c)
  let bd = karatsuba(b, by: d)
  let adPlusbc = karatsuba(a+b, by: c+d) - ac - bd

  let product = ac * 10^^(2 * nBy2) + adPlusbc * 10^^nBy2 + bd

  return product
}