//===--- BigInt.swift -----------------------------------------*- swift -*-===// // // This source file is part of the Swift Numerics open source project // // Copyright (c) 2019 - 2020 Apple Inc. and the Swift Numerics project authors // Licensed under Apache License v2.0 with Runtime Library Exception // // See https://swift.org/LICENSE.txt for license information // //===----------------------------------------------------------------------===// public struct BigInt: SignedInteger { public typealias Words = [UInt] public private(set) var words: Words @usableFromInline internal init(_uncheckedWords: Words) { self.words = _uncheckedWords } public init(bitPattern source: T) where T: BinaryInteger { words = Words(source.words) BigInt._dropExcessWords(words: &words) } @usableFromInline internal var _isNegative: Bool { words[words.endIndex - 1] > Int.max } private static let _digits: [BigInt] = (0 ... 36).map { BigInt(_uncheckedWords: [UInt(bitPattern: $0)]) } private static let _digitRadix = BigInt(_uncheckedWords: [0, 1]) } // MARK: - Basic Behaviors extension BigInt: Equatable { @inlinable public static func == (lhs: BigInt, rhs: BigInt) -> Bool { lhs.words == rhs.words } @inlinable public static func != (lhs: BigInt, rhs: BigInt) -> Bool { !(lhs == rhs) } } extension BigInt: Hashable { @inlinable public func hash(into hasher: inout Hasher) { hasher.combine(words) } } extension BigInt: Comparable { @inlinable public static func < (lhs: BigInt, rhs: BigInt) -> Bool { let lhsNegative = lhs._isNegative let rhsNegative = rhs._isNegative if lhsNegative && !rhsNegative { return true } if rhsNegative && !lhsNegative { return false } if (lhsNegative && rhsNegative) || (!lhsNegative && !rhsNegative) { if lhs.words.count > rhs.words.count { return lhsNegative ? true : false } if lhs.words.count < rhs.words.count { return lhsNegative ? false : true } for i in stride(from: lhs.words.count - 1, through: 0, by: -1) { if lhs.words[i] > rhs.words[i] { return false } else if lhs.words[i] < rhs.words[i] { return true } } } return false } } extension BigInt: LosslessStringConvertible { public init?(_ description: String) { self.init(description, radix: 10) } public init?(_ description: T, radix: Int = 10) where T: StringProtocol { precondition(2 ... 36 ~= radix, "Radix not in range 2 ... 36") self = 0 let isNegative = description.hasPrefix("-") let hasPrefix = isNegative || description.hasPrefix("+") let utf8 = description.utf8.dropFirst(hasPrefix ? 1 : 0) guard !utf8.isEmpty else { return nil } for var byte in utf8 { switch byte { case UInt8(ascii: "0") ... UInt8(ascii: "9"): byte -= UInt8(ascii: "0") case UInt8(ascii: "A") ... UInt8(ascii: "Z"): byte -= UInt8(ascii: "A") byte += 10 case UInt8(ascii: "a") ... UInt8(ascii: "z"): byte -= UInt8(ascii: "a") byte += 10 default: return nil } guard byte < radix else { return nil } self *= BigInt._digits[radix] self += BigInt._digits[Int(byte)] } if isNegative { self.negate() } } } extension BigInt: Decodable { public init(from decoder: Decoder) throws { let singleValueContainer = try decoder.singleValueContainer() let description = try singleValueContainer.decode(String.self) guard let result = BigInt(description) else { throw DecodingError.dataCorruptedError( in: singleValueContainer, debugDescription: "BigInt(\(description.debugDescription)) failed") } self = result } } extension BigInt: Encodable { public func encode(to encoder: Encoder) throws { var singleValueContainer = encoder.singleValueContainer() try singleValueContainer.encode(description) } } // MARK: - Numeric Protocols extension BigInt: ExpressibleByIntegerLiteral { public init(integerLiteral value: Int) { if value >= 0, value < BigInt._digits.count { self = BigInt._digits[value] } else { words = [UInt(bitPattern: value)] } } } extension BigInt: AdditiveArithmetic { @inlinable public static func + (lhs: BigInt, rhs: BigInt) -> BigInt { var result = lhs result += rhs return result } public static func += (lhs: inout BigInt, rhs: BigInt) { if lhs.words.count == 1, rhs.words.count == 1 { let lhsWord = lhs.words[0] let rhsWord = rhs.words[0] let (result, isOverflow) = lhsWord.addingReportingOverflow(rhsWord) if !isOverflow && result < Int.max { lhs.words[0] = result return } let knownNegativeResult = lhsWord > Int.max && rhsWord > Int.max if lhsWord > Int.max || rhsWord > Int.max, !knownNegativeResult { // positive + negative is always smaller, so overflow is a red herring lhs.words[0] = result return } } var isOverflow = false var rhsWords = rhs.words lhs.words.append(lhs._isNegative ? UInt.max : 0) rhsWords.append(rhs._isNegative ? UInt.max : 0) BigInt._signExtend(lhsWords: &lhs.words, rhsWords: &rhsWords) var temp: UInt = 0 for index in 0 ..< lhs.words.count { var carryOverflow = false if isOverflow { (temp, carryOverflow) = rhsWords[index].addingReportingOverflow(1) } else { temp = rhsWords[index] } (lhs.words[index], isOverflow) = lhs.words[index].addingReportingOverflow(temp) isOverflow = carryOverflow || isOverflow } BigInt._dropExcessWords(words: &lhs.words) } @inlinable public static func - (lhs: BigInt, rhs: BigInt) -> BigInt { var result = lhs result -= rhs return result } @inlinable public static func -= (lhs: inout BigInt, rhs: BigInt) { lhs += -rhs } } extension BigInt: Numeric { public init?(exactly source: T) where T: BinaryInteger { self.init(source) } public var magnitude: BigInt { _isNegative ? -self : self } public static func * (lhs: BigInt, rhs: BigInt) -> BigInt { let lhsIsNeg = lhs.words[lhs.words.endIndex - 1] > Int.max let rhsIsNeg = rhs.words[rhs.words.endIndex - 1] > Int.max let lhsWords = lhsIsNeg ? (-lhs).words : lhs.words let rhsWords = rhsIsNeg ? (-rhs).words : rhs.words let count = lhsWords.count + rhsWords.count + 1 var newWords = Words(repeating: 0, count: count) for i in 0 ..< rhsWords.count { var carry: UInt = 0 var digit: UInt = 0 var lastJ: Int = 0 for j in i ..< (lhsWords.count + i) { var (high, low) = rhsWords[i].multipliedFullWidth(by: lhsWords[j - i]) var isOverflow: Bool (digit, isOverflow) = low.addingReportingOverflow(newWords[j]) if isOverflow { high += 1 } (digit, isOverflow) = digit.addingReportingOverflow(carry) if isOverflow { high += 1 } carry = high newWords[j] = digit lastJ = j } if carry != 0 { let isOverflow: Bool (digit, isOverflow) = newWords[lastJ + 1].addingReportingOverflow(carry) if isOverflow { carry = 1 } newWords[lastJ + 1] = digit } } for i in stride(from: count - 1, through: 1, by: -1) { if newWords[i] == 0, newWords[i - 1] <= Int.max { newWords.removeLast() } else { break } } if lhsIsNeg || rhsIsNeg, !(lhsIsNeg && rhsIsNeg) { return -BigInt(_uncheckedWords: newWords) } return BigInt(_uncheckedWords: newWords) } @inlinable public static func *= (lhs: inout BigInt, rhs: BigInt) { lhs = lhs * rhs } } extension BigInt: SignedNumeric { public mutating func negate() { var isOverflow = true for i in 0 ..< words.count { if isOverflow { (words[i], isOverflow) = (~words[i]).addingReportingOverflow(1) } else { words[i] = ~words[i] } } BigInt._dropExcessWords(words: &words) } @inlinable public static prefix func - (x: BigInt) -> BigInt { var result = x result.negate() return result } } extension BigInt: BinaryInteger { public init?(exactly source: T) where T: BinaryFloatingPoint { guard source.isFinite, source == source.rounded(.towardZero) else { return nil } self.init(source) } public init(_ source: T) where T: BinaryFloatingPoint { precondition( source.isFinite, """ \(type(of: source)) value cannot be converted to BigInt because it is \ either infinite or NaN """) let isNegative = source < 0.0 var float = isNegative ? -source : source if let _ = UInt(exactly: T.greatestFiniteMagnitude) { words = [UInt(float)] } else { var words = Words() let radix = T(sign: .plus, exponent: T.Exponent(UInt.bitWidth), significand: 1) repeat { let digit = UInt(float.truncatingRemainder(dividingBy: radix)) words.append(digit) float = (float / radix).rounded(.towardZero) } while float != 0 if let last = words.last, last >= Int.max { words.append(0) } self.words = words } if isNegative { self.negate() } } public init(_ source: T) where T: BinaryInteger { if source >= 0, source < BigInt._digits.count { self = BigInt._digits[Int(source)] } else { words = Words(source.words) if source > 0 && source.words[source.words.endIndex - 1] > Int.max { words.append(0) } // needed to handle sign-extended multi-word numbers that // actually fit in a single word BigInt._dropExcessWords(words: &words) } } public init(clamping source: T) where T: BinaryInteger { self.init(source) } public init(truncatingIfNeeded source: T) where T: BinaryInteger { words = Words(source.words) } public var bitWidth: Int { words.count * UInt.bitWidth } public var trailingZeroBitCount: Int { var totalZeros = 0 for word in words { if word == 0 { totalZeros += UInt.bitWidth } else { totalZeros += word.trailingZeroBitCount break } } return totalZeros } @inlinable public static func / (lhs: BigInt, rhs: BigInt) -> BigInt { let (result, _) = _div(lhs: lhs, rhs: rhs) return result } @inlinable public static func /= (lhs: inout BigInt, rhs: BigInt) { lhs = lhs / rhs } @inlinable public static func % (lhs: BigInt, rhs: BigInt) -> BigInt { let (_, result) = _div(lhs: lhs, rhs: rhs) return result } @inlinable public static func %= (lhs: inout BigInt, rhs: BigInt) { lhs = lhs % rhs } @inlinable public static prefix func ~ (x: BigInt) -> BigInt { let newWords = x.words.map { ~$0 } return BigInt(_uncheckedWords: Words(newWords)) } public static func &= (lhs: inout BigInt, rhs: BigInt) { var rhsWords = rhs.words BigInt._signExtend(lhsWords: &lhs.words, rhsWords: &rhsWords) for i in 0 ..< rhsWords.count { lhs.words[i] &= rhsWords[i] } BigInt._dropExcessWords(words: &lhs.words) } public static func |= (lhs: inout BigInt, rhs: BigInt) { var rhsWords = rhs.words BigInt._signExtend(lhsWords: &lhs.words, rhsWords: &rhsWords) for i in 0 ..< rhsWords.count { lhs.words[i] |= rhsWords[i] } BigInt._dropExcessWords(words: &lhs.words) } public static func ^= (lhs: inout BigInt, rhs: BigInt) { var rhsWords = rhs.words BigInt._signExtend(lhsWords: &lhs.words, rhsWords: &rhsWords) for i in 0 ..< rhsWords.count { lhs.words[i] &= rhsWords[i] } BigInt._dropExcessWords(words: &lhs.words) } public static func <<= (lhs: inout BigInt, rhs: RHS) where RHS: BinaryInteger { if rhs.signum() < 0 { lhs >>= rhs.magnitude return } let wordLength = UInt.bitWidth let isNegative = lhs._isNegative let (fullWords, remainder) = rhs.quotientAndRemainder(dividingBy: RHS(wordLength)) lhs.words = Words(repeating: 0, count: Int(fullWords)) + lhs.words + [isNegative ? UInt.max : 0] if remainder > 0 { var value: UInt = 0 for i in 0 ..< lhs.words.count { let temp = lhs.words[i] >> (wordLength - Int(remainder)) lhs.words[i] <<= Int(remainder) if i > 0 { lhs.words[i] &= UInt.max << Int(remainder) lhs.words[i] |= value } value = temp } if isNegative { lhs.words[lhs.words.count - 1] |= (UInt.max << Int(remainder)) } } BigInt._dropExcessWords(words: &lhs.words) } public static func >>= (lhs: inout BigInt, rhs: RHS) where RHS: BinaryInteger { if rhs.signum() < 0 { lhs <<= rhs.magnitude return } let wordLength = UInt.bitWidth let isNegative = lhs._isNegative let (fullWords, remainder) = rhs.quotientAndRemainder(dividingBy: RHS(wordLength)) if fullWords < lhs.words.count { lhs.words.removeFirst(Int(fullWords)) } else { lhs = isNegative ? -1 : 0 return } if remainder > 0 { let mask = ~(UInt.max << remainder) var value: UInt = 0 for i in stride(from: lhs.words.count - 1, through: 0, by: -1) { let temp = lhs.words[i] & mask lhs.words[i] >>= remainder lhs.words[i] |= (value << (UInt.bitWidth - Int(remainder))) value = temp } } if isNegative { lhs.words[lhs.words.count - 1] |= (UInt.max << (UInt.bitWidth - Int(remainder))) } BigInt._dropExcessWords(words: &lhs.words) } @inlinable public func quotientAndRemainder(dividingBy rhs: BigInt) -> (quotient: BigInt, remainder: BigInt) { return BigInt._div(lhs: self, rhs: rhs) } @inlinable public func signum() -> BigInt { _isNegative ? -1 : (self == 0) ? 0 : 1 } } // MARK: - extension BigInt { /// See _The Art of Computer Programming_ volume 2 by Donald Knuth, Section 4.3.1: The Classical Algorithms private static func _findQhat( high: UInt, low: UInt.Magnitude, divisor: UInt, nextVdigit: UInt, nextUdigit: UInt ) -> UInt { var qhat: Array var rhat: Array if high >= divisor { let v = divisor let u = [low, high] var r: UInt = 0 qhat = Words(repeating: 0, count: 2) for j in (0...1).reversed() { let uj = u[j] (qhat[j], r) = v.dividingFullWidth((r, uj)) } BigInt._dropExcessWords(words: &qhat) rhat = [r] } else { let (qhatWord, rhatWord) = divisor.dividingFullWidth((high, low)) qhat = [qhatWord] rhat = [rhatWord] } repeat { var qhatTooLarge = false if qhat.count > 1 { qhatTooLarge = true } else { // All of the following is computing and checking qhat*v_n-2 > rhat*b + u_j+n-2 // from TAoCP Volume 2 Section 4.3.1, Algorithm D, step D3 let (comp_lhs_hi, comp_lhs_lo) = qhat[0].multipliedFullWidth(by: nextVdigit) if comp_lhs_hi > rhat[0] { qhatTooLarge = true } else if comp_lhs_hi == rhat[0] && comp_lhs_lo > nextUdigit { qhatTooLarge = true } } // high >= divisor is standing in for the test qhat >= b from Algorithm D step D3 if qhatTooLarge { // begin qhat -= 1 if qhat.count == 1 { qhat[0] -= 1 } else { let (qlow, underflow) = qhat[0].subtractingReportingOverflow(1) qhat[0] = qlow if qhat[1] > 0 && underflow { qhat[1] -= 1 if qhat[1] == 0 { qhat.remove(at: 1) } } } // end qhat -= 1 // begin rhat += divisor let (rhatResult, overflow) : (UInt, Bool) if rhat.count == 1 || rhat[1] == 0 { (rhatResult, overflow) = rhat[0].addingReportingOverflow(divisor) rhat[0] = rhatResult if overflow { rhat.append(1) } } // we don't need an else because rhat is already larger than BigInt._digitRadix // end rhat += divisor } else { break } } while rhat.count == 1 // equivalent to rhat < b return qhat[0] } /// See _The Art of Computer Programming_ volume 2 by Donald Knuth, Section 4.3.1: The Classical Algorithms @usableFromInline internal static func _div(lhs: BigInt, rhs: BigInt) -> (quotient: BigInt, remainder: BigInt) { precondition(rhs != _digits[0], "Division by zero error!") if lhs.words.count == 1, rhs.words.count == 1 { let (quot, rem) = Int(bitPattern: lhs.words[0]).quotientAndRemainder(dividingBy: Int(bitPattern: rhs.words[0])) return (BigInt(_uncheckedWords: [UInt(bitPattern: quot)]), BigInt(_uncheckedWords: [UInt(bitPattern: rem)])) } let lhsIsNeg = lhs._isNegative let rhsIsNeg = rhs._isNegative var lhsWords = lhsIsNeg ? (-lhs).words : lhs.words var rhsWords = rhsIsNeg ? (-rhs).words : rhs.words // See the answer to exercise 16 in Section 4.3.1 of TAOCP if rhsWords.count == 1 || (rhsWords.count == 2 && rhsWords[1] == 0) { let v = rhsWords[0] let u = lhsWords var r: UInt = 0 var quot = Words(repeating: 0, count: u.count) for j in (0...(u.count - 1)).reversed() { let uj = u[j] (quot[j], r) = v.dividingFullWidth((r, uj)) } if quot[u.count - 1] > UInt(Int.max) { quot.append(0) } BigInt._dropExcessWords(words: ") return (quotient: BigInt(_uncheckedWords: quot), remainder: BigInt(r)) } while rhsWords[rhsWords.endIndex - 1] == 0 { rhsWords.removeLast() } if rhsWords.count > lhsWords.count { return (0, lhs) } if lhsWords.count <= rhsWords.count { for _ in 0 ... (rhsWords.count - lhsWords.count) { lhsWords.append(0) } } let m = lhsWords.count - rhsWords.count let n = rhsWords.count let bitWidth = UInt(UInt.bitWidth) let s = UInt(rhsWords[n - 1].leadingZeroBitCount) let rn = UnsafeMutablePointer.allocate(capacity: n) rn.initialize(repeating: 0, count: n) defer { rn.deallocate() } for i in (1 ... (n - 1)).reversed() { rn[i] = (rhsWords[i] << s) | (rhsWords[i - 1] >> (bitWidth - s)) } rn[0] = rhsWords[0] << s let ln = UnsafeMutablePointer.allocate(capacity: m + n + 1) ln.initialize(repeating: 0, count: m + n + 1) defer { ln.deallocate() } ln[m + n] = lhsWords[m + n - 1] >> (bitWidth - s) for i in (1 ... (m + n - 1)).reversed() { ln[i] = (lhsWords[i] << s) | (lhsWords[i - 1] >> (bitWidth - s)) } ln[0] = lhsWords[0] << s let resultSize = m + 1 var quot = Words(repeating: 0, count: resultSize) for j in (0 ... m).reversed() { let qhat = _findQhat( high: ln[j + n], low: UInt.Magnitude(ln[j + n - 1]), divisor: rn[n - 1], nextVdigit: rn[n - 2], nextUdigit: ln[j + n - 2]) var carry: UInt = 0 var isOverflow = false var borrow: UInt = 0 var underflow = false for i in 0 ..< n { if borrow > 0 { (ln[i + j], underflow) = ln[i + j].subtractingReportingOverflow(borrow) borrow = underflow ? 1 : 0 } var (pHigh, pLow) = qhat.multipliedFullWidth(by: rn[i]) (pLow, isOverflow) = pLow.addingReportingOverflow(carry) if isOverflow { pHigh += 1 } (ln[i + j], underflow) = ln[i + j].subtractingReportingOverflow(pLow) if underflow { borrow += 1 } carry = pHigh } (ln[j + n], underflow) = ln[j + n].subtractingReportingOverflow(carry + borrow) if underflow { let newQhat = qhat - 1 carry = 0 var total: UInt = 0 for i in 0 ..< n { (total, isOverflow) = ln[i + j].addingReportingOverflow(carry) carry = isOverflow ? 1 : 0 (ln[i + j], isOverflow) = total.addingReportingOverflow(rn[i]) if carry == 0 { carry = isOverflow ? 1 : 0 } } (ln[j + n], _) = ln[j + n].addingReportingOverflow(carry) quot[j] = newQhat } else { quot[j] = qhat } } var rem = Words(repeating: 0, count: n) for i in 0 ..< (n - 1) { rem[i] = (ln[i] >> s) | ln[i + 1] << (bitWidth - s) } rem[n - 1] = ln[n - 1] >> s if rem[n - 1] > UInt(Int.max) { rem.append(0) } BigInt._dropExcessWords(words: ") BigInt._dropExcessWords(words: &rem) return (BigInt(_uncheckedWords: quot), BigInt(_uncheckedWords: rem)) } private static func _signExtend(lhsWords: inout Words, rhsWords: inout Words) { let lhsIsNeg = (lhsWords.last ?? 0) >> (UInt.bitWidth - Int(1)) == 1 let rhsIsNeg = (rhsWords.last ?? 0) >> (UInt.bitWidth - Int(1)) == 1 if lhsWords.count > rhsWords.count { for _ in 0 ..< (lhsWords.count - rhsWords.count) { rhsIsNeg ? rhsWords.append(UInt.max) : rhsWords.append(0) } } else if rhsWords.count > lhsWords.count { for _ in 0 ..< (rhsWords.count - lhsWords.count) { lhsIsNeg ? lhsWords.append(UInt.max) : lhsWords.append(0) } } } @usableFromInline internal static func _dropExcessWords(words: inout Words) { while words.count > 1, words[words.endIndex - 1] == 0 { if words[words.endIndex - 2] <= Int.max { words.removeLast() } else { break } } while words.count > 1, words[words.endIndex - 1] == UInt.max { if words[words.endIndex - 2] > Int.max { words.removeLast() } else { break } } } }