BigUInt

public struct BigUInt

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

Operations on big integers never overflow, but they might 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 implements a mutable collection of its UInt64 digits, with the digit at index 0 being the least significant.

To make memory management simple, BigUInt allows you to subscript it with out-of-bounds indexes: the subscript getter zero-extends the digit sequence, while the subscript setter automatically extends the underlying storage when necessary:

var number = BigUInt(1)
number[42]                // Not an error, returns 0
number[23] = 1            // Not an error, number is now 2^1472 + 1.

Note that it is rarely a good idea to use big integers as collections; in the vast majority of cases it is much easier to work with the provided high-level methods and operators rather than with raw big digits.

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

    Declaration

    Swift

    public typealias Digit = UIntMax
  • Initializes a new BigUInt with value 0.

    Declaration

    Swift

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

    Declaration

    Swift

    public init(_ digits: [Digit])
  • Initializes a new BigUInt that has the supplied value.

    Declaration

    Swift

    public init<I: UnsignedInteger>(_ integer: I)
  • Initializes a new BigUInt that has the supplied value.

    Requires

    integer >= 0

    Declaration

    Swift

    public init<I: SignedInteger>(_ integer: I)
  • The empty bitset.

    Declaration

    Swift

    public static let allZeros: BigUInt = 0
  • The minimum number of bits required to represent this integer in binary.

    Returns

    floor(log2(2 * self + 1))

    Complexity

    O(1)

    Declaration

    Swift

    public var width: Int

    Return Value

    floor(log2(2 * self + 1))

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

    Note

    0 is considered to have zero leading zero bits.

    Returns

    A value in 0...(Digit.width - 1).

    See also

    width

    Complexity

    O(1)

    Declaration

    Swift

    public var leadingZeroes: Int

    Return Value

    A value in 0...(Digit.width - 1).

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

    Note

    0 is considered to have zero trailing zero bits.

    Returns

    A value in 0...width.

    Complexity

    O(count)

    Declaration

    Swift

    public var trailingZeroes: Int

    Return Value

    A value in 0...width.

  • Return the ones’ complement of a.

    Complexity

    O(a.count)

    Declaration

    Swift

    public static prefix func ~(a: BigUInt) -> BigUInt
  • Calculate the bitwise OR of a and b and return the result.

    Complexity

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

    Declaration

    Swift

    public static func | (a: BigUInt, b: BigUInt) -> 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: BigUInt, b: BigUInt) -> BigUInt
  • Calculate the bitwise OR of a and b and return the result.

    Complexity

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

    Declaration

    Swift

    public static func ^ (a: BigUInt, b: 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 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 XOR 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)
  • Create a big integer consisting of width uniformly distributed random bits.

    Returns

    A big integer less than 1 << width.

    Note

    This function uses arc4random_buf to generate random bits.

    Declaration

    Swift

    public static func randomInteger(withMaximumWidth width: Int) -> BigUInt

    Return Value

    A big integer less than 1 << width.

  • Create a big integer consisting of width-1 uniformly distributed random bits followed by a one bit.

    Returns

    A random big integer whose width is width.

    Note

    This function uses arc4random_buf to generate random bits.

    Declaration

    Swift

    public static func randomInteger(withExactWidth width: Int) -> BigUInt

    Return Value

    A random big integer whose width is width.

  • Create a uniformly distributed random integer that’s less than the specified limit.

    Returns

    A random big integer that is less than limit.

    Note

    This function uses arc4random_buf to generate random bits.

    Declaration

    Swift

    public static func randomIntegerLessThan(_ limit: BigUInt) -> BigUInt

    Return Value

    A random big integer that is less than limit.

  • Returns true iff this integer passes the strong probable prime test for the specified base.

    Declaration

    Swift

    public func isStrongProbablePrime(_ base: BigUInt) -> Bool
  • Returns true if this integer is probably prime. Returns false if this integer is definitely not prime.

    This function performs a probabilistic Miller-Rabin Primality Test, consisting of rounds iterations, each calculating the strong probable prime test for a random base. The number of rounds is 10 by default, but you may specify your own choice.

    To speed things up, the function checks if self is divisible by the first few prime numbers before diving into (slower) Miller-Rabin testing.

    Also, when self is less than 82 bits wide, isPrime does a deterministic test that is guaranteed to return a correct result.

    Declaration

    Swift

    public func isPrime(rounds: Int = 10) -> Bool
  • Subtract a digit d from this integer in place, returning a flag that is true if the operation caused an arithmetic overflow. d is shifted shift digits to the left before being subtracted.

    Note

    If the result is true, then self becomes the two’s complement of the absolute difference.

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func subtractDigitWithOverflow(_ d: Digit, atPosition shift: Int = 0) -> Bool
  • Subtract a digit d from this integer, returning the difference and a flag that is true if the operation caused an arithmetic overflow. d is shifted shift digits 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

    public func subtractingDigitWithOverflow(_ d: Digit, atPosition shift: Int = 0) -> (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

    public mutating func subtractDigit(_ d: Digit, atPosition 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

    public func subtractingDigit(_ d: Digit, atPosition shift: Int = 0) -> BigUInt
  • Subtract b from this integer in place, and return true iff the operation caused an arithmetic overflow. b is shifted shift digits to the left before being subtracted.

    Note

    If the result is true, then self becomes the twos’ complement of the absolute difference.

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func subtractWithOverflow(_ b: BigUInt, atPosition shift: Int = 0) -> Bool
  • Subtract b from this integer, returning the difference and a flag that is true if the operation caused an arithmetic overflow. b 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 subtractingWithOverflow(_ b: BigUInt, atPosition shift: Int = 0) -> (BigUInt, overflow: Bool)
  • Subtract b from this integer in place. b is shifted shift digits to the left before being subtracted.

    Requires

    self >= b * 2^shift

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func subtract(_ b: BigUInt, atPosition 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(_ b: BigUInt, atPosition shift: Int = 0) -> BigUInt
  • Decrement this integer by one.

    Requires

    !isZero

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func decrement(atPosition 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)
  • Subtracts rhs from lhs, returning the result and a Bool that is true iff the operation caused an arithmetic overflow. Overflow is returned if and only if lhs is less than rhs, in which case the result is the twos’ complement of the absolute difference.

    Declaration

    Swift

    public static func subtractWithOverflow(_ lhs: BigUInt, _ rhs: BigUInt) -> (BigUInt, overflow: Bool)
  • Divide this integer by the digit y, leaving the quotient in its place and returning the remainder.

    Requires

    y > 0

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func divide(byDigit y: Digit) -> Digit
  • Divide this integer by the digit y and return the resulting quotient and remainder.

    Requires

    y > 0

    Returns

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

    Complexity

    O(x.count)

    Declaration

    Swift

    public func divided(byDigit y: Digit) -> (quotient: BigUInt, remainder: Digit)

    Return Value

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

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

    Requires

    y > 0

    Returns

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

    Complexity

    O(count^2)

    Declaration

    Swift

    public func divided(by 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)
  • Divide lhs by rhs, returning the quotient. This function never results in an overflow.

    Declaration

    Swift

    public static func divideWithOverflow(_ lhs: BigUInt, _ rhs: BigUInt) -> (BigUInt, overflow: Bool)
  • Divide lhs by rhs, returning the remainder. This function never results in an overflow.

    Declaration

    Swift

    public static func remainderWithOverflow(_ lhs: BigUInt, _ rhs: BigUInt) -> (BigUInt, overflow: Bool)
  • 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)
  • Explicitly convert to IntMax, trapping on overflow.

    Declaration

    Swift

    public func toIntMax() -> IntMax
  • The type representing the iteration interface for the digits in a big integer.

    Declaration

    Swift

    public typealias Iterator = DigitIterator<Digit>
  • The type representing valid indices for subscripting the collection.

    Declaration

    Swift

    public typealias Indices = CountableRange<Int>
  • Big integers can be contiguous digit subranges of another big integer.

    Declaration

    Swift

    public typealias SubSequence = BigUInt
  • 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

    public subscript(index: Int) -> Digit
  • Returns an integer built from the digits of this integer in the given range.

    Declaration

    Swift

    public subscript(bounds: Range<Int>) -> BigUInt
  • The type representing the number of steps between two indices.

    Declaration

    Swift

    public typealias IndexDistance = Int
  • Big integers implement Collection to provide access to their big digits, indexed by integers; a zero index refers to the least significant digit.

    Declaration

    Swift

    public typealias Index = Int
  • Big integers can be contiguous digit subranges of another big integer.

    Declaration

    Swift

    public var indices: Indices
  • The index of the first digit, starting from the least significant. (This is always zero.)

    Declaration

    Swift

    public var startIndex: Int
  • The index of the digit after the most significant digit in this integer.

    Declaration

    Swift

    public var endIndex: Int
  • The number of digits in this integer, excluding leading zero digits.

    Declaration

    Swift

    public var count: Int
  • Return a generator over the digits of this integer, starting at the least significant digit.

    Declaration

    Swift

    public func makeIterator() -> DigitIterator<Digit>
  • Returns the position immediately after the given index.

    Declaration

    Swift

    public func index(after i: Int) -> Int
  • Returns the position immediately before the given index.

    Declaration

    Swift

    public func index(before i: Int) -> Int
  • Replaces the given index with its successor.

    Declaration

    Swift

    public func formIndex(after i: inout Int)
  • Replaces the given index with its predecessor.

    Declaration

    Swift

    public func formIndex(before i: inout Int)
  • Returns an index that is the specified distance from the given index.

    Declaration

    Swift

    public func index(_ i: Int, offsetBy n: Int) -> Int
  • Returns an index that is the specified distance from the given index, unless that distance is beyond a given limiting index.

    Declaration

    Swift

    public func index(_ i: Int, offsetBy n: Int, limitedBy limit: Int) -> Int?
  • Returns the number of steps between two indices.

    Declaration

    Swift

    public func distance(from start: Int, to end: Int) -> Int
  • Adds n to self and returns the result. Traps if the result would be less than zero.

    Declaration

    Swift

    public func advanced(by n: BigInt) -> BigUInt
  • A type that can represent the distance between two values of BigUInt.

    Declaration

    Swift

    public typealias Stride = BigInt
  • Returns the (potentially negative) difference between self and other as a BigInt. Never traps.

    Declaration

    Swift

    public func distance(to other: BigUInt) -> BigInt
  • 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
  • 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

    Parameter

    Parameter text: A string consisting of characters corresponding to numerals in the given radix. (0-9, a-z, A-Z)

    Parameter

    Parameter radix: The base of the number system to use, or 10 if unspecified.

    Returns

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

    Declaration

    Swift

    public init?(_ text: String, radix: Int = 10)

    Return Value

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

  • Return the decimal representation of this integer.

    Declaration

    Swift

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

    Declaration

    Swift

    public init(_ data: Data)
  • Return an NSData instance that contains the base-256 representation of this integer, in network (big-endian) byte order.

    Declaration

    Swift

    public func serialize() -> Data
  • Multiply this big integer by a single digit, and store the result in place of the original big integer.

    Complexity

    O(count)

    Declaration

    Swift

    public mutating func multiply(byDigit y: Digit)
  • Multiply this big integer by a single digit, and return the result.

    Complexity

    O(count)

    Declaration

    Swift

    public func multiplied(byDigit y: Digit) -> BigUInt
  • Multiply x by y, and add the result to this integer, optionally shifted shift digits 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.)

    Returns

    self is set to self + (x * y) << (shift * 2^Digit.width)

    Complexity

    O(count)

    Declaration

    Swift

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

    Return Value

    self is set to self + (x * y) << (shift * 2^Digit.width)

  • 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 digits.

    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 digits than this limit.

    Declaration

    Swift

    public static var directMultiplicationLimit: Int = 1024
  • 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 digits.

    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)
  • Multiply lhs and rhs together, returning the result. This function never results in an overflow.

    Declaration

    Swift

    public static func multiplyWithOverflow(_ lhs: BigUInt, _ rhs: BigUInt) -> (BigUInt, overflow: Bool)
  • Shift a big integer to the right by amount bits and store the result in place.

    Complexity

    O(count)

    Declaration

    Swift

    public static func <<= (b: inout BigUInt, amount: Int)
  • Shift a big integer to the left by amount bits and return the result.

    Returns

    b * 2^amount

    Complexity

    O(count)

    Declaration

    Swift

    public static func << (b: BigUInt, amount: Int) -> BigUInt

    Return Value

    b * 2^amount

  • Shift a big integer to the right by amount bits and store the result in place.

    Complexity

    O(count)

    Declaration

    Swift

    public static func >>= (b: inout BigUInt, amount: Int)
  • Shift a big integer to the right by amount bits and return the result.

    Returns

    b / 2^amount

    Complexity

    O(count)

    Declaration

    Swift

    public static func >> (b: BigUInt, amount: Int) -> BigUInt

    Return Value

    b / 2^amount

  • Returns the greatest common divisor of a and b.

    Complexity

    O(count^2) where count = max(a.count, b.count)

    Declaration

    Swift

    public static func gcd(_ a: BigUInt, _ b: BigUInt) -> BigUInt
  • Returns the multiplicative inverse of this integer in modulo modulus arithmetic, or nil if there is no such number.

    Returns

    If gcd(self, modulus) == 1, the value returned is an integer a < modulus such that (a * self) % modulus == 1. If self and modulus aren’t coprime, the return value is nil.

    Complexity

    O(count^3)

    Declaration

    Swift

    public func inverse(_ modulus: BigUInt) -> BigUInt?

    Return Value

    If gcd(self, modulus) == 1, the value returned is an integer a < modulus such that (a * self) % modulus == 1. If self and modulus aren’t coprime, the return value is nil.

  • 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.

    Returns

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

    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
  • Add the digit d to this integer in place. d is shifted shift digits to the left before being added.

    Complexity

    O(max(count, shift))

    Declaration

    Swift

    public mutating func addDigit(_ d: Digit, atPosition shift: Int = 0)
  • Add the digit d to this integer and return the result. d is shifted shift digits to the left before being added.

    Complexity

    O(max(count, shift))

    Declaration

    Swift

    public func addingDigit(_ d: Digit, atPosition shift: Int = 0) -> BigUInt
  • Add b to this integer in place. b is shifted shift digits to the left before being added.

    Complexity

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

    Declaration

    Swift

    public mutating func add(_ b: BigUInt, atPosition shift: Int = 0)
  • Add b to this integer and return the result. b is shifted shift digits to the left before being added.

    Complexity

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

    Declaration

    Swift

    public func adding(_ b: BigUInt, atPosition shift: Int = 0) -> BigUInt
  • Increment this integer by one. If shift is non-zero, it selects the digit that is to be incremented.

    Complexity

    O(count + shift)

    Declaration

    Swift

    public mutating func increment(atPosition 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)
  • Add lhs and rhs together, returning the result. This function never results in an overflow.

    Declaration

    Swift

    public static func addWithOverflow(_ lhs: BigUInt, _ rhs: BigUInt) -> (BigUInt, overflow: Bool)