0001    //
0002    //  Digits.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    internal protocol BigDigit
BigDigit.swift:36
extension BigDigit {
BigDigit.swift:45
extension UInt64: BigDigit {
BigDigit.swift:50
extension UInt32: BigDigit {
BigDigit.swift:70
extension UInt16: BigDigit {
BigDigit.swift:86
extension UInt8: BigDigit {
BigDigit.swift:104
extension BigDigit {
: UnsignedIntegerType, BitwiseOperationsType, ShiftOperationsType {
0012        init
BigDigit.swift:37
    var upshifted: Self { return self << (Self(Self.width) / 2) }
BigDigit.swift:115
        let high = a * c + mv.high + (mo ? Self(1).upshifted : 0) + (lo ? 1 : 0)
BigDigit.swift:160
        let z = Self(v.leadingZeroes)
BigDigit.swift:161
        let w = Self(Self.width) - z
(_ v: Int)
0013    
0014        @warn_unused_result
0015        static func digitsFromUIntMax(i: UIntMax) -> [Self]
0016    
0017        @warn_unused_result
0018        static func fullMultiply(x: Self, _ y: Self) -> (high: Self, low: Self)
0019    
0020        @warn_unused_result
0021        static func fullDivide(xh: Self, _ xl: Self, _ y: Self) -> (div: Self, mod: Self)
0022    
0023        static var max: Self { get }
0024        static var width
BigDigit.swift:37
    var upshifted: Self { return self << (Self(Self.width) / 2) }
BigDigit.swift:161
        let w = Self(Self.width) - z
: Int { get }
0025    
0026        /// The number of leading zero bits in the binary representation of this digit.
0027        var leadingZeroes
BigDigit.swift:160
        let z = Self(v.leadingZeroes)
: Int { get }
0028        /// The number of trailing zero bits in the binary representation of this digit.
0029        var trailingZeroes: Int { get }
0030    
0031        var low
BigDigit.swift:114
        let (low, lo) = Self.addWithOverflow(b * d, mv.low.upshifted)
BigDigit.swift:154
            let r = Self(high: uh.low, low: ul) &- q &* v
: Self { get }
0032        var high
BigDigit.swift:40
        assert(low.high == 0 && high.high == 0)
BigDigit.swift:40
        assert(low.high == 0 && high.high == 0)
BigDigit.swift:115
        let high = a * c + mv.high + (mo ? Self(1).upshifted : 0) + (lo ? 1 : 0)
BigDigit.swift:140
            if q.high == 0 && p <= r.upshifted | ul { return (q, ()) }
BigDigit.swift:141
            if (r + vn1).high != 0 { return (q - 1, ()) }
BigDigit.swift:142
            if (q - 1).high == 0 && (p - vn0) <= Self(high: r + vn1, low: ul) { return (q - 1, ()) }
BigDigit.swift:143
            assert((r + 2 * vn1).high != 0 || p - 2 * vn0 <= Self(high: r + 2 * vn1, low: ul))
: Self { get }
0033        var split
BigDigit.swift:108
        let (a, b) = x.split
BigDigit.swift:109
        let (c, d) = y.split
BigDigit.swift:134
            let (vn1, vn0) = vn.split
BigDigit.swift:166
        let (un1, un0) = un10.split
: (high: Self, low: Self) { get }
0034    }
0035    
0036    extension BigDigit {
0037        var upshifted
BigDigit.swift:41
        self = high.upshifted | low
BigDigit.swift:114
        let (low, lo) = Self.addWithOverflow(b * d, mv.low.upshifted)
BigDigit.swift:115
        let high = a * c + mv.high + (mo ? Self(1).upshifted : 0) + (lo ? 1 : 0)
BigDigit.swift:140
            if q.high == 0 && p <= r.upshifted | ul { return (q, ()) }
: Self { return self << (Self(Self.width) / 2) }
0038    
0039        init
BigDigit.swift:142
            if (q - 1).high == 0 && (p - vn0) <= Self(high: r + vn1, low: ul) { return (q - 1, ()) }
BigDigit.swift:143
            assert((r + 2 * vn1).high != 0 || p - 2 * vn0 <= Self(high: r + 2 * vn1, low: ul))
BigDigit.swift:154
            let r = Self(high: uh.low, low: ul) &- q &* v
BigDigit.swift:174
        let div = Self(high: q1, low: q0)
(high: Self, low: Self) {
0040            assert(low.high == 0 && high.high == 0)
0041            self = high.upshifted | low
0042        }
0043    }
0044    
0045    extension UInt64: BigDigit {
0046        @warn_unused_result
0047        internal static func digitsFromUIntMax
BigUInt.swift:62
        self.init(Digit.digitsFromUIntMax(integer.toUIntMax()))
(i: UIntMax) -> [UInt64] { return [i] }
0048    }
0049    
0050    extension UInt32: BigDigit {
0051        @warn_unused_result
0052        internal static func digitsFromUIntMax(i: UIntMax) -> [UInt32] { return [UInt32(i.low), UInt32(i.high)] }
0053    
0054        // Somewhat surprisingly, these specializations do not help make UInt32 reach UInt64's performance.
0055        // (They are 4-42% faster in benchmarks, but UInt64 is 2-3 times faster still.)
0056        @warn_unused_result
0057        internal static func fullMultiply(x: UInt32, _ y: UInt32) -> (high: UInt32, low: UInt32) {
0058            let p = UInt64(x) * UInt64(y)
0059            return (UInt32(p.high), UInt32(p.low))
0060        }
0061        @warn_unused_result 
0062        internal static func fullDivide(xh: UInt32, _ xl: UInt32, _ y: UInt32) -> (div: UInt32, mod: UInt32) {
0063            let x = UInt64(xh) << 32 + UInt64(xl)
0064            let div = x / UInt64(y)
0065            let mod = x % UInt64(y)
0066            return (UInt32(div), UInt32(mod))
0067        }
0068    }
0069    
0070    extension UInt16: BigDigit {
0071        @warn_unused_result
0072        internal static func digitsFromUIntMax(i: UIntMax) -> [UInt16] {
0073            var digits = Array<UInt16>()
0074            var remaining = i
0075            var width = UIntMax.width - remaining.leadingZeroes
0076            while width >= 16 {
0077                digits.append(UInt16(remaining & UIntMax(UInt16.max)))
0078                remaining >>= 16
0079                width -= 16
0080            }
0081            digits.append(UInt16(remaining))
0082            return digits
0083        }
0084    }
0085    
0086    extension UInt8: BigDigit {
0087        @warn_unused_result
0088        internal static func digitsFromUIntMax(i: UIntMax) -> [UInt8] {
0089            var digits = Array<UInt8>()
0090            var remaining = i
0091            var width = UIntMax.width - remaining.leadingZeroes
0092            while width >= 8 {
0093                digits.append(UInt8(remaining & UIntMax(UInt8.max)))
0094                remaining >>= 8
0095                width -= 8
0096            }
0097            digits.append(UInt8(remaining))
0098            return digits
0099        }
0100    }
0101    
0102    //MARK: Full-width multiplication and division
0103    
0104    extension BigDigit {
0105        /// Return a tuple with the high and low digits of the product of `x` and `y`.
0106        @warn_unused_result
0107        internal static func fullMultiply
BigUInt Division.swift:110
            let (ph, pl) = Digit.fullMultiply(q, y.1)
BigUInt Multiplication.swift:25
            let (h, l) = Digit.fullMultiply(self[i], y)
BigUInt Multiplication.swift:59
            let (h, l) = Digit.fullMultiply(x[xi], y)
(x: Self, _ y: Self) -> (high: Self, low: Self) {
0108            let (a, b) = x.split
0109            let (c, d) = y.split
0110    
0111            // We don't have a full-width multiplication, so we build it out of four half-width multiplications.
0112            // x * y = ac * HH + (ad + bc) * H + bd where H = 2^(n/2)
0113            let (mv, mo) = Self.addWithOverflow(a * d, b * c)
0114            let (low, lo) = Self.addWithOverflow(b * d, mv.low.upshifted)
0115            let high = a * c + mv.high + (mo ? Self(1).upshifted : 0) + (lo ? 1 : 0)
0116            return (high, low)
0117        }
0118    
0119        /// Divide the two-digit number `(u1, u0)` by a single digit `v` and return the quotient and remainder.
0120        ///
0121        /// - Requires: `u1 < v`, so that the result will fit in a single digit.
0122        /// - Complexity: O(1) with 2 divisions, 6 multiplications and ~12 or so additions/subtractions.
0123        @warn_unused_result
0124        internal static func fullDivide
BigUInt Division.swift:28
            let q = Digit.fullDivide(remainder, u, y)
BigUInt Division.swift:104
                let (d, m) = Digit.fullDivide(x.0, x.1, y.0)
(u1: Self, _ u0: Self, _ v: Self) -> (div: Self, mod: Self) {
0125            // Division is complicated; doing it with single-digit operations is maddeningly complicated.
0126            // This is a Swift adaptation for "divlu2" in Hacker's Delight,
0127            // which is in turn a C adaptation of Knuth's Algorithm D (TAOCP vol 2, 4.3.1).
0128            precondition(u1 < v)
0129    
0130            /// Find the half-digit quotient in `(uh, ul) / vn`, which must be normalized.
0131            ///
0132            /// - Requires: uh < vn && ul.high == 0 && vn.width = width(Digit)
0133            func quotient(uh: Self, _ ul: Self, _ vn: Self) -> (Self, ()) { // Strange return type is workaround for compiler bug
0134                let (vn1, vn0) = vn.split
0135                let q = uh / vn1 // Approximated quotient.
0136                let r = uh - q * vn1 // Remainder, less than vn1
0137                let p = q * vn0
0138                // q is often already correct, but sometimes the approximation overshoots by at most 2.
0139                // The code that follows checks for this while being careful to only perform single-digit operations.
0140                if q.high == 0 && p <= r.upshifted | ul { return (q, ()) }
0141                if (r + vn1).high != 0 { return (q - 1, ()) }
0142                if (q - 1).high == 0 && (p - vn0) <= Self(high: r + vn1, low: ul) { return (q - 1, ()) }
0143                assert((r + 2 * vn1).high != 0 || p - 2 * vn0 <= Self(high: r + 2 * vn1, low: ul))
0144                return (q - 2, ())
0145            }
0146            /// Divide 3 half-digits by 2 half-digits to get a half-digit quotient and a full-digit remainder.
0147            ///
0148            /// - Requires: uh < vn && ul.high == 0 && vn.width = width(Digit)
0149            func divmod(uh: Self, _ ul: Self, _ v: Self) -> (div: Self, mod: Self) {
0150                let q = quotient(uh, ul, v).0
0151                // Note that `uh.low` masks off a couple of bits, and `q * v` and the
0152                // subtraction are likely to overflow. Despite this, the end result (remainder) will
0153                // still be correct and it will fit inside a single (full) Digit.
0154                let r = Self(high: uh.low, low: ul) &- q &* v
0155                assert(r < v)
0156                return (q, r)
0157            }
0158    
0159            // Normalize u and v such that v has no leading zeroes.
0160            let z = Self(v.leadingZeroes)
0161            let w = Self(Self.width) - z
0162            let vn = v << z
0163    
0164            let un32 = (z == 0 ? u1 : (u1 << z) | (u0 >> w)) // No bits are lost
0165            let un10 = u0 << z
0166            let (un1, un0) = un10.split
0167    
0168            // Divide `(un32,un10)` by `vn`, splitting the full 4/2 division into two 3/2 ones.
0169            let (q1, un21) = divmod(un32, un1, vn)
0170            let (q0, rn) = divmod(un21, un0, vn)
0171    
0172            // Undo normalization of the remainder and combine the two halves of the quotient.
0173            let mod = rn >> z
0174            let div = Self(high: q1, low: q0)
0175            return (div, mod)
0176        }
0177    }
0178