快速的 Karatsuba 乘法

Question

我试图在 swift 中实现 Karatsuba 乘法。我写了下面的代码，它对一些较小的数字工作正常，但随着数字变大，这段代码无法给出正确的答案。我已经尽我所能进行调试，但找不到错误。在算法方面，我认为我确实正确地编写了代码。并且代码对于较小的数字工作正常。但是对于更大的数字，最终的答案是错误的。如果有人能纠正我犯的错误，请帮助我

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

这里有一个实现：
https://victorqi.gitbooks.io/swift-algorithm/content/karatsuba-multiplication.html
他们的代码是：

// 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
}

出于好奇，我问了 ChatGPT。它的实现：

func karatsubaMultiplication(_ x: Int, _ y: Int) -> Int {
    
    // base case for single-digit multiplication
    if x < 10 || y < 10 {
        return x * y
    }
    
    // determine the number of digits in each input number
    let n = max(String(x).count, String(y).count)
    let n2 = n / 2
    
    // split the input numbers into high and low digits
    let high1 = x / Int(pow(10, Double(n2)))
    let low1 = x % Int(pow(10, Double(n2)))
    let high2 = y / Int(pow(10, Double(n2)))
    let low2 = y % Int(pow(10, Double(n2)))
    
    // recursively compute the three sub-products
    let z0 = karatsubaMultiplication(low1, low2)
    let z1 = karatsubaMultiplication((low1 + high1), (low2 + high2))
    let z2 = karatsubaMultiplication(high1, high2)
    
    // compute the final result using the Karatsuba formula
    return z2 * Int(pow(10, Double(n2 * 2))) + ((z1 - z2 - z0) * Int(pow(10, Double(n2)))) + z0
}

用 2 个整数参数调用它：

let result = karatsubaMultiplication(12345, 6789)
print(result) // prints 83810205