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

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

• ``` +(_:_:) ```

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

#### Declaration

Swift

``public static var isSigned: Bool { get }``
• ``` isZero ```

Return true iff this integer is zero.

Complexity

O(1)

#### Declaration

Swift

``public var isZero: Bool { get }``
• ``` signum() ```

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.

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

#### Declaration

Swift

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

#### Declaration

Swift

``public func encode(to encoder: Encoder) throws``

### Comparison

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

### NSData Conversion

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

Initialize a BigInt from bytes accessed from an UnsafeRawBufferPointer

#### Declaration

Swift

``public init(_ buffer: UnsafeRawBufferPointer)``
• ``` 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``

### Division

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

### Exponentiation

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

#### Declaration

Swift

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

#### Declaration

Swift

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

### Greatest Common Divisor

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

### Hashing

• ``` hash(into:) ```

Append this `BigUInt` to the specified hasher.

#### Declaration

Swift

``public func hash(into hasher: inout Hasher)``
• ``` init(exactly:) ```

#### Declaration

Swift

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

#### Declaration

Swift

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

#### Declaration

Swift

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

#### Declaration

Swift

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

Initialize a new big integer from an integer literal.

#### Declaration

Swift

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

### Multiplication

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

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

### Primality Testing

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

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

• ``` randomInteger(withMaximumWidth:) ```

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

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

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

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

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

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

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

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

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

### Shift Operators

• ``` >>=(_:_:) ```

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

### Square Root

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

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

### String Conversion

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

• ``` 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 { get }``
• ``` playgroundDescription ```

Return the playground quick look representation of this integer.

#### Declaration

Swift

``public var playgroundDescription: Any { get }``

### Subtraction

• ``` 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)``
• ``` subscript(bitAt:) ```

Undocumented

#### Declaration

Swift

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

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

• ``` 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 { get }``

#### 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 { get }``

#### Return Value

A value in `0...width`.

• ``` Words ```

#### Declaration

Swift

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

#### Declaration

Swift

``public var words: Words { get }``
• ``` init(words:) ```

Undocumented

#### Declaration

Swift

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