BigUInt

public struct BigUInt : UnsignedInteger
extension BigUInt: Comparable
extension BigUInt: Hashable
extension BigUInt: ExpressibleByIntegerLiteral
extension BigUInt: ExpressibleByStringLiteral
extension BigUInt: CustomPlaygroundDisplayConvertible

An arbitary precision unsigned integer type, also known as a “big integer”.

Operations on big integers never overflow, but they may take a long time to execute. The amount of memory (and address space) available is the only constraint to the magnitude of these numbers.

This particular big integer type uses base-2^64 digits to represent integers; you can think of it as a wrapper around Array<UInt64>. (In fact, BigUInt only uses an array if there are more than two digits.)

  • The type representing a digit in BigUInt‘s underlying number system.

    Declaration

    Swift

    public typealias Word = UInt

  • The storage variants of a BigUInt.

    See more

    Declaration

    Swift

    enum Kind

  • Undocumented

    Declaration

    Swift

    internal fileprivate(set) var kind: Kind { get }

  • Undocumented

    Declaration

    Swift

    internal fileprivate(set) var storage: [Word] { get }

  • Initializes a new BigUInt with value 0.

    Declaration

    Swift

    public init()

  • Undocumented

    Declaration

    Swift

    internal init(word: Word)

  • Undocumented

    Declaration

    Swift

    internal init(low: Word, high: Word)

  • Initializes a new BigUInt with the specified digits. The digits are ordered from least to most significant.

    Declaration

    Swift

    public init(words: [Word])

  • Undocumented

    Declaration

    Swift

    internal init(words: [Word], from startIndex: Int, to endIndex: Int)

Addition

  • Add word to this integer in place. word is shifted shift words to the left before being added.

    Complexity

    O(max(count, shift))

    Declaration

    Swift

    internal mutating func addWord(_ word: Word, shiftedBy shift: Int = 0)

  • Add the digit d to this integer and return the result. d is shifted shift words to the left before being added.

    Complexity

    O(max(count, shift))

    Declaration

    Swift

    internal func addingWord(_ word: Word, shiftedBy shift: Int = 0) -> BigUInt

  • Add b to this integer in place. b is shifted shift words to the left before being added.

    Complexity

    O(max(count, b.count + shift))

    Declaration

    Swift

    internal mutating func add(_ b: BigUInt, shiftedBy shift: Int = 0)

  • Add b to this integer and return the result. b is shifted shift words to the left before being added.

    Complexity

    O(max(count, b.count + shift))

    Declaration

    Swift

    internal func adding(_ b: BigUInt, shiftedBy shift: Int = 0) -> BigUInt

  • Increment this integer by one. If shift is non-zero, it selects the word that is to be incremented.

    Complexity

    O(count + shift)

    Declaration

    Swift

    internal mutating func increment(shiftedBy shift: Int = 0)

  • Add a and b together and return the result.

    Complexity

    O(max(a.count, b.count))

    Declaration

    Swift

    public static func + (a: BigUInt, b: BigUInt) -> BigUInt

  • Add a and b together, and store the sum in a.

    Complexity

    O(max(a.count, b.count))

    Declaration

    Swift

    public static func += (a: inout BigUInt, b: BigUInt)

  • Declaration

    Swift

    public static var isSigned: Bool { get }

  • Return true iff this integer is zero.

    Complexity

    O(1)

    Declaration

    Swift

    public var isZero: Bool { get }

  • Returns 1 if this value is, positive; otherwise, 0.

    Declaration

    Swift

    public func signum() -> BigUInt

    Return Value

    The sign of this number, expressed as an integer of the same type.

  • Undocumented

    Declaration

    Swift

    mutating func ensureArray()

  • Undocumented

    Declaration

    Swift

    var capacity: Int { get }

  • Undocumented

    Declaration

    Swift

    mutating func reserveCapacity(_ minimumCapacity: Int)

  • Gets rid of leading zero digits in the digit array and converts slices into inline digits when possible.

    Declaration

    Swift

    internal mutating func normalize()

  • Set this integer to 0 without releasing allocated storage capacity (if any).

    Declaration

    Swift

    mutating func clear()

  • Set this integer to value by copying its digits without releasing allocated storage capacity (if any).

    Declaration

    Swift

    mutating func load(_ value: BigUInt)

