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 >= 0Declaration
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 aBigUInt
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 in0...(Digit.width - 1)
.See also
widthComplexity
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 in0...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
andb
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
andb
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
andb
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
andb
, and store the result ina
.Complexity
O(max(a.count, b.count))Declaration
Swift
public static func |= (a: inout BigUInt, b: BigUInt)
-
Calculate the bitwise AND of
a
andb
, and store the result ina
.Complexity
O(max(a.count, b.count))Declaration
Swift
public static func &= (a: inout BigUInt, b: BigUInt)
-
Calculate the bitwise XOR of
a
andb
, and store the result ina
.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 than1 << width
.Note
This function usesarc4random_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 iswidth
.Note
This function usesarc4random_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 thanlimit
.Note
This function usesarc4random_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
-
Append this
BigUInt
to the specified hasher.Declaration
Swift
public func appendHashes(to hasher: inout SipHasher)
-
Subtract a digit
d
from this integer in place, returning a flag that is true if the operation caused an arithmetic overflow.d
is shiftedshift
digits to the left before being subtracted.Note
If the result is true, thenself
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 shiftedshift
digits to the left before being subtracted.Note
Ifoverflow
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 shiftedshift
digits to the left before being subtracted.Requires
self >= d * 2^shiftComplexity
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 shiftedshift
digits to the left before being subtracted.Requires
self >= d * 2^shiftComplexity
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 shiftedshift
digits to the left before being subtracted.Note
If the result is true, thenself
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 shiftedshift
digits to the left before being subtracted.Note
Ifoverflow
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 shiftedshift
digits to the left before being subtracted.Requires
self >= b * 2^shiftComplexity
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 shiftedshift
digits to the left before being subtracted.Requires
self >= b * 2^shiftComplexity
O(count)Declaration
Swift
public func subtracting(_ b: BigUInt, atPosition shift: Int = 0) -> BigUInt
-
Decrement this integer by one.
Requires
!isZeroComplexity
O(count)Declaration
Swift
public mutating func decrement(atPosition shift: Int = 0)
-
Subtract
b
froma
and return the result.Requires
a >= bComplexity
O(a.count)Declaration
Swift
public static func -(a: BigUInt, b: BigUInt) -> BigUInt
-
Subtract
b
froma
and store the result ina
.Requires
a >= bComplexity
O(a.count)Declaration
Swift
public static func -=(a: inout BigUInt, b: BigUInt)
-
Subtracts rhs from
lhs
, returning the result and aBool
that is true iff the operation caused an arithmetic overflow. Overflow is returned if and only iflhs
is less thanrhs
, 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 > 0Complexity
O(count) -
Divide this integer by the digit
y
and return the resulting quotient and remainder.Requires
y > 0Returns
(quotient, remainder) where quotient = floor(x/y), remainder = x - quotient * yComplexity
O(x.count)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)
wherequotient = 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)
wherequotient = floor(self/y)
,remainder = self - quotient * y
-
Divide
x
byy
and return the quotient.Note
Usedivided(by:)
if you also need the remainder.Declaration
Swift
public static func /(x: BigUInt, y: BigUInt) -> BigUInt
-
Divide
x
byy
and return the remainder.Note
Usedivided(by:)
if you also need the remainder.Declaration
Swift
public static func %(x: BigUInt, y: BigUInt) -> BigUInt
-
Divide
x
byy
and store the quotient inx
.Note
Usedivided(by:)
if you also need the remainder.Declaration
Swift
public static func /=(x: inout BigUInt, y: BigUInt)
-
Divide
x
byy
and store the remainder inx
.Note
Usedivided(by:)
if you also need the remainder.Declaration
Swift
public static func %=(x: inout BigUInt, y: BigUInt)
-
Divide
lhs
byrhs
, 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
byrhs
, 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 an integer literal.
Declaration
Swift
public init(integerLiteral value: UInt64)
-
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 toendIndex
. 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 >= 0Complexity
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
-
Compare
a
tob
and return anNSComparisonResult
indicating their order.Complexity
O(count)Declaration
Swift
public static func compare(_ a: BigUInt, _ b: BigUInt) -> ComparisonResult
-
Return true iff
a
is equal tob
.Complexity
O(count)Declaration
Swift
public static func ==(a: BigUInt, b: BigUInt) -> Bool
-
Return true iff
a
is less thanb
.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
Parametertext
: A string consisting of characters corresponding to numerals in the given radix. (0-9, a-z, A-Z)Parameter
Parameterradix
: The base of the number system to use, or 10 if unspecified.Returns
The integer represented bytext
, or nil iftext
contains a character that does not represent a numeral inradix
.Declaration
Swift
public init?(_ text: String, radix: Int = 10)
Return Value
The integer represented by
text
, or nil iftext
contains a character that does not represent a numeral inradix
. -
Return the decimal representation of this integer.
Declaration
Swift
public var description: String
-
Return the playground quick look representation of this integer.
Declaration
Swift
public var customPlaygroundQuickLook: PlaygroundQuickLook
-
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
byy
, and add the result to this integer, optionally shiftedshift
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 toself + (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 toself + (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 thanBigUInt.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
byb
and return the result.Note
This uses the naive O(n^2) multiplication algorithm unless both arguments have more thanBigUInt.directMultiplicationLimit
digits.Complexity
O(n^log2(3))Declaration
Swift
public static func *(x: BigUInt, y: BigUInt) -> BigUInt
-
Multiply
a
byb
and store the result ina
.Declaration
Swift
public static func *=(a: inout BigUInt, b: BigUInt)
-
Multiply
lhs
andrhs
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^amountComplexity
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^amountComplexity
O(count)Declaration
Swift
public static func >> (b: BigUInt, amount: Int) -> BigUInt
Return Value
b / 2^amount
-
Returns the greatest common divisor of
a
andb
.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, ornil
if there is no such number.Returns
Ifgcd(self, modulus) == 1
, the value returned is an integera < modulus
such that(a * self) % modulus == 1
. Ifself
andmodulus
aren’t coprime, the return value isnil
.Complexity
O(count^3)Declaration
Swift
public func inverse(_ modulus: BigUInt) -> BigUInt?
Return Value
If
gcd(self, modulus) == 1
, the value returned is an integera < modulus
such that(a * self) % modulus == 1
. Ifself
andmodulus
aren’t coprime, the return value isnil
.
-
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 whyexponent
is a simple integer value. If you want to calculate big exponents, you’ll probably need to use the modulo arithmetic variant.Returns
1 ifexponent == 0
, otherwiseself
raised toexponent
. (This implies that0.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
, otherwiseself
raised toexponent
. (This implies that0.power(0) == 1
.) -
Returns the remainder of this integer raised to the power
exponent
in modulo arithmetic undermodulus
.Uses the right-to-left binary method.
Complexity
O(exponent.count * modulus.count^log2(3)) or somesuchDeclaration
Swift
public func power(_ exponent: BigUInt, modulus: BigUInt) -> BigUInt
-
Add the digit
d
to this integer in place.d
is shiftedshift
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 shiftedshift
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 shiftedshift
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 shiftedshift
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
andb
together and return the result.Complexity
O(max(a.count, b.count))Declaration
Swift
public static func +(a: BigUInt, b: BigUInt) -> BigUInt
-
Add
a
andb
together, and store the sum ina
.Complexity
O(max(a.count, b.count))Declaration
Swift
public static func +=(a: inout BigUInt, b: BigUInt)
-
Add
lhs
andrhs
together, returning the result. This function never results in an overflow.Declaration
Swift
public static func addWithOverflow(_ lhs: BigUInt, _ rhs: BigUInt) -> (BigUInt, overflow: Bool)