0

我试图快速实现 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
}
4

0 回答 0