CODEWITHSUNDEEP
swiftbigintegermodular-arithmetic
Dracula
Dracula

Reputation: 3090

How to do modular arithmetics on big numbers in Swift?

This comes up when evaluating a rolling hash of a string by subtracting the old weight of a character and adding a new weight for a new character.

Python has infinite length digits and is able to store such large numbers:

num = -56061846576641933068511861128435847024473459936647893758520084401988341
div = 10**9 + 7
mod = num % div #504892002

But in Swift, as I keep doing calculations, I lose precision and get bigger and bigger errors. For example, at some point in my calculations, the above number had this value:

var num = Double("-5.606184657664193e+70")
var div = pow(Double(10), 9) + 7
var mod = num!.truncatingRemainder(dividingBy: div)
mod = mod < 0 ? mod + div : mod //215272131.0

I looked into Decimal, but it does not support the mod operation. And Int64 will also be too small for such numbers. Are there any other native options, without adding convenience extensions?

Also, How do you get the int and modulo (mod) of division with an NSDecimalNumber does not help. It suggests extensions or has examples that do not deal with big numbers.

Upvotes: 0

Views: 161

Answers (0)

Related Questions