BigInt

public struct BigInt : SignedInteger
extension BigInt: Codable
extension BigInt: Comparable
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).magnitude.isPrime()   // Returns false
Show on GitHub

Bitwise Operations

  • Undocumented

    Declaration

    Swift

    public prefix static func ~ (x: BigInt) -> BigInt
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public static func & (lhs: inout BigInt, rhs: BigInt) -> BigInt
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public static func | (lhs: inout BigInt, rhs: BigInt) -> BigInt
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public static func ^ (lhs: inout BigInt, rhs: BigInt) -> BigInt
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public static func &= (lhs: inout BigInt, rhs: BigInt)
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public static func |= (lhs: inout BigInt, rhs: BigInt)
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public static func ^= (lhs: inout BigInt, rhs: BigInt)
    Show on GitHub

  • Declaration

    Swift

    public init(from decoder: Decoder) throws
    Show on GitHub

  • Declaration

    Swift

    public func encode(to encoder: Encoder) throws
    Show on GitHub

  • Return true iff a is equal to b.

    Declaration

    Swift

    public static func == (a: BigInt, b: BigInt) -> Bool
    Show on GitHub

  • Return true iff a is less than b.

    Declaration

    Swift

    public static func < (a: BigInt, b: BigInt) -> Bool
    Show on GitHub

  • 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)
    Show on GitHub

  • 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)
    Show on GitHub

  • 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
    Show on GitHub

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

    Show on GitHub

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

    Declaration

    Swift

    public static func / (a: BigInt, b: BigInt) -> BigInt
    Show on GitHub

  • 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
    Show on GitHub

  • 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
    Show on GitHub

  • Divide a by b storing the quotient in a.

    Declaration

    Swift

    public static func /= (a: inout BigInt, b: BigInt)
    Show on GitHub

  • Divide a by b storing the remainder in a.

    Declaration

    Swift

    public static func %= (a: inout BigInt, b: BigInt)
    Show on GitHub

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

    Show on GitHub

  • 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
    Show on GitHub

  • Declaration

    Swift

    public init?<T>(exactly source: T) where T : BinaryFloatingPoint
    Show on GitHub

  • Declaration

    Swift

    public init<T>(_ source: T) where T : BinaryFloatingPoint
    Show on GitHub

  • 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
    Show on GitHub

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

    Show on GitHub

  • Append this BigInt to the specified hasher.

    Declaration

    Swift

    public func hash(into hasher: inout Hasher)
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public init()
    Show on GitHub

  • Initializes a new signed big integer with the same value as the specified unsigned big integer.

    Declaration

    Swift

    public init(_ integer: BigUInt)
    Show on GitHub

  • Declaration

    Swift

    public init<T>(_ source: T) where T : BinaryInteger
    Show on GitHub

  • Declaration

    Swift

    public init?<T>(exactly source: T) where T : BinaryInteger
    Show on GitHub

  • Declaration

    Swift

    public init<T>(clamping source: T) where T : BinaryInteger
    Show on GitHub

  • Declaration

    Swift

    public init<T>(truncatingIfNeeded source: T) where T : BinaryInteger
    Show on GitHub

  • Initialize a new big integer from an integer literal.

    Declaration

    Swift

    public init(integerLiteral value: Int64)
    Show on GitHub

  • Multiply a with b and return the result.

    Declaration

    Swift

    public static func * (a: BigInt, b: BigInt) -> BigInt
    Show on GitHub

  • Multiply a with b in place.

    Declaration

    Swift

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

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
    Show on GitHub

  • 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
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public static func &<< (left: BigInt, right: BigInt) -> BigInt
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public static func &<<= (left: inout BigInt, right: BigInt)
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public static func &>> (left: BigInt, right: BigInt) -> BigInt
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public static func &>>= (left: inout BigInt, right: BigInt)
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public static func << <Other>(lhs: BigInt, rhs: Other) -> BigInt where Other : BinaryInteger
    Show on GitHub

  • Undocumented

    Declaration

    Swift

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

  • Undocumented

    Declaration

    Swift

    public static func >> <Other>(lhs: BigInt, rhs: Other) -> BigInt where Other : BinaryInteger
    Show on GitHub

  • Undocumented

    Declaration

    Swift

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

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

    Show on GitHub

  • Declaration

    Swift

    public typealias Stride = BigInt
    Show on GitHub

  • Returns self + n.

    Declaration

    Swift

    public func advanced(by n: Stride) -> BigInt
    Show on GitHub

  • Returns other - self.

    Declaration

    Swift

    public func distance(to other: BigInt) -> Stride
    Show on GitHub

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

    Show on GitHub

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

    Declaration

    Swift

    public init(unicodeScalarLiteral value: UnicodeScalar)
    Show on GitHub

  • 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)
    Show on GitHub

  • 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)
    Show on GitHub

  • Return the decimal representation of this integer.

    Declaration

    Swift

    public var description: String { get }
    Show on GitHub

  • Return the playground quick look representation of this integer.

    Declaration

    Swift

    public var playgroundDescription: Any { get }
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public mutating func negate()
    Show on GitHub

  • Subtract b from a and return the result.

    Declaration

    Swift

    public static func - (a: BigInt, b: BigInt) -> BigInt
    Show on GitHub

  • Subtract b from a in place.

    Declaration

    Swift

    public static func -= (a: inout BigInt, b: BigInt)
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public var bitWidth: Int { get }
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public var trailingZeroBitCount: Int { get }
    Show on GitHub
  • See more

    Declaration

    Swift

    public struct Words : RandomAccessCollection
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public var words: Words { get }
    Show on GitHub

  • Undocumented

    Declaration

    Swift

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