如何处理 swift 中长整数的答案

Question

我必须计算 swift 中两个长整数的幂。 Swift 给出了 NaN 的错误（不是数字），无法回答。

例如

pow(2907,1177)

计算幂取余数的主进程id(a^b % n) where a= 2907, b= 1177, n= 1211

有什么解决方法的指南吗？

Answer 1

您将不得不使用 1. 外部框架或 2. 自己动手。

1.外部框架：

我想你可以试试：https://github.com/mkrd/Swift-Big-Integer

let a = BInt(2907)
let b = 1177
let n = BInt(1211)

let result = (a ** b) % n

print(result) // prints 331

注意：Cocoapods 导入失败所以我只导入了这个文件让它工作：https://github.com/mkrd/Swift-Big-Integer/tree/master/Sources

2。 DIY: 使用 Modulus power of big numbers

的答案

func powerMod(base: Int, exponent: Int, modulus: Int) -> Int {
    guard base > 0 && exponent >= 0 && modulus > 0
        else { return -1 }

    var base = base
    var exponent = exponent
    var result = 1

    while exponent > 0 {
        if exponent % 2 == 1 {
            result = (result * base) % modulus
        }
        base = (base * base) % modulus
        exponent = exponent / 2
    }

    return result
}

let result = powerMod(base: 2907, exponent: 1177, modulus: 1211)

print(result) // prints 331

3。奖励：使用与 2 相同的方法。但由于 http://natecook.com/blog/2014/10/ternary-operators-in-swift/

而使用自定义三元运算符

precedencegroup ModularityLeft {
    higherThan: ComparisonPrecedence
    lowerThan: AdditionPrecedence
}

precedencegroup ModularityRight {
    higherThan: ModularityLeft
    lowerThan: AdditionPrecedence
}

infix operator *%* : ModularityLeft
infix operator %*% : ModularityRight

func %*%(exponent: Int, modulus: Int) -> (Int) -> Int {
    return { base in
        guard base > 0 && exponent >= 0 && modulus > 0
            else { return -1 }

        var base = base
        var exponent = exponent
        var result = 1

        while exponent > 0 {
            if exponent % 2 == 1 {
                result = (result * base) % modulus
            }
            base = (base * base) % modulus
            exponent = exponent / 2
        }

        return result
    }
}

func *%*(lhs: Int, rhs: (Int) -> Int) -> Int {
    return rhs(lhs)
}

然后你可以调用：

let result = 2907 *%* 1177 %*% 1211

附加信息：仅用于二进制 2907^1177 的信息需要 13542 位... https://www.wolframalpha.com/input/?i=2907%5E1177+in+binary

它需要一个 4kb 的字符串以 10 进制存储它：https://www.wolframalpha.com/input/?i=2907%5E1177

如何处理 swift 中长整数的答案

How to handle answer of long long integers in swift

rsa

pow

modulus

long-integer

swift