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

• ``` Word ```

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

#### Declaration

Swift

``public typealias Word = UInt``
• ``` init() ```

Initializes a new BigUInt with value 0.

#### Declaration

Swift

``public init()``
• ``` init(words:) ```

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)``
• ``` randomInteger(withMaximumWidth:) ```

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

• ``` randomInteger(withExactWidth:) ```

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

• ``` randomInteger(lessThan:) ```

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

• ``` isStrongProbablePrime(_:) ```

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

#### Declaration

Swift

``public func isStrongProbablePrime(_ base: BigUInt) -> Bool``
• ``` isPrime(rounds:) ```

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

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

• ``` leadingZeroBitCount ```

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.

width

Complexity

O(1)

#### Declaration

Swift

``public var leadingZeroBitCount: Int``

#### Return Value

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

• ``` trailingZeroBitCount ```

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

• ``` Words ```

#### Declaration

Swift

``public struct Words: RandomAccessCollection``
• ``` words ```

#### Declaration

Swift

``public var words: Words``
• ``` init(words:) ```

Undocumented

#### Declaration

Swift

``public struct BigUInt: UnsignedInteger``
• ``` appendHashes(to:) ```

Append this `BigUInt` to the specified hasher.

#### Declaration

Swift

``public func appendHashes(to hasher: inout SipHasher)``
• ``` init(exactly:) ```

#### Declaration

Swift

``public init?<T: BinaryFloatingPoint>(exactly source: T)``
• ``` init(_:) ```

#### Declaration

Swift

``public init<T: BinaryFloatingPoint>(_ source: T)``
• ``` subtractReportingOverflow(_:shiftedBy:) ```

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``
• ``` subtractingReportingOverflow(_:shiftedBy:) ```

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)``
• ``` subtractingReportingOverflow(_:) ```

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(_:shiftedBy:) ```

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)``
• ``` subtracting(_:shiftedBy:) ```

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(shiftedBy:) ```

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)``
• ``` quotientAndRemainder(dividingBy:) ```

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)``
• ``` init(exactly:) ```

#### Declaration

Swift

``public init?<T: BinaryInteger>(exactly source: T)``
• ``` init(_:) ```

#### Declaration

Swift

``public init<T: BinaryInteger>(_ source: T)``
• ``` init(truncatingIfNeeded:) ```

#### Declaration

Swift

``public init<T: BinaryInteger>(truncatingIfNeeded source: T)``
• ``` init(clamping:) ```

#### Declaration

Swift

``public init<T: BinaryInteger>(clamping source: T)``
• ``` init(integerLiteral:) ```

Initialize a new big integer from an integer literal.

#### Declaration

Swift

``public init(integerLiteral value: UInt64)``
• ``` isSigned ```

#### Declaration

Swift

``public static var isSigned: Bool``
• ``` signum() ```

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.

• ``` subscript(_:) ```

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(_:_:) ```

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``
• ``` init(_:radix:) ```

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

• ``` init(_:radix:) ```

Undocumented

#### Declaration

Swift

``public struct BigUInt: UnsignedInteger``
• ``` init(unicodeScalarLiteral:) ```

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

#### Declaration

Swift

``public init(unicodeScalarLiteral value: UnicodeScalar)``
• ``` init(extendedGraphemeClusterLiteral:) ```

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)``
• ``` init(stringLiteral:) ```

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

Return the decimal representation of this integer.

#### Declaration

Swift

``public var description: String``
• ``` customPlaygroundQuickLook ```

Return the playground quick look representation of this integer.

#### Declaration

Swift

``public var customPlaygroundQuickLook: PlaygroundQuickLook``
• ``` init(_:) ```

Undocumented

#### Declaration

Swift

``public struct BigUInt: UnsignedInteger``
• ``` init(_:) ```

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)``
• ``` serialize() ```

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(byWord:) ```

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)``
• ``` multiplied(byWord:) ```

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

Complexity

O(count)

#### Declaration

Swift

``public func multiplied(byWord y: Word) -> BigUInt``
• ``` multiplyAndAdd(_:_:shiftedBy:) ```

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

• ``` multiplied(by:) ```

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

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

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

#### Declaration

Swift

``public typealias Stride = BigInt``
• ``` advanced(by:) ```

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``
• ``` distance(to:) ```

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``
• ``` greatestCommonDivisor(with:) ```

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``
• ``` inverse(_:) ```

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

• ``` squareRoot() ```

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

• ``` init(from:) ```

#### Declaration

Swift

``public init(from decoder: Decoder) throws``
• ``` encode(to:) ```

#### Declaration

Swift

``public func encode(to encoder: Encoder) throws``
• ``` power(_:) ```

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.

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

• ``` power(_:modulus:) ```

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