How to handle answer of long long integers in swift

Question

I have to calculate power of two long integers in swift. Swift gives an error of NaN (not a number) and fails to answer.

e.g

pow(2907,1177)

The main process id to calculate power and get remainder (a^b % n) where a= 2907, b= 1177, n= 1211

Any guidelines how to solve it?

`pow` works with floating points only, well `NaN` is IEEE 754 floating point "value". — user28434'mstep, Jan 24 '19 at 11:15
Also, it looks like you're trying to do `Modular exponentiation`, and there's special [`Memory-efficient method`](https://en.wikipedia.org/wiki/Modular_exponentiation#Memory-efficient_method) for this. You don't need to calculate full value of `a^b` at all. — user28434'mstep, Jan 24 '19 at 11:21
@Mubashar, do not hesitate to accept the answer if it works for you. — Zaphod, Jan 25 '19 at 13:45

Zaphod · Accepted Answer · 2019-01-24T14:44:50.220

You will have to use either 1. an external framework or 2. do it by yourself.

1. External Framework:

I think you can try : 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

Note: Cocoapods import failed so I just imported this file for it to work: https://github.com/mkrd/Swift-Big-Integer/tree/master/Sources

2. DIY: Using the answer of 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. Bonus: Using the same as 2. but with custom ternary operator thanks to 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)
}

And then you can just call:

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

Additional information: Just for information in binary 2907^1177 takes 13542bits... https://www.wolframalpha.com/input/?i=2907%5E1177+in+binary

It takes a 4kb string to store it in base 10 : https://www.wolframalpha.com/input/?i=2907%5E1177

2nd point. *DIY: Using the answer of Modulus power of big numbers* is the right option to get modulus of long numbers. — Mubashar, Jan 28 '19 at 09:30

How to handle answer of long long integers in swift

1 Answers1