BigUInt

public struct BigUInt: UnsignedInteger

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
  • 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(words: [Word])
  • 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 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)
  • Create a big integer consisting of width uniformly distributed random bits.

    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.

    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.

    Note

    This function uses arc4random_buf to generate random bits.

    Declaration

    Swift

    public static func randomInteger(lessThan 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
  • The minimum number of bits required to represent this integer in binary.

    Complexity

    O(1)

    Declaration

    Swift

    public var bitWidth: Int

    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

    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

    Return Value

    A value in 0...width.

  • 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)
  • 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)
  • Declaration

    Swift

    public static var isSigned: Bool
  • Returns -1 if this value is negative and 1 if it’s positive; otherwise, 0.

    Declaration

    Swift

    public func signum() -> BigUInt

    Return Value

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

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

    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.

  • Undocumented

    Declaration

    Swift

    public struct BigUInt: UnsignedInteger
  • 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 decimal representation of this integer.

    Declaration

    Swift

    public var description: String
  • Undocumented

    Declaration

    Swift

    public struct BigUInt: UnsignedInteger
  • 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
  • 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 = 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 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)
  • A type that can represent the distance between two values ofa BigUInt.

    Declaration

    Swift

    public typealias Stride = BigInt
  • 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
  • Returns the (potentially negative) difference between self and other as a BigInt. Never traps.

    Declaration

    Swift

    public func distance(to other: BigUInt) -> BigInt
  • Declaration

    Swift

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

    Swift

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

    Swift

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

    Swift

    public static func <<<Other: BinaryInteger>(lhs: BigUInt, rhs: Other) -> BigUInt
  • Returns the greatest common divisor of self and b.

    Complexity

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

    Declaration

    Swift

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

    Requires

    modulus > 1

    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 the integer square root of a big integer; i.e., the largest integer whose square isn’t greater than value.

    Declaration

    Swift

    public func squareRoot() -> BigUInt

    Return Value

    floor(sqrt(self))

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