Collection-like members

  • The number of digits in this integer, excluding leading zero digits.

    Declaration

    Swift

    var count: Int { get }

  • Get or set a digit at a given index.

    Note

    Unlike a normal collection, it is OK for the index to be greater than or equal to endIndex. The subscripting getter returns zero for indexes beyond the most significant digit. Setting these extended digits automatically appends new elements to the underlying digit array.

    Requires

    index >= 0

    Complexity

    The getter is O(1). The setter is O(1) if the conditions below are true; otherwise it’s O(count).
    • The integer’s storage is not shared with another integer
    • The integer wasn’t created as a slice of another integer
    • index < count

    Declaration

    Swift

    subscript(index: Int) -> Word { get set }

  • Returns an integer built from the digits of this integer in the given range.

    Declaration

    Swift

    internal func extract(_ bounds: Range<Int>) -> BigUInt

  • Undocumented

    Declaration

    Swift

    internal func extract<Bounds>(_ bounds: Bounds) -> BigUInt where Bounds : RangeExpression, Bounds.Bound == Int

  • Undocumented

    Declaration

    Swift

    internal mutating func shiftRight(byWords amount: Int)

  • Undocumented

    Declaration

    Swift

    internal mutating func shiftLeft(byWords amount: Int)

Low and High

  • Split this integer into a high-order and a low-order part.

    Requires

    count > 1

    Complexity

    Typically O(1), but O(count) in the worst case, because high-order zero digits need to be removed after the split.

    Declaration

    Swift

    internal var split: (high: BigUInt, low: BigUInt) { get }

    Return Value

    (low, high) such that

    • self == low.add(high, shiftedBy: middleIndex)
    • high.width <= floor(width / 2)
    • low.width <= ceil(width / 2)

  • Index of the digit at the middle of this integer.

    Declaration

    Swift

    internal var middleIndex: Int { get }

    Return Value

    The index of the digit that is least significant in self.high.

  • low

    The low-order half of this BigUInt.

    Requires

    count > 1

    Declaration

    Swift

    internal var low: BigUInt { get }

    Return Value

    self[0 ..< middleIndex]

  • The high-order half of this BigUInt.

    Requires

    count > 1

    Declaration

    Swift

    internal var high: BigUInt { get }

    Return Value

    self[middleIndex ..< count]

Bitwise Operations

  • Return the ones’ complement of a.

    Complexity

    O(a.count)

    Declaration

    Swift

    public prefix static func ~ (a: BigUInt) -> BigUInt

  • Calculate the bitwise OR of a and b, and store the result in a.

    Complexity

    O(max(a.count, b.count))

    Declaration

    Swift

    public static func |= (a: inout BigUInt, b: BigUInt)

  • Calculate the bitwise AND of a and b and return the result.

    Complexity

    O(max(a.count, b.count))

    Declaration

    Swift

    public static func &= (a: inout BigUInt, b: BigUInt)

  • Calculate the bitwise XOR of a and b and return the result.

    Complexity

    O(max(a.count, b.count))

    Declaration

    Swift

    public static func ^= (a: inout BigUInt, b: BigUInt)

Comparison

  • Compare a to b and return an NSComparisonResult indicating their order.

    Complexity

    O(count)

    Declaration

    Swift

    public static func compare(_ a: BigUInt, _ b: BigUInt) -> ComparisonResult

  • Return true iff a is equal to b.

    Complexity

    O(count)

    Declaration

    Swift

    public static func == (a: BigUInt, b: BigUInt) -> Bool

  • Return true iff a is less than b.

    Complexity

    O(count)

    Declaration

    Swift

    public static func < (a: BigUInt, b: BigUInt) -> Bool

NSData Conversion

  • Initialize a BigInt from bytes accessed from an UnsafeRawBufferPointer

    Declaration

    Swift

    public init(_ buffer: UnsafeRawBufferPointer)

  • Initializes an integer from the bits stored inside a piece of Data. The data is assumed to be in network (big-endian) byte order.

    Declaration

    Swift

    public init(_ data: Data)

  • Return a Data value that contains the base-256 representation of this integer, in network (big-endian) byte order.

    Declaration

    Swift

    public func serialize() -> Data

