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
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 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
andb
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 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.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.
Note
This function usesarc4random_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 aBigUInt
such that the top bit of its most significant word is 1.Note
0 is considered to have zero leading zero bits.See also
widthComplexity
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
.
-
Declaration
Swift
public struct Words: RandomAccessCollection
-
Declaration
Swift
public var words: Words
-
Undocumented
Declaration
Swift
public struct BigUInt: UnsignedInteger
-
Append this
BigUInt
to the specified hasher.Declaration
Swift
public func appendHashes(to hasher: inout SipHasher)
-
Declaration
Swift
public init?<T: BinaryFloatingPoint>(exactly source: T)
-
Declaration
Swift
public init<T: BinaryFloatingPoint>(_ source: T)
-
Subtract
other
from this integer in place, and return a flag indicating if the operation caused an arithmetic overflow.other
is shiftedshift
digits to the left before being subtracted.Note
If the result indicates an overflow, thenself
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 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 subtractingReportingOverflow(_ other: BigUInt, shiftedBy shift: Int) -> (partialValue: BigUInt, overflow: Bool)
-
Subtracts
other
fromself
, returning the result and a flag indicating arithmetic overflow.Note
When the operation overflows, thenpartialValue
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 shiftedshift
digits to the left before being subtracted.Requires
self >= other * 2^shiftComplexity
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 shiftedshift
digits to the left before being subtracted.Requires
self >= b * 2^shiftComplexity
O(count)Declaration
Swift
public func subtracting(_ other: BigUInt, shiftedBy shift: Int = 0) -> BigUInt
-
Decrement this integer by one.
Requires
!isZeroComplexity
O(count)Declaration
Swift
public mutating func decrement(shiftedBy 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)
-
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)
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)
-
Declaration
Swift
public init?<T: BinaryInteger>(exactly source: T)
-
Declaration
Swift
public init<T: BinaryInteger>(_ source: T)
-
Declaration
Swift
public init<T: BinaryInteger>(truncatingIfNeeded source: T)
-
Declaration
Swift
public init<T: BinaryInteger>(clamping source: T)
-
Initialize a new big integer from an integer literal.
Declaration
Swift
public init(integerLiteral value: UInt64)
-
Declaration
Swift
public static var isSigned: Bool
-
Returns
-1
if this value is negative and1
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 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
subscript(_ index: Int) -> Word
-
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
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
. -
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
-
Return the playground quick look representation of this integer.
Declaration
Swift
public var customPlaygroundQuickLook: PlaygroundQuickLook
-
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
byy
, and add the result to this integer, optionally shiftedshift
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 toself + (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 thanBigUInt.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
byb
and return the result.Note
This uses the naive O(n^2) multiplication algorithm unless both arguments have more thanBigUInt.directMultiplicationLimit
words.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)
-
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
andb
.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, ornil
if there is no such number.Requires
modulus > 1Complexity
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 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))
-
Declaration
Swift
public init(from decoder: Decoder) throws
-
Declaration
Swift
public func encode(to encoder: Encoder) throws
-
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.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
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)