BigInt

public struct BigInt: SignedInteger

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
  • 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
  • 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)
  • 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)
  • 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 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: StringProtocol>(_ text: S, radix: Int = 10)

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

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

  • 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
  • Add a to b and return the result.

    Declaration

    Swift

    public static func +(a: BigInt, b: BigInt) -> BigInt
  • Add b to a in place.

    Declaration

    Swift

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