0001    //
0002    //  BigInt.swift
0003    //  BigInt
0004    //
0005    //  Created by Károly Lőrentey on 2015-12-27.
0006    //  Copyright © 2016 Károly Lőrentey. All rights reserved.
0007    //
0008    
0009    import Foundation
0010    
0011    //MARK: BigInt
0012    
0013    /// An arbitary precision signed integer type, also known as a "big integer".
0014    ///
0015    /// Operations on big integers never overflow, but they might take a long time to execute.
0016    /// The amount of memory (and address space) available is the only constraint to the magnitude of these numbers.
0017    ///
0018    /// This particular big integer type uses base-2^64 digits to represent integers.
0019    ///
0020    /// `BigInt` is essentially a tiny wrapper that extends `BigUInt` with a sign bit and provides signed integer
0021    /// operations. Both the underlying absolute value and the negative/positive flag are available as read-write 
0022    /// properties.
0023    ///
0024    /// Not all algorithms of `BigUInt` are available for `BigInt` values; for example, there is no square root or
0025    /// primality test for signed integers. When you need to call one of these, just extract the absolute value:
0026    ///
0027    /// ```Swift
0028    /// BigInt(255).abs.isPrime()   // Returns false
0029    /// ```
0030    ///
0031    public struct BigInt
BigInt.swift:69
extension BigInt {
BigInt.swift:101
    public init(_ value: BigInt, radix: Int = 10, uppercase: Bool = false) {
BigInt.swift:109
extension BigInt: CustomStringConvertible {
BigInt.swift:114
extension BigInt: IntegerLiteralConvertible {
BigInt.swift:122
extension BigInt: StringLiteralConvertible {
BigInt.swift:126
        self = BigInt(String(value), radix: 10)!
BigInt.swift:132
        self = BigInt(value, radix: 10)!
BigInt.swift:138
        self = BigInt(value, radix: 10)!
BigInt.swift:142
extension BigInt: CustomPlaygroundQuickLookable {
BigInt.swift:151
extension BigInt: Comparable {
BigInt.swift:156
public func ==(a: BigInt, b: BigInt) -> Bool {
BigInt.swift:156
public func ==(a: BigInt, b: BigInt) -> Bool {
BigInt.swift:162
public func <(a: BigInt, b: BigInt) -> Bool {
BigInt.swift:162
public func <(a: BigInt, b: BigInt) -> Bool {
BigInt.swift:175
extension BigInt: Hashable {
BigInt.swift:185
public func +(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:185
public func +(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:185
public func +(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:188
        return BigInt(abs: a.abs + b.abs, negative: false)
BigInt.swift:190
        return BigInt(abs: a.abs + b.abs, negative: true)
BigInt.swift:193
            return BigInt(abs: a.abs - b.abs, negative: false)
BigInt.swift:196
            return BigInt(abs: b.abs - a.abs, negative: true)
BigInt.swift:200
            return BigInt(abs: b.abs - a.abs, negative: false)
BigInt.swift:203
            return BigInt(abs: a.abs - b.abs, negative: true)
BigInt.swift:210
public prefix func -(a: BigInt) -> BigInt {
BigInt.swift:210
public prefix func -(a: BigInt) -> BigInt {
BigInt.swift:212
    return BigInt(abs: a.abs, negative: !a.negative)
BigInt.swift:217
public func -(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:217
public func -(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:217
public func -(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:223
public func *(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:223
public func *(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:223
public func *(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:224
    return BigInt(abs: a.abs * b.abs, negative: a.negative != b.negative)
BigInt.swift:229
public func /(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:229
public func /(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:229
public func /(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:230
    return BigInt(abs: a.abs / b.abs, negative: a.negative != b.negative)
BigInt.swift:235
public func %(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:235
public func %(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:235
public func %(a: BigInt, b: BigInt) -> BigInt {
BigInt.swift:236
    return BigInt(abs: a.abs % b.abs, negative: a.negative)
BigInt.swift:240
public func +=(inout a: BigInt, b: BigInt) { a = a + b }
BigInt.swift:240
public func +=(inout a: BigInt, b: BigInt) { a = a + b }
BigInt.swift:242
public func -=(inout a: BigInt, b: BigInt) { a = a - b }
BigInt.swift:242
public func -=(inout a: BigInt, b: BigInt) { a = a - b }
BigInt.swift:244
public func *=(inout a: BigInt, b: BigInt) { a = a * b }
BigInt.swift:244
public func *=(inout a: BigInt, b: BigInt) { a = a * b }
BigInt.swift:246
public func /=(inout a: BigInt, b: BigInt) { a = a / b }
BigInt.swift:246
public func /=(inout a: BigInt, b: BigInt) { a = a / b }
BigInt.swift:248
public func %=(inout a: BigInt, b: BigInt) { a = a % b }
BigInt.swift:248
public func %=(inout a: BigInt, b: BigInt) { a = a % b }
BigUInt GCD.swift:46
        var t1 = BigInt(0)
BigUInt GCD.swift:47
        var t2 = BigInt(1)
BigUInt GCD.swift:52
            (t1, t2) = (t2, t1 - BigInt(quotient) * t2)
 {
0032        /// The absolute value of this integer.
0033        public var abs
BigInt.swift:39
        self.abs = abs
BigInt.swift:64
        self.abs = integer
BigInt.swift:88
        self.abs = abs
BigInt.swift:102
        self = String(value.abs, radix: radix, uppercase: uppercase)
BigInt.swift:147
        return PlaygroundQuickLook.Text(text + " (\(self.abs.width) bits)")
BigInt.swift:157
    return a.negative == b.negative && a.abs == b.abs
BigInt.swift:157
    return a.negative == b.negative && a.abs == b.abs
BigInt.swift:165
        return a.abs < b.abs
BigInt.swift:165
        return a.abs < b.abs
BigInt.swift:171
        return a.abs > b.abs
BigInt.swift:171
        return a.abs > b.abs
BigInt.swift:178
        let v = abs.hashValue
BigInt.swift:188
        return BigInt(abs: a.abs + b.abs, negative: false)
BigInt.swift:188
        return BigInt(abs: a.abs + b.abs, negative: false)
BigInt.swift:190
        return BigInt(abs: a.abs + b.abs, negative: true)
BigInt.swift:190
        return BigInt(abs: a.abs + b.abs, negative: true)
BigInt.swift:192
        if a.abs >= b.abs {
BigInt.swift:192
        if a.abs >= b.abs {
BigInt.swift:193
            return BigInt(abs: a.abs - b.abs, negative: false)
BigInt.swift:193
            return BigInt(abs: a.abs - b.abs, negative: false)
BigInt.swift:196
            return BigInt(abs: b.abs - a.abs, negative: true)
BigInt.swift:196
            return BigInt(abs: b.abs - a.abs, negative: true)
BigInt.swift:199
        if b.abs >= a.abs {
BigInt.swift:199
        if b.abs >= a.abs {
BigInt.swift:200
            return BigInt(abs: b.abs - a.abs, negative: false)
BigInt.swift:200
            return BigInt(abs: b.abs - a.abs, negative: false)
BigInt.swift:203
            return BigInt(abs: a.abs - b.abs, negative: true)
BigInt.swift:203
            return BigInt(abs: a.abs - b.abs, negative: true)
BigInt.swift:211
    if a.abs.isZero { return a }
BigInt.swift:212
    return BigInt(abs: a.abs, negative: !a.negative)
BigInt.swift:224
    return BigInt(abs: a.abs * b.abs, negative: a.negative != b.negative)
BigInt.swift:224
    return BigInt(abs: a.abs * b.abs, negative: a.negative != b.negative)
BigInt.swift:230
    return BigInt(abs: a.abs / b.abs, negative: a.negative != b.negative)
BigInt.swift:230
    return BigInt(abs: a.abs / b.abs, negative: a.negative != b.negative)
BigInt.swift:236
    return BigInt(abs: a.abs % b.abs, negative: a.negative)
BigInt.swift:236
    return BigInt(abs: a.abs % b.abs, negative: a.negative)
BigUInt GCD.swift:56
        if t1.negative { return modulus - t1.abs }
BigUInt GCD.swift:57
        return t1.abs
: BigUInt
0034        /// True iff the value of this integer is negative.
0035        public var negative
BigInt.swift:40
        self.negative = (abs.isZero ? false : negative)
BigInt.swift:65
        self.negative = false
BigInt.swift:89
        self.negative = negative
BigInt.swift:103
        if value.negative {
BigInt.swift:157
    return a.negative == b.negative && a.abs == b.abs
BigInt.swift:157
    return a.negative == b.negative && a.abs == b.abs
BigInt.swift:163
    switch (a.negative, b.negative) {
BigInt.swift:163
    switch (a.negative, b.negative) {
BigInt.swift:179
        return negative ? ~v : v
BigInt.swift:186
    switch (a.negative, b.negative) {
BigInt.swift:186
    switch (a.negative, b.negative) {
BigInt.swift:212
    return BigInt(abs: a.abs, negative: !a.negative)
BigInt.swift:224
    return BigInt(abs: a.abs * b.abs, negative: a.negative != b.negative)
BigInt.swift:224
    return BigInt(abs: a.abs * b.abs, negative: a.negative != b.negative)
BigInt.swift:230
    return BigInt(abs: a.abs / b.abs, negative: a.negative != b.negative)
BigInt.swift:230
    return BigInt(abs: a.abs / b.abs, negative: a.negative != b.negative)
BigInt.swift:236
    return BigInt(abs: a.abs % b.abs, negative: a.negative)
BigUInt GCD.swift:56
        if t1.negative { return modulus - t1.abs }
: Bool
0036    
0037        /// Initializes a new big integer with the provided absolute number and sign flag.
0038        public init
BigInt.swift:45
        self.init(abs: BigUInt(integer), negative: false)
BigInt.swift:52
            self.init(abs: BigUInt(IntMax.max) + 1, negative: true)
BigInt.swift:55
            self.init(abs: BigUInt(-i), negative: true)
BigInt.swift:58
            self.init(abs: BigUInt(i), negative: false)
BigInt.swift:188
        return BigInt(abs: a.abs + b.abs, negative: false)
BigInt.swift:190
        return BigInt(abs: a.abs + b.abs, negative: true)
BigInt.swift:193
            return BigInt(abs: a.abs - b.abs, negative: false)
BigInt.swift:196
            return BigInt(abs: b.abs - a.abs, negative: true)
BigInt.swift:200
            return BigInt(abs: b.abs - a.abs, negative: false)
BigInt.swift:203
            return BigInt(abs: a.abs - b.abs, negative: true)
BigInt.swift:212
    return BigInt(abs: a.abs, negative: !a.negative)
BigInt.swift:224
    return BigInt(abs: a.abs * b.abs, negative: a.negative != b.negative)
BigInt.swift:230
    return BigInt(abs: a.abs / b.abs, negative: a.negative != b.negative)
BigInt.swift:236
    return BigInt(abs: a.abs % b.abs, negative: a.negative)
(abs: BigUInt, negative: Bool = false) {
0039            self.abs = abs
0040            self.negative = (abs.isZero ? false : negative)
0041        }
0042    
0043        /// Initializes a new big integer with the same value as the specified integer.
0044        public init<I: UnsignedIntegerType>(_ integer: I) {
0045            self.init(abs: BigUInt(integer), negative: false)
0046        }
0047    
0048        /// Initializes a new big integer with the same value as the specified integer.
0049        public init
BigInt.swift:118
        self.init(value)
BigUInt GCD.swift:46
        var t1 = BigInt(0)
BigUInt GCD.swift:47
        var t2 = BigInt(1)
<I: SignedIntegerType>(_ integer: I) {
0050            let i = integer.toIntMax()
0051            if i == IntMax.min {
0052                self.init(abs: BigUInt(IntMax.max) + 1, negative: true)
0053            }
0054            else if i < 0 {
0055                self.init(abs: BigUInt(-i), negative: true)
0056            }
0057            else {
0058                self.init(abs: BigUInt(i), negative: false)
0059            }
0060        }
0061    
0062        /// Initializes a new signed big integer with the same value as the specified unsigned big integer.
0063        public init
BigUInt GCD.swift:52
            (t1, t2) = (t2, t1 - BigInt(quotient) * t2)
(_ integer: BigUInt) {
0064            self.abs = integer
0065            self.negative = false
0066        }
0067    }
0068    
0069    extension BigInt {
0070        /// Initialize a big integer from an ASCII representation in a given radix. Numerals above `9` are represented by
0071        /// letters from the English alphabet.
0072        ///
0073        /// - Requires: `radix > 1 && radix < 36`
0074        /// - Parameter `text`: A string optionally starting with "-" or "+" followed by characters corresponding to numerals in the given radix. (0-9, a-z, A-Z)
0075        /// - Parameter `radix`: The base of the number system to use, or 10 if unspecified.
0076        /// - Returns: The integer represented by `text`, or nil if `text` contains a character that does not represent a numeral in `radix`.
0077        public init
BigInt.swift:126
        self = BigInt(String(value), radix: 10)!
BigInt.swift:132
        self = BigInt(value, radix: 10)!
BigInt.swift:138
        self = BigInt(value, radix: 10)!
?(_ text: String, radix: Int = 10) {
0078            var text = text
0079            var negative = false
0080            if text.characters.first == "-" {
0081                negative = true
0082                text = text.substringFromIndex(text.startIndex.successor())
0083            }
0084            else if text.characters.first == "+" {
0085                text = text.substringFromIndex(text.startIndex.successor())
0086            }
0087            guard let abs = BigUInt(text, radix: radix) else { return nil }
0088            self.abs = abs
0089            self.negative = negative
0090        }
0091    }
0092    
0093    extension String {
0094        /// Initialize a new string representing a signed big integer in the given radix (base).
0095        ///
0096        /// Numerals greater than 9 are represented as letters from the English alphabet,
0097        /// starting with `a` if `uppercase` is false or `A` otherwise.
0098        ///
0099        /// - Requires: radix > 1 && radix <= 36
0100        /// - Complexity: O(count) when radix is a power of two; otherwise O(count^2).
0101        public init
BigInt.swift:111
    public var description: String { return String(self, radix: 10) }
BigInt.swift:146
        let text = String(self)
(_ value: BigInt, radix: Int = 10, uppercase: Bool = false) {
0102            self = String(value.abs, radix: radix, uppercase: uppercase)
0103            if value.negative {
0104                self = "-" + self
0105            }
0106        }
0107    }
0108    
0109    extension BigInt: CustomStringConvertible {
0110        /// Return the decimal representation of this integer.
0111        public var description: String { return String(self, radix: 10) }
0112    }
0113    
0114    extension BigInt: IntegerLiteralConvertible {
0115    
0116        /// Initialize a new big integer from an integer literal.
0117        public init(integerLiteral value: IntMax) {
0118            self.init(value)
0119        }
0120    }
0121    
0122    extension BigInt: StringLiteralConvertible {
0123        /// Initialize a new big integer from a Unicode scalar.
0124        /// The scalar must represent a decimal digit.
0125        public init(unicodeScalarLiteral value: UnicodeScalar) {
0126            self = BigInt(String(value), radix: 10)!
0127        }
0128    
0129        /// Initialize a new big integer from an extended grapheme cluster.
0130        /// The cluster must consist of a decimal digit.
0131        public init(extendedGraphemeClusterLiteral value: String) {
0132            self = BigInt(value, radix: 10)!
0133        }
0134    
0135        /// Initialize a new big integer from a decimal number represented by a string literal of arbitrary length.
0136        /// The string must contain only decimal digits.
0137        public init(stringLiteral value: StringLiteralType) {
0138            self = BigInt(value, radix: 10)!
0139        }
0140    }
0141    
0142    extension BigInt: CustomPlaygroundQuickLookable {
0143        /// Return the playground quick look representation of this integer.
0144        @warn_unused_result
0145        public func customPlaygroundQuickLook() -> PlaygroundQuickLook {
0146            let text = String(self)
0147            return PlaygroundQuickLook.Text(text + " (\(self.abs.width) bits)")
0148        }
0149    }
0150    
0151    extension BigInt: Comparable {
0152    }
0153    
0154    /// Return true iff `a` is equal to `b`.
0155    @warn_unused_result
0156    public func ==(a: BigInt, b: BigInt) -> Bool {
0157        return a.negative == b.negative && a.abs == b.abs
0158    }
0159    
0160    /// Return true iff `a` is less than `b`.
0161    @warn_unused_result
0162    public func <(a: BigInt, b: BigInt) -> Bool {
0163        switch (a.negative, b.negative) {
0164        case (false, false):
0165            return a.abs < b.abs
0166        case (false, true):
0167            return false
0168        case (true, false):
0169            return true
0170        case (true, true):
0171            return a.abs > b.abs
0172        }
0173    }
0174    
0175    extension BigInt: Hashable {
0176        /// Return the hash value of this integer.
0177        public var hashValue: Int {
0178            let v = abs.hashValue
0179            return negative ? ~v : v
0180        }
0181    }
0182    
0183    /// Add `a` to `b` and return the result.
0184    @warn_unused_result
0185    public func +(a: BigInt, b: BigInt) -> BigInt {
0186        switch (a.negative, b.negative) {
0187        case (false, false):
0188            return BigInt(abs: a.abs + b.abs, negative: false)
0189        case (true, true):
0190            return BigInt(abs: a.abs + b.abs, negative: true)
0191        case (false, true):
0192            if a.abs >= b.abs {
0193                return BigInt(abs: a.abs - b.abs, negative: false)
0194            }
0195            else {
0196                return BigInt(abs: b.abs - a.abs, negative: true)
0197            }
0198        case (true, false):
0199            if b.abs >= a.abs {
0200                return BigInt(abs: b.abs - a.abs, negative: false)
0201            }
0202            else {
0203                return BigInt(abs: a.abs - b.abs, negative: true)
0204            }
0205        }
0206    }
0207    
0208    /// Negate `a` and return the result.
0209    @warn_unused_result
0210    public prefix func -(a: BigInt) -> BigInt {
0211        if a.abs.isZero { return a }
0212        return BigInt(abs: a.abs, negative: !a.negative)
0213    }
0214    
0215    /// Subtract `b` from `a` and return the result.
0216    @warn_unused_result
0217    public func -(a: BigInt, b: BigInt) -> BigInt {
0218        return a + (-b)
0219    }
0220    
0221    /// Multiply `a` with `b` and return the result.
0222    @warn_unused_result
0223    public func *(a: BigInt, b: BigInt) -> BigInt {
0224        return BigInt(abs: a.abs * b.abs, negative: a.negative != b.negative)
0225    }
0226    
0227    /// Divide `a` by `b` and return the quotient.
0228    @warn_unused_result
0229    public func /(a: BigInt, b: BigInt) -> BigInt {
0230        return BigInt(abs: a.abs / b.abs, negative: a.negative != b.negative)
0231    }
0232    
0233    /// Divide `a` by `b` and return the remainder.
0234    @warn_unused_result
0235    public func %(a: BigInt, b: BigInt) -> BigInt {
0236        return BigInt(abs: a.abs % b.abs, negative: a.negative)
0237    }
0238    
0239    /// Add `b` to `a` in place.
0240    public func +=(inout a: BigInt, b: BigInt) { a = a + b }
0241    /// Subtract `b` from `a` in place.
0242    public func -=(inout a: BigInt, b: BigInt) { a = a - b }
0243    /// Multiply `a` with `b` in place.
0244    public func *=(inout a: BigInt, b: BigInt) { a = a * b }
0245    /// Divide `a` by `b` storing the quotient in `a`.
0246    public func /=(inout a: BigInt, b: BigInt) { a = a / b }
0247    /// Divide `a` by `b` storing the remainder in `a`.
0248    public func %=(inout a: BigInt, b: BigInt) { a = a % b }
0249