Division

  • Divide this integer by the word y, leaving the quotient in its place and returning the remainder.

    Requires

    y > 0

    Complexity

    O(count)

    Declaration

    Swift

    internal mutating func divide(byWord y: Word) -> Word

  • Divide this integer by the word y and return the resulting quotient and remainder.

    Requires

    y > 0

    Complexity

    O(x.count)

    Declaration

    Swift

    internal func quotientAndRemainder(dividingByWord y: Word) -> (quotient: BigUInt, remainder: Word)

    Return Value

    (quotient, remainder) where quotient = floor(x/y), remainder = x - quotient * y

  • Divide x by y, putting the quotient in x and the remainder in y. Reusing integers like this reduces the number of allocations during the calculation.

    Declaration

    Swift

    static func divide(_ x: inout BigUInt, by y: inout BigUInt)

  • Divide x by y, putting the remainder in x.

    Declaration

    Swift

    mutating func formRemainder(dividingBy y: BigUInt, normalizedBy shift: Int)

  • Divide this integer by y and return the resulting quotient and remainder.

    Requires

    y > 0

    Complexity

    O(count^2)

    Declaration

    Swift

    public func quotientAndRemainder(dividingBy y: BigUInt) -> (quotient: BigUInt, remainder: BigUInt)

    Return Value

    (quotient, remainder) where quotient = floor(self/y), remainder = self - quotient * y

  • Divide x by y and return the quotient.

    Note

    Use divided(by:) if you also need the remainder.

    Declaration

    Swift

    public static func / (x: BigUInt, y: BigUInt) -> BigUInt

  • Divide x by y and return the remainder.

    Note

    Use divided(by:) if you also need the remainder.

    Declaration

    Swift

    public static func % (x: BigUInt, y: BigUInt) -> BigUInt

  • Divide x by y and store the quotient in x.

    Note

    Use divided(by:) if you also need the remainder.

    Declaration

    Swift

    public static func /= (x: inout BigUInt, y: BigUInt)

  • Divide x by y and store the remainder in x.

    Note

    Use divided(by:) if you also need the remainder.

    Declaration

    Swift

    public static func %= (x: inout BigUInt, y: BigUInt)

Exponentiation

  • Returns this integer raised to the power exponent.

    This function calculates the result by successively squaring the base while halving the exponent.

    Note

    This function can be unreasonably expensive for large exponents, which is why exponent is a simple integer value. If you want to calculate big exponents, you’ll probably need to use the modulo arithmetic variant.

    See also

    BigUInt.power(_:, modulus:)

    Complexity

    O((exponent * self.count)^log2(3)) or somesuch. The result may require a large amount of memory, too.

    Declaration

    Swift

    public func power(_ exponent: Int) -> BigUInt

    Return Value

    1 if exponent == 0, otherwise self raised to exponent. (This implies that 0.power(0) == 1.)

  • Returns the remainder of this integer raised to the power exponent in modulo arithmetic under modulus.

    Uses the right-to-left binary method.

    Complexity

    O(exponent.count * modulus.count^log2(3)) or somesuch

    Declaration

    Swift

    public func power(_ exponent: BigUInt, modulus: BigUInt) -> BigUInt

  • Declaration

    Swift

    public init?<T>(exactly source: T) where T : BinaryFloatingPoint

  • Declaration

    Swift

    public init<T>(_ source: T) where T : BinaryFloatingPoint

Hashing

  • Append this BigUInt to the specified hasher.

    Declaration

    Swift

    public func hash(into hasher: inout Hasher)

  • Declaration

    Swift

    public init?<T>(exactly source: T) where T : BinaryInteger

  • Declaration

    Swift

    public init<T>(_ source: T) where T : BinaryInteger

  • Declaration

    Swift

    public init<T>(truncatingIfNeeded source: T) where T : BinaryInteger

  • Declaration

    Swift

    public init<T>(clamping source: T) where T : BinaryInteger

  • Initialize a new big integer from an integer literal.

    Declaration

    Swift

    public init(integerLiteral value: UInt64)

