BigInt

public struct BigInt : SignedInteger
extension BigInt: Codable
extension BigInt: Hashable
extension BigInt: ExpressibleByIntegerLiteral
extension BigInt: Strideable
extension BigInt: ExpressibleByStringLiteral
extension BigInt: CustomStringConvertible
extension BigInt: CustomPlaygroundDisplayConvertible

An arbitary precision signed 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.

BigInt is essentially a tiny wrapper that extends BigUInt with a sign bit and provides signed integer operations. Both the underlying absolute value and the negative/positive flag are available as read-write properties.

Not all algorithms of BigUInt are available for BigInt values; for example, there is no square root or primality test for signed integers. When you need to call one of these, just extract the absolute value:

BigInt(255).abs.isPrime()   // Returns false

Bitwise Operations

  • Undocumented

    Declaration

    Swift

    public prefix static func ~ (x: BigInt) -> BigInt
  • Undocumented

    Declaration

    Swift

    public static func & (lhs: inout BigInt, rhs: BigInt) -> BigInt
  • Undocumented

    Declaration

    Swift

    public static func | (lhs: inout BigInt, rhs: BigInt) -> BigInt
  • Undocumented

    Declaration

    Swift

    public static func ^ (lhs: inout BigInt, rhs: BigInt) -> BigInt
  • Undocumented

    Declaration

    Swift

    public static func &= (lhs: inout BigInt, rhs: BigInt)
  • Undocumented

    Declaration

    Swift

    public static func |= (lhs: inout BigInt, rhs: BigInt)
  • Undocumented

    Declaration

    Swift

    public static func ^= (lhs: inout BigInt, rhs: BigInt)
  • Declaration

    Swift

    public init(from decoder: Decoder) throws
  • Declaration

    Swift

    public func encode(to encoder: Encoder) throws
  • Return true iff a is equal to b.

    Declaration

    Swift

    public static func == (a: BigInt, b: BigInt) -> Bool
  • Return true iff a is less than b.

    Declaration

    Swift

    public static func < (a: BigInt, b: BigInt) -> Bool
  • Initialize a BigInt from bytes accessed from an UnsafeRawBufferPointer, where the first byte indicates sign (0 for positive, 1 for negative)

    Declaration

    Swift

    public init(_ buffer: UnsafeRawBufferPointer)
  • Initializes an integer from the bits stored inside a piece of Data. The data is assumed to be in network (big-endian) byte order with a first byte to represent the sign (0 for positive, 1 for negative)

    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 and a prepended byte to indicate the sign (0 for positive, 1 for negative)

    Declaration

    Swift

    public func serialize() -> Data

Full-width multiplication and 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: BigInt) -> (quotient: BigInt, remainder: BigInt)

    Return Value

    (quotient, remainder) where quotient = floor(self/y), remainder = self - quotient * y

  • Divide a by b and return the quotient. Traps if b is zero.

    Declaration

    Swift

    public static func / (a: BigInt, b: BigInt) -> BigInt
  • Divide a by b and return the remainder. The result has the same sign as a.

    Declaration

    Swift

    public static func % (a: BigInt, b: BigInt) -> BigInt
  • Return the result of a mod b. The result is always a nonnegative integer that is less than the absolute value of b.

    Declaration

    Swift

    public func modulus(_ mod: BigInt) -> BigInt
  • Divide a by b storing the quotient in a.

    Declaration

    Swift

    public static func /= (a: inout BigInt, b: BigInt)
  • Divide a by b storing the remainder in a.

    Declaration

    Swift

    public static func %= (a: inout BigInt, b: BigInt)
  • 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) -> BigInt

    Return Value

    1 if exponent == 0, otherwise self raised to exponent. (This implies that 0.power(0) == 1.)

  • 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: BigInt, modulus: BigInt) -> BigInt
  • Declaration

    Swift

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

    Swift

    public init<T>(_ source: T) where T : BinaryFloatingPoint
  • Returns the greatest common divisor of a and b.

    Complexity

    O(count^2) where count = max(a.count, b.count)

    Declaration

    Swift

    public func greatestCommonDivisor(with b: BigInt) -> BigInt
  • Returns the multiplicative inverse of this integer in modulo modulus arithmetic, or nil if there is no such number.

    Requires

    modulus.magnitude > 1

    Complexity

    O(count^3)

    Declaration

    Swift

    public func inverse(_ modulus: BigInt) -> BigInt?

    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.

  • Append this BigInt to the specified hasher.

    Declaration

    Swift

    public func hash(into hasher: inout Hasher)
  • Undocumented

    Declaration

    Swift

    public init()
  • Initializes a new signed big integer with the same value as the specified unsigned big integer.

    Declaration

    Swift

    public init(_ integer: BigUInt)
  • Declaration

    Swift

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

    Swift

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

    Swift

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

    Swift

    public init<T>(truncatingIfNeeded source: T) where T : BinaryInteger
  • Initialize a new big integer from an integer literal.

    Declaration

    Swift

    public init(integerLiteral value: Int64)
  • Multiply a with b and return the result.

    Declaration

    Swift

    public static func * (a: BigInt, b: BigInt) -> BigInt
  • Multiply a with b in place.

    Declaration

    Swift

    public static func *= (a: inout BigInt, b: BigInt)

