BigUInt

public struct BigUInt : UnsignedInteger
extension BigUInt: Codable
extension BigUInt: Comparable
extension BigUInt: Hashable
extension BigUInt: ExpressibleByIntegerLiteral
extension BigUInt: Strideable
extension BigUInt: ExpressibleByStringLiteral
extension BigUInt: CustomStringConvertible
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.)

Show on GitHub

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

    Declaration

    Swift

    public typealias Word = UInt
    Show on GitHub

  • Initializes a new BigUInt with value 0.

    Declaration

    Swift

    public init()
    Show on GitHub

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

    Declaration

    Swift

    public init(words: [Word])
    Show on GitHub

Addition

  • 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
    Show on GitHub

  • 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)
    Show on GitHub

  • Declaration

    Swift

    public static var isSigned: Bool { get }
    Show on GitHub

  • Return true iff this integer is zero.

    Complexity

    O(1)

    Declaration

    Swift

    public var isZero: Bool { get }
    Show on GitHub

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

    Show on GitHub

Bitwise Operations

  • Return the ones’ complement of a.

    Complexity

    O(a.count)

    Declaration

    Swift

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

  • 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)
    Show on GitHub

  • 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)
    Show on GitHub

  • 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)
    Show on GitHub

  • Declaration

    Swift

    public init(from decoder: Decoder) throws
    Show on GitHub

  • Declaration

    Swift

    public func encode(to encoder: Encoder) throws
    Show on GitHub

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
    Show on GitHub

  • Return true iff a is equal to b.

    Complexity

    O(count)

    Declaration

    Swift

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

  • Return true iff a is less than b.

    Complexity

    O(count)

    Declaration

    Swift

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

NSData Conversion

  • Initialize a BigInt from bytes accessed from an UnsafeRawBufferPointer

    Declaration

    Swift

    public init(_ buffer: UnsafeRawBufferPointer)
    Show on GitHub

  • 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)
    Show on GitHub

  • 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
    Show on GitHub

Division

  • 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

    Show on GitHub

  • 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
    Show on GitHub

  • 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
    Show on GitHub

  • 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)
    Show on GitHub

  • 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)
    Show on GitHub

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

    Show on GitHub

  • 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
    Show on GitHub

  • Declaration

    Swift

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

  • Declaration

    Swift

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

Greatest Common Divisor

  • 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
    Show on GitHub

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

    Show on GitHub

Hashing

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)
    Show on GitHub

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

    Complexity

    O(count)

    Declaration

    Swift

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

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

    Show on GitHub

  • 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
    Show on GitHub

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

    Declaration

    Swift

    public static var directMultiplicationLimit: Int
    Show on GitHub

  • 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
    Show on GitHub

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

    Declaration

    Swift

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

Primality Testing

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

    Declaration

    Swift

    public func isStrongProbablePrime(_ base: BigUInt) -> Bool
    Show on GitHub

  • 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
    Show on GitHub

  • Create a big unsigned integer consisting of width uniformly distributed random bits.

    Declaration

    Swift

    public static func randomInteger<RNG>(withMaximumWidth width: Int, using generator: inout RNG) -> BigUInt where RNG : RandomNumberGenerator

    Parameters

    width

    The maximum number of one bits in the result.
    generator

    The source of randomness.

    Return Value

    A big unsigned integer less than 1 << width.

    Show on GitHub

  • Create a big unsigned integer consisting of width uniformly distributed random bits.

    Note

    I use a SystemRandomGeneratorGenerator as the source of randomness.

    Declaration

    Swift

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

    Parameters

    width

    The maximum number of one bits in the result.

    Return Value

    A big unsigned integer less than 1 << width.

    Show on GitHub

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

    Note

    If width is zero, the result is zero.

    Declaration

    Swift

    public static func randomInteger<RNG>(withExactWidth width: Int, using generator: inout RNG) -> BigUInt where RNG : RandomNumberGenerator

    Parameters

    width

    The number of bits required to represent the answer.
    generator

    The source of randomness.

    Return Value

    A random big unsigned integer whose width is width.

    Show on GitHub

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

    Note

    If width is zero, the result is zero.

    Note

    I use a SystemRandomGeneratorGenerator as the source of randomness.

    Declaration

    Swift

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

    Return Value

    A random big unsigned integer whose width is width.

    Show on GitHub

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

    Precondition

    limit > 0.

    Declaration

    Swift

    public static func randomInteger<RNG>(lessThan limit: BigUInt, using generator: inout RNG) -> BigUInt where RNG : RandomNumberGenerator

    Parameters

    limit

    The upper bound on the result.
    generator

    The source of randomness.

    Return Value

    A random big unsigned integer that is less than limit.

    Show on GitHub

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

    Precondition

    limit > 0.

    Note

    I use a SystemRandomGeneratorGenerator as the source of randomness.

    Declaration

    Swift

    public static func randomInteger(lessThan limit: BigUInt) -> BigUInt

    Parameters

    limit

    The upper bound on the result.

    Return Value

    A random big unsigned integer that is less than limit.

    Show on GitHub

Shift Operators

  • Undocumented

    Declaration

    Swift

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

  • Undocumented

    Declaration

    Swift

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

  • Undocumented

    Declaration

    Swift

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

  • Undocumented

    Declaration

    Swift

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

Square Root

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

    Show on GitHub

  • A type that can represent the distance between two values ofa BigUInt.

    Declaration

    Swift

    public typealias Stride = BigInt
    Show on GitHub

  • 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
    Show on GitHub

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

    Declaration

    Swift

    public func distance(to other: BigUInt) -> BigInt
    Show on GitHub

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.

    Show on GitHub

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

    Declaration

    Swift

    public init(unicodeScalarLiteral value: UnicodeScalar)
    Show on GitHub

  • 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)
    Show on GitHub

  • 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)
    Show on GitHub

  • Return the decimal representation of this integer.

    Declaration

    Swift

    public var description: String { get }
    Show on GitHub

  • Return the playground quick look representation of this integer.

    Declaration

    Swift

    public var playgroundDescription: Any { get }
    Show on GitHub

Subtraction

  • 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
    Show on GitHub

  • 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)
    Show on GitHub

  • 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)
    Show on GitHub

  • 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)
    Show on GitHub

  • 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
    Show on GitHub

  • Decrement this integer by one.

    Requires

    !isZero

    Complexity

    O(count)

    Declaration

    Swift

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

  • 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
    Show on GitHub

  • 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)
    Show on GitHub

  • Undocumented

    Declaration

    Swift

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

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

    Show on GitHub

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

    Show on GitHub

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

    Show on GitHub
  • See more

    Declaration

    Swift

    public struct Words : RandomAccessCollection
    Show on GitHub

  • Declaration

    Swift

    public var words: Words { get }
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public init<Words>(words: Words) where Words : Sequence, Words.Element == BigUInt.Word
    Show on GitHub