Files
2020-04-24 12:39:49 +01:00

811 lines
21 KiB
Swift

//===--- 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<T>(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?<T>(_ 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?<T>(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?<T>(exactly source: T) where T: BinaryFloatingPoint {
guard source.isFinite, source == source.rounded(.towardZero) else {
return nil
}
self.init(source)
}
public init<T>(_ 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<T>(_ 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<T>(clamping source: T) where T: BinaryInteger {
self.init(source)
}
public init<T>(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 <<= <RHS>(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 >>= <RHS>(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<UInt>
var rhat: Array<UInt>
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: &quot)
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<UInt>.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<UInt>.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: &quot)
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
}
}
}
}