Primality Testing

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

    Declaration

    Swift

    public func isStrongProbablePrime(_ base: BigInt) -> 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
  • Undocumented

    Declaration

    Swift

    public static func &<< (left: BigInt, right: BigInt) -> BigInt
  • Undocumented

    Declaration

    Swift

    public static func &<<= (left: inout BigInt, right: BigInt)
  • Undocumented

    Declaration

    Swift

    public static func &>> (left: BigInt, right: BigInt) -> BigInt
  • Undocumented

    Declaration

    Swift

    public static func &>>= (left: inout BigInt, right: BigInt)
  • Undocumented

    Declaration

    Swift

    public static func << <Other>(lhs: BigInt, rhs: Other) -> BigInt where Other : BinaryInteger
  • Undocumented

    Declaration

    Swift

    public static func <<= <Other>(lhs: inout BigInt, rhs: Other) where Other : BinaryInteger
  • Undocumented

    Declaration

    Swift

    public static func >> <Other>(lhs: BigInt, rhs: Other) -> BigInt where Other : BinaryInteger
  • Undocumented

    Declaration

    Swift

    public static func >>= <Other>(lhs: inout BigInt, rhs: Other) where Other : BinaryInteger

Square Root

  • Returns the integer square root of a big integer; i.e., the largest integer whose square isn’t greater than value.

    Requires

    self >= 0

    Declaration

    Swift

    public func squareRoot() -> BigInt

    Return Value

    floor(sqrt(self))

  • Declaration

    Swift

    public typealias Stride = BigInt
  • Returns self + n.

    Declaration

    Swift

    public func advanced(by n: Stride) -> BigInt
  • Returns other - self.

    Declaration

    Swift

    public func distance(to other: BigInt) -> Stride
  • 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.

  • 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 { get }
  • Return the playground quick look representation of this integer.

    Declaration

    Swift

    public var playgroundDescription: Any { get }
  • Undocumented

    Declaration

    Swift

    public mutating func negate()
  • Subtract b from a and return the result.

    Declaration

    Swift

    public static func - (a: BigInt, b: BigInt) -> BigInt
  • Subtract b from a in place.

    Declaration

    Swift

    public static func -= (a: inout BigInt, b: BigInt)
  • Undocumented

    Declaration

    Swift

    public var bitWidth: Int { get }
  • Undocumented

    Declaration

    Swift

    public var trailingZeroBitCount: Int { get }
  • Declaration

    Swift

    public struct Words : RandomAccessCollection
  • Undocumented

    Declaration

    Swift

    public var words: Words { get }
  • Undocumented

    Declaration

    Swift

    public init<S>(words: S) where S : Sequence, S.Element == BigInt.Word