0001    //
0002    //  BigUInt Multiplication.swift
0003    //  BigInt
0004    //
0005    //  Created by Károly Lőrentey on 2016-01-03.
0006    //  Copyright © 2016 Károly Lőrentey. All rights reserved.
0007    //
0008    
0009    import Foundation
0010    
0011    extension BigUInt {
0012    
0013        //MARK: Multiplication
0014    
0015        /// Multiply this big integer by a single digit, and store the result in place of the original big integer.
0016        ///
0017        /// - Complexity: O(count)
0018        public mutating func multiplyInPlaceByDigitBigUInt Multiplication.swift:39         r.multiplyInPlaceByDigit(y)
BigUInt Radix Conversion.swift:70                 self.multiplyInPlaceByDigit(power)(y: Digit) {
0019            guard y != 0 else { self = 0; return }
0020            guard y != 1 else { return }
0021            lift()
0022            var carry: Digit = 0
0023            let c = self.count
0024            for i in 0..<c {
0025                let (h, l) = Digit.fullMultiply(self[i], y)
0026                let (low, o) = Digit.addWithOverflow(l, carry)
0027                self[i] = low
0028                carry = (o ? h + 1 : h)
0029            }
0030            self[c] = carry
0031        }
0032    
0033        /// Multiply this big integer by a single digit, and return the result.
0034        ///
0035        /// - Complexity: O(count)
0036        @warn_unused_result
0037        public func multiplyByDigitBigUInt Division.swift:149             let product = divisor.multiplyByDigit(q)
BigUInt Multiplication.swift:106     if yc == 1 { return x.multiplyByDigit(y[0]) }
BigUInt Multiplication.swift:107     if xc == 1 { return y.multiplyByDigit(x[0]) }(y: Digit) -> BigUInt {
0038            var r = self
0039            r.multiplyInPlaceByDigit(y)
0040            return r
0041        }
0042    
0043        /// Multiply `x` by `y`, and add the result to this integer, optionally shifted `shift` digits to the left.
0044        ///
0045        /// - Note: This is the fused multiply/shift/add operation; it is more efficient than doing the components
0046        ///   individually. (The fused operation doesn't need to allocate space for temporary big integers.)
0047        /// - Returns: `self` is set to `self + (x * y) << (shift * 2^Digit.width)`
0048        /// - Complexity: O(count)
0049        public mutating func multiplyAndAddInPlaceBigUInt Multiplication.swift:115             result.multiplyAndAddInPlace(left, right[i], shift: i)(x: BigUInt, _ y: Digit, shift: Int = 0) {
0050            precondition(shift >= 0)
0051            guard y != 0 && x.count > 0 else { return }
0052            guard y != 1 else { self.addInPlace(x, shift: shift); return }
0053            lift()
0054            var mulCarry: Digit = 0
0055            var addCarry = false
0056            let xc = x.count
0057            var xi = 0
0058            while xi < xc || addCarry || mulCarry > 0 {
0059                let (h, l) = Digit.fullMultiply(x[xi], y)
0060                let (low, o) = Digit.addWithOverflow(l, mulCarry)
0061                mulCarry = (o ? h + 1 : h)
0062    
0063                let ai = shift + xi
0064                let (sum1, so1) = Digit.addWithOverflow(self[ai], low)
0065                if addCarry {
0066                    let (sum2, so2) = Digit.addWithOverflow(sum1, 1)
0067                    self[ai] = sum2
0068                    addCarry = so1 || so2
0069                }
0070                else {
0071                    self[ai] = sum1
0072                    addCarry = so1
0073                }
0074                xi += 1
0075            }
0076        }
0077    
0078        /// Multiply this integer by `y` and return the result.
0079        ///
0080        /// - Note: This uses the naive O(n^2) multiplication algorithm unless both arguments have more than
0081        ///   `BigUInt.directMultiplicationLimit` digits.
0082        /// - Complexity: O(n^log2(3))
0083        @warn_unused_result
0084        public func multiply(y: BigUInt) -> BigUInt {
0085            // This method is mostly defined for symmetry with the rest of the arithmetic operations.
0086            return self * y
0087        }
0088    
0089        /// Multiplication switches to an asymptotically better recursive algorithm when arguments have more digits than this limit.
0090        public static var directMultiplicationLimitBigUInt Multiplication.swift:109     if min(xc, yc) <= BigUInt.directMultiplicationLimit {: Int = 1024
0091    }
0092    
0093    //MARK: Multiplication
0094    
0095    /// Multiply `a` by `b` and return the result.
0096    ///
0097    /// - Note: This uses the naive O(n^2) multiplication algorithm unless both arguments have more than
0098    ///   `BigUInt.directMultiplicationLimit` digits.
0099    /// - Complexity: O(n^log2(3))
0100    @warn_unused_result
0101    public func *(x: BigUInt, y: BigUInt) -> BigUInt {
0102        let xc = x.count
0103        let yc = y.count
0104        if xc == 0 { return BigUInt() }
0105        if yc == 0 { return BigUInt() }
0106        if yc == 1 { return x.multiplyByDigit(y[0]) }
0107        if xc == 1 { return y.multiplyByDigit(x[0]) }
0108    
0109        if min(xc, yc) <= BigUInt.directMultiplicationLimit {
0110            // Long multiplication.
0111            let left = (xc < yc ? y : x)
0112            let right = (xc < yc ? x : y)
0113            var result = BigUInt()
0114            for i in (0 ..< right.count).reverse() {
0115                result.multiplyAndAddInPlace(left, right[i], shift: i)
0116            }
0117            return result
0118        }
0119    
0120        if yc < xc {
0121            let (xh, xl) = x.split
0122            var r = xl * y
0123            r.addInPlace(xh * y, shift: x.middleIndex)
0124            return r
0125        }
0126        else if xc < yc {
0127            let (yh, yl) = y.split
0128            var r = yl * x
0129            r.addInPlace(yh * x, shift: y.middleIndex)
0130            return r
0131        }
0132    
0133        let shift = x.middleIndex
0134    
0135        // Karatsuba multiplication:
0136        // x * y = <a,b> * <c,d> = <ac, ac + bd - (a-b)(c-d), bd> (ignoring carry)
0137        let (a, b) = x.split
0138        let (c, d) = y.split
0139    
0140        let high = a * c
0141        let low = b * d
0142        let xp = a >= b
0143        let yp = c >= d
0144        let xm = (xp ? a - b : b - a)
0145        let ym = (yp ? c - d : d - c)
0146        let m = xm * ym
0147    
0148        var r = low
0149        r.addInPlace(high, shift: 2 * shift)
0150        r.addInPlace(low, shift: shift)
0151        r.addInPlace(high, shift: shift)
0152        if xp == yp {
0153            r.subtractInPlace(m, shift: shift)
0154        }
0155        else {
0156            r.addInPlace(m, shift: shift)
0157        }
0158        return r
0159    }
0160    
0161    /// Multiply `a` by `b` and store the result in `a`.
0162    public func *=(inout a: BigUInt, b: BigUInt) {
0163        a = a * b
0164    }
0165    
0166
BigUInt Multiplication.swift:39	r.multiplyInPlaceByDigit(y)
BigUInt Radix Conversion.swift:70	self.multiplyInPlaceByDigit(power)
BigUInt Division.swift:149	let product = divisor.multiplyByDigit(q)
BigUInt Multiplication.swift:106	if yc == 1 { return x.multiplyByDigit(y[0]) }
BigUInt Multiplication.swift:107	if xc == 1 { return y.multiplyByDigit(x[0]) }