Multiplication

  • Multiply this big integer by a single word, and store the result in place of the original big integer.

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func multiply(byWord y: Word)

  • Multiply this big integer by a single Word, and return the result.

    Complexity

    O(count)

    Declaration

    Swift

    public func multiplied(byWord y: Word) -> BigUInt

  • Multiply x by y, and add the result to this integer, optionally shifted shift words to the left.

    Note

    This is the fused multiply/shift/add operation; it is more efficient than doing the components individually. (The fused operation doesn’t need to allocate space for temporary big integers.)

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func multiplyAndAdd(_ x: BigUInt, _ y: Word, shiftedBy shift: Int = 0)

    Return Value

    self is set to self + (x * y) << (shift * 2^Word.bitWidth)

  • Multiply this integer by y and return the result.

    Note

    This uses the naive O(n^2) multiplication algorithm unless both arguments have more than BigUInt.directMultiplicationLimit words.

    Complexity

    O(n^log2(3))

    Declaration

    Swift

    public func multiplied(by y: BigUInt) -> BigUInt

  • Multiplication switches to an asymptotically better recursive algorithm when arguments have more words than this limit.

    Declaration

    Swift

    public static var directMultiplicationLimit: Int

  • Multiply a by b and return the result.

    Note

    This uses the naive O(n^2) multiplication algorithm unless both arguments have more than BigUInt.directMultiplicationLimit words.

    Complexity

    O(n^log2(3))

    Declaration

    Swift

    public static func * (x: BigUInt, y: BigUInt) -> BigUInt

  • Multiply a by b and store the result in a.

    Declaration

    Swift

    public static func *= (a: inout BigUInt, b: BigUInt)

Shift Operators

  • Undocumented

    Declaration

    Swift

    internal func shiftedLeft(by amount: Word) -> BigUInt

  • Undocumented

    Declaration

    Swift

    internal mutating func shiftLeft(by amount: Word)

  • Undocumented

    Declaration

    Swift

    internal func shiftedRight(by amount: Word) -> BigUInt

  • Undocumented

    Declaration

    Swift

    internal mutating func shiftRight(by amount: Word)

  • Undocumented

    Declaration

    Swift

    public static func >>= <Other>(lhs: inout BigUInt, rhs: Other) where Other : BinaryInteger

  • Undocumented

    Declaration

    Swift

    public static func <<= <Other>(lhs: inout BigUInt, rhs: Other) where Other : BinaryInteger

  • Undocumented

    Declaration

    Swift

    public static func >> <Other>(lhs: BigUInt, rhs: Other) -> BigUInt where Other : BinaryInteger

  • Undocumented

    Declaration

    Swift

    public static func << <Other>(lhs: BigUInt, rhs: Other) -> BigUInt where Other : BinaryInteger

String Conversion

  • Initialize a big integer from an ASCII representation in a given radix. Numerals above 9 are represented by letters from the English alphabet.

    Requires

    radix > 1 && radix < 36

    Declaration

    Swift

    public init?<S>(_ text: S, radix: Int = 10) where S : StringProtocol

    Return Value

    The integer represented by text, or nil if text contains a character that does not represent a numeral in radix.

  • Initialize a new big integer from a Unicode scalar. The scalar must represent a decimal digit.

    Declaration

    Swift

    public init(unicodeScalarLiteral value: UnicodeScalar)

  • Initialize a new big integer from an extended grapheme cluster. The cluster must consist of a decimal digit.

    Declaration

    Swift

    public init(extendedGraphemeClusterLiteral value: String)

  • Initialize a new big integer from a decimal number represented by a string literal of arbitrary length. The string must contain only decimal digits.

    Declaration

    Swift

    public init(stringLiteral value: StringLiteralType)

  • Return the playground quick look representation of this integer.

    Declaration

    Swift

    public var playgroundDescription: Any { get }

Subtraction

  • Subtract word from this integer in place, returning a flag indicating if the operation caused an arithmetic overflow. word is shifted shift words to the left before being subtracted.

    Note

    If the result indicates an overflow, then self becomes the two’s complement of the absolute difference.

    Complexity

    O(count)

    Declaration

    Swift

    internal mutating func subtractWordReportingOverflow(_ word: Word, shiftedBy shift: Int = 0) -> Bool

  • Subtract word from this integer, returning the difference and a flag that is true if the operation caused an arithmetic overflow. word is shifted shift words to the left before being subtracted.

    Note

    If overflow is true, then the returned value is the two’s complement of the absolute difference.

    Complexity

    O(count)

    Declaration

    Swift

    internal func subtractingWordReportingOverflow(_ word: Word, shiftedBy shift: Int = 0) -> (partialValue: BigUInt, overflow: Bool)

  • Subtract a digit d from this integer in place. d is shifted shift digits to the left before being subtracted.

    Requires

    self >= d * 2^shift

    Complexity

    O(count)

    Declaration

    Swift

    internal mutating func subtractWord(_ word: Word, shiftedBy shift: Int = 0)

  • Subtract a digit d from this integer and return the result. d is shifted shift digits to the left before being subtracted.

    Requires

    self >= d * 2^shift

    Complexity

    O(count)

    Declaration

    Swift

    internal func subtractingWord(_ word: Word, shiftedBy shift: Int = 0) -> BigUInt

  • Subtract other from this integer in place, and return a flag indicating if the operation caused an arithmetic overflow. other is shifted shift digits to the left before being subtracted.

    Note

    If the result indicates an overflow, then self becomes the twos’ complement of the absolute difference.

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func subtractReportingOverflow(_ b: BigUInt, shiftedBy shift: Int = 0) -> Bool

  • Subtract other from this integer, returning the difference and a flag indicating arithmetic overflow. other is shifted shift digits to the left before being subtracted.

    Note

    If overflow is true, then the result value is the twos’ complement of the absolute value of the difference.

    Complexity

    O(count)

    Declaration

    Swift

    public func subtractingReportingOverflow(_ other: BigUInt, shiftedBy shift: Int) -> (partialValue: BigUInt, overflow: Bool)

  • Subtracts other from self, returning the result and a flag indicating arithmetic overflow.

    Note

    When the operation overflows, then partialValue is the twos’ complement of the absolute value of the difference.

    Complexity

    O(count)

    Declaration

    Swift

    public func subtractingReportingOverflow(_ other: BigUInt) -> (partialValue: BigUInt, overflow: Bool)

  • Subtract other from this integer in place. other is shifted shift digits to the left before being subtracted.

    Requires

    self >= other * 2^shift

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func subtract(_ other: BigUInt, shiftedBy shift: Int = 0)

  • Subtract b from this integer, and return the difference. b is shifted shift digits to the left before being subtracted.

    Requires

    self >= b * 2^shift

    Complexity

    O(count)

    Declaration

    Swift

    public func subtracting(_ other: BigUInt, shiftedBy shift: Int = 0) -> BigUInt

  • Decrement this integer by one.

    Requires

    !isZero

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func decrement(shiftedBy shift: Int = 0)

  • Subtract b from a and return the result.

    Requires

    a >= b

    Complexity

    O(a.count)

    Declaration

    Swift

    public static func - (a: BigUInt, b: BigUInt) -> BigUInt

  • Subtract b from a and store the result in a.

    Requires

    a >= b

    Complexity

    O(a.count)

    Declaration

    Swift

    public static func -= (a: inout BigUInt, b: BigUInt)

  • Undocumented

    Declaration

    Swift

    public subscript(bitAt index: Int) -> Bool { get set }

  • The minimum number of bits required to represent this integer in binary.

    Complexity

    O(1)

    Declaration

    Swift

    public var bitWidth: Int { get }

    Return Value

    floor(log2(2 * self + 1))

  • The number of leading zero bits in the binary representation of this integer in base 2^(Word.bitWidth). This is useful when you need to normalize a BigUInt such that the top bit of its most significant word is 1.

    Note

    0 is considered to have zero leading zero bits.

    See also

    width

    Complexity

    O(1)

    Declaration

    Swift

    public var leadingZeroBitCount: Int { get }

    Return Value

    A value in 0...(Word.bitWidth - 1).

  • The number of trailing zero bits in the binary representation of this integer.

    Note

    0 is considered to have zero trailing zero bits.

    Complexity

    O(count)

    Declaration

    Swift

    public var trailingZeroBitCount: Int { get }

    Return Value

    A value in 0...width.

  • See more

    Declaration

    Swift

    public struct Words : RandomAccessCollection

  • Declaration

    Swift

    public var words: Words { get }

  • Undocumented

    Declaration

    Swift

    public init<Words>(words: Words) where Words : Sequence, Words.Element == UInt