BigInt.swift

//===--- BigInt.swift -----------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// XFAIL: linux
// RUN: rm -rf %t ; mkdir -p %t
// RUN: %target-build-swift -swift-version 4 -o %t/a.out %s
// RUN: %target-run %t/a.out
// REQUIRES: executable_test
// REQUIRES: CPU=x86_64

import StdlibUnittest
import Darwin

extension FixedWidthInteger {
  /// Returns the high and low parts of a potentially overflowing addition.
  func addingFullWidth(_ other: Self) ->
    (high: Self, low: Self) {
    let sum = self.addingReportingOverflow(other)
    return (sum.overflow == .overflow ? 1 : 0, sum.partialValue)
  }

  /// Returns the high and low parts of two seqeuential potentially overflowing
  /// additions.
  static func addingFullWidth(_ x: Self, _ y: Self, _ z: Self) ->
    (high: Self, low: Self) {
    let xy = x.addingReportingOverflow(y)
    let xyz = xy.partialValue.addingReportingOverflow(z)
    let high: Self = (xy.overflow == .overflow ? 1 : 0) +
      (xyz.overflow == .overflow ? 1 : 0)
    return (high, xyz.partialValue)
  }

  /// Returns a tuple containing the value that would be borrowed from a higher
  /// place and the partial difference of this value and `rhs`.
  func subtractingWithBorrow(_ rhs: Self) ->
    (borrow: Self, partialValue: Self) {
    let difference = subtractingReportingOverflow(rhs)
    return (difference.overflow == .overflow ? 1 : 0, difference.partialValue)
  }

  /// Returns a tuple containing the value that would be borrowed from a higher
  /// place and the partial value of `x` and `y` subtracted from this value.
  func subtractingWithBorrow(_ x: Self, _ y: Self) ->
    (borrow: Self, partialValue: Self) {
    let firstDifference = subtractingReportingOverflow(x)
    let secondDifference =
      firstDifference.partialValue.subtractingReportingOverflow(y)
    let borrow: Self = (firstDifference.overflow == .overflow ? 1 : 0) +
      (secondDifference.overflow == .overflow ? 1 : 0)
    return (borrow, secondDifference.partialValue)
  }
}

//===--- BigInt -----------------------------------------------------------===//
//===----------------------------------------------------------------------===//

/// A dynamically-sized signed integer.
///
/// The `_BigInt` type is fully generic on the size of its "word" -- the
/// `BigInt` alias uses the system's word-sized `UInt` as its word type, but
/// any word size should work properly.
public struct _BigInt<Word: FixedWidthInteger & UnsignedInteger> :
  BinaryInteger, SignedInteger, CustomStringConvertible,
  CustomDebugStringConvertible
  where Word.Magnitude == Word
{

  /// The binary representation of the value's magnitude, with the least
  /// significant word at index `0`.
  ///
  /// - `_data` has no trailing zero elements
  /// - If `self == 0`, then `isNegative == false` and `_data == []`
  internal var _data: [Word] = []

  /// A Boolean value indicating whether this instance is negative.
  public private(set) var isNegative = false

  /// A Boolean value indicating whether this instance is equal to zero.
  public var isZero: Bool {
    return _data.count == 0
  }

  //===--- Numeric initializers -------------------------------------------===//

  /// Creates a new instance equal to zero.
  public init() { }

  /// Creates a new instance using `_data` as the data collection.
  init<C: Collection>(_ _data: C) where C.Iterator.Element == Word {
    self._data = Array(_data)
    _standardize()
  }

  public init(integerLiteral value: Int) {
    self.init(value)
  }

  public init<T : BinaryInteger>(_ source: T) {
    var source = source
    if source < 0 as T {
      if source.bitWidth <= UInt64.bitWidth {
        let sourceMag = Int(extendingOrTruncating: source).magnitude
        self = _BigInt(sourceMag)
        self.isNegative = true
        return
      } else {
        // Have to kind of assume that we're working with another BigInt here
        self.isNegative = true
        source *= -1
      }
    }

    // FIXME: This is broken on 32-bit arch w/ Word = UInt64
    let wordRatio = UInt.bitWidth / Word.bitWidth
    _sanityCheck(wordRatio != 0)
    for var sourceWord in source.words {
      for _ in 0..<wordRatio {
        _data.append(Word(extendingOrTruncating: sourceWord))
        sourceWord >>= Word.bitWidth
      }
    }
    _standardize()
  }

  public init?<T : BinaryInteger>(exactly source: T) {
    self.init(source)
  }

  public init<T : BinaryInteger>(extendingOrTruncating source: T) {
    self.init(source)
  }

  public init<T : BinaryInteger>(clamping source: T) {
    self.init(source)
  }

  public init<T : FloatingPoint>(_ source: T) {
    fatalError("Not implemented")
  }

  public init?<T : FloatingPoint>(exactly source: T) {
    fatalError("Not implemented")
  }

  /// Returns a randomly-generated word.
  static func _randomWord() -> Word {
    // This handles up to a 64-bit word
    if Word.bitWidth > UInt32.bitWidth {
      return Word(arc4random()) << 32 | Word(arc4random())
    } else {
      return Word(extendingOrTruncating: arc4random())
    }
  }

  /// Creates a new instance whose magnitude has `randomBits` bits of random
  /// data. The sign of the new value is randomly selected.
  public init(randomBits: Int) {
    let (words, extraBits) =
      randomBits.quotientAndRemainder(dividingBy: Word.bitWidth)

    // Get the bits for any full words.
    self._data = (0..<words).map({ _ in _BigInt._randomWord() })

    // Get another random number - the highest bit will determine the sign,
    // while the lower `Word.bitWidth - 1` bits are available for any leftover
    // bits in `randomBits`.
    let word = _BigInt._randomWord()
    if extraBits != 0 {
      let mask = ~((~0 as Word) << Word(extraBits))
      _data.append(word & mask)
    }
    isNegative = word & ~(~0 >> 1) == 0

    _standardize()
  }

  //===--- Private methods ------------------------------------------------===//

  /// Standardizes this instance after mutation, removing trailing zeros
  /// and making sure zero is nonnegative. Calling this method satisfies the
  /// two invariants.
  mutating func _standardize(source: String = #function) {
    defer { _checkInvariants(source: source + " >> _standardize()") }
    while _data.last == 0 {
      _data.removeLast()
    }
    // Zero is never negative.
    isNegative = isNegative && _data.count != 0
  }

  /// Checks and asserts on invariants -- all invariants must be satisfied
  /// at the end of every mutating method.
  ///
  /// - `_data` has no trailing zero elements
  /// - If `self == 0`, then `isNegative == false`
  func _checkInvariants(source: String = #function) {
    if _data.count == 0 {
      assert(isNegative == false,
        "\(source): isNegative with zero length _data")
    }
    assert(_data.last != 0, "\(source): extra zeroes on _data")
  }

  //===--- Word-based arithmetic ------------------------------------------===//

  mutating func _unsignedAdd(_ rhs: Word) {
    defer { _standardize() }

    // Quick return if `rhs == 0`
    guard rhs != 0 else { return }

    // Quick return if `self == 0`
    if isZero {
      _data.append(rhs)
      return
    }

    // Add `rhs` to the first word, catching any carry.
    var carry: Word
    (carry, _data[0]) = _data[0].addingFullWidth(rhs)

    // Handle any additional carries
    for i in 1..<_data.count {
      // No more action needed if there's nothing to carry
      if carry == 0 { break }
      (carry, _data[i]) = _data[i].addingFullWidth(carry)
    }

    // If there's any carry left, add it now
    if carry != 0 {
      _data.append(1)
    }
  }

  /// Subtracts `rhs` from this instance, ignoring the sign.
  ///
  /// - Precondition: `rhs <= self.magnitude`
  mutating func _unsignedSubtract(_ rhs: Word) {
    _precondition(_data.count > 1 || _data[0] > rhs)

    // Quick return if `rhs == 0`
    guard rhs != 0 else { return }

    // If `isZero == true`, then `rhs` must also be zero.
    _precondition(!isZero)

    var carry: Word
    (carry, _data[0]) = _data[0].subtractingWithBorrow(rhs)

    for i in 1..<_data.count {
      // No more action needed if there's nothing to carry
      if carry == 0 { break }
      (carry, _data[i]) = _data[i].subtractingWithBorrow(carry)
    }
    _sanityCheck(carry == 0)

    _standardize()
  }

  /// Adds `rhs` to this instance.
  mutating func add(_ rhs: Word) {
    if isNegative {
      // If _data only contains one word and `rhs` is greater, swap them,
      // make self positive and continue with unsigned subtraction.
      var rhs = rhs
      if _data.count == 1 && _data[0] < rhs {
        swap(&rhs, &_data[0])
        isNegative = false
      }
      _unsignedSubtract(rhs)
    } else {   // positive or zero
      _unsignedAdd(rhs)
    }
  }

  /// Subtracts `rhs` from this instance.
  mutating func subtract(_ rhs: Word) {
    guard rhs != 0 else { return }

    if isNegative {
      _unsignedAdd(rhs)
    } else if isZero {
      isNegative = true
      _data.append(rhs)
    } else {
      var rhs = rhs
      if _data.count == 1 && _data[0] < rhs {
        swap(&rhs, &_data[0])
        isNegative = true
      }
      _unsignedSubtract(rhs)
    }
  }

  /// Multiplies this instance by `rhs`.
  mutating func multiply(by rhs: Word) {
    // If either `self` or `rhs` is zero, the result is zero.
    guard !isZero && rhs != 0 else {
      self = 0
      return
    }

    // If `rhs` is a power of two, can just left shift `self`.
    let rhsLSB = rhs.trailingZeroBitCount
    if rhs >> rhsLSB == 1 {
      self <<= rhsLSB
      return
    }

    var carry: Word = 0
    for i in 0..<_data.count {
      let product = _data[i].multipliedFullWidth(by: rhs)
      (carry, _data[i]) = product.low.addingFullWidth(carry)
      carry = carry &+ product.high
    }

    // Add the leftover carry
    if carry != 0 {
      _data.append(carry)
    }
    _standardize()
  }

  /// Divides this instance by `rhs`, returning the remainder.
  @discardableResult
  mutating func divide(by rhs: Word) -> Word {
    _precondition(rhs != 0, "divide by zero")

    // No-op if `rhs == 1` or `self == 0`.
    if rhs == 1 || isZero {
      return 0
    }

    // If `rhs` is a power of two, can just right shift `self`.
    let rhsLSB = rhs.trailingZeroBitCount
    if rhs >> rhsLSB == 1 {
      defer { self >>= rhsLSB }
      return _data[0] & ~(~0 << rhsLSB)
    }

    var carry: Word = 0
    for i in (0..<_data.count).reversed() {
      let lhs = (high: carry, low: _data[i])
      (_data[i], carry) = rhs.dividingFullWidth(lhs)
    }

    _standardize()
    return carry
  }

  //===--- Numeric --------------------------------------------------------===//

  public typealias Magnitude = _BigInt

  public var magnitude: _BigInt {
    var result = self
    result.isNegative = false
    return result
  }

  /// Adds `rhs` to this instance, ignoring any signs.
  mutating func _unsignedAdd(_ rhs: _BigInt) {
    defer { _checkInvariants() }

    let commonCount = Swift.min(_data.count, rhs._data.count)
    let maxCount = Swift.max(_data.count, rhs._data.count)
    _data.reserveCapacity(maxCount)

    // Add the words up to the common count, carrying any overflows
    var carry: Word = 0
    for i in 0..<commonCount {
      (carry, _data[i]) = Word.addingFullWidth(_data[i], rhs._data[i], carry)
    }

    // If there are leftover words in `self`, just need to handle any carries
    if _data.count > rhs._data.count {
      for i in commonCount..<maxCount {
        // No more action needed if there's nothing to carry
        if carry == 0 { break }
        (carry, _data[i]) = _data[i].addingFullWidth(carry)
      }

    // If there are leftover words in `rhs`, need to copy to `self` with carries
    } else if _data.count < rhs._data.count {
      for i in commonCount..<maxCount {
        // Append remaining words if nothing to carry
        if carry == 0 {
          _data.append(contentsOf: rhs._data.suffix(from: i))
          break
        }
        let sum: Word
        (carry, sum) = rhs._data[i].addingFullWidth(carry)
        _data.append(sum)
      }
    }

    // If there's any carry left, add it now
    if carry != 0 {
      _data.append(1)
    }
  }

  /// Subtracts `rhs` from this instance, ignoring the sign.
  ///
  /// - Precondition: `rhs.magnitude <= self.magnitude` (unchecked)
  /// - Precondition: `rhs._data.count <= self._data.count`
  mutating func _unsignedSubtract(_ rhs: _BigInt) {
    _precondition(rhs._data.count <= _data.count)

    var carry: Word = 0
    for i in 0..<rhs._data.count {
      (carry, _data[i]) = _data[i].subtractingWithBorrow(rhs._data[i], carry)
    }

    for i in rhs._data.count..<_data.count {
      // No more action needed if there's nothing to carry
      if carry == 0 { break }
      (carry, _data[i]) = _data[i].subtractingWithBorrow(carry)
    }
    _sanityCheck(carry == 0)

    _standardize()
  }

  public static func +=(lhs: inout _BigInt, rhs: _BigInt) {
    defer { lhs._checkInvariants() }
    if lhs.isNegative == rhs.isNegative {
      lhs._unsignedAdd(rhs)
    } else {
      lhs -= -rhs
    }
  }

  public static func -=(lhs: inout _BigInt, rhs: _BigInt) {
    defer { lhs._checkInvariants() }

    // Subtracting something of the opposite sign just adds magnitude.
    guard lhs.isNegative == rhs.isNegative else {
      lhs._unsignedAdd(rhs)
      return
    }

    // Comare `lhs` and `rhs` so we can use `_unsignedSubtract` to subtract
    // the smaller magnitude from the larger magnitude.
    switch lhs._compareMagnitude(to: rhs) {
    case .equal:
      lhs = 0
    case .greaterThan:
      lhs._unsignedSubtract(rhs)
    case .lessThan:
      // x - y == -y + x == -(y - x)
      var result = rhs
      result._unsignedSubtract(lhs)
      result.isNegative = !lhs.isNegative
      lhs = result
    }
  }

  public static func *=(lhs: inout _BigInt, rhs: _BigInt) {
    // If either `lhs` or `rhs` is zero, the result is zero.
    guard !lhs.isZero && !rhs.isZero else {
      lhs = 0
      return
    }

    var newData: [Word] = Array(repeating: 0,
      count: lhs._data.count + rhs._data.count)
    let (a, b) = lhs._data.count > rhs._data.count
      ? (lhs._data, rhs._data)
      : (rhs._data, lhs._data)
    _sanityCheck(a.count >= b.count)

    var carry: Word = 0
    for ai in 0..<a.count {
      carry = 0
      for bi in 0..<b.count {
        // Each iteration needs to perform this operation:
        //
        //     newData[ai + bi] += (a[ai] * b[bi]) + carry
        //
        // However, `a[ai] * b[bi]` produces a double-width result, and both
        // additions can overflow to a higher word. The following two lines
        // capture the low word of the multiplication and additions in
        // `newData[ai + bi]` and any addition overflow in `carry`.
        let product = a[ai].multipliedFullWidth(by: b[bi])
        (carry, newData[ai + bi]) = Word.addingFullWidth(
          newData[ai + bi], product.low, carry)

        // Now we combine the high word of the multiplication with any addition
        // overflow. It is safe to add `product.high` and `carry` here without
        // checking for overflow, because if `product.high == .max - 1`, then
        // `carry <= 1`. Otherwise, `carry <= 2`.
        //
        // Worst-case (aka 9 + 9*9 + 9):
        //
        //       newData         a[ai]        b[bi]         carry
        //      0b11111111 + (0b11111111 * 0b11111111) + 0b11111111
        //      0b11111111 + (0b11111110_____00000001) + 0b11111111
        //                   (0b11111111_____00000000) + 0b11111111
        //                   (0b11111111_____11111111)
        //
        // Second-worse case:
        //
        //      0b11111111 + (0b11111111 * 0b11111110) + 0b11111111
        //      0b11111111 + (0b11111101_____00000010) + 0b11111111
        //                   (0b11111110_____00000001) + 0b11111111
        //                   (0b11111111_____00000000)
        _sanityCheck(
          product.high.addingReportingOverflow(carry).overflow == .none)
        carry = product.high &+ carry
      }

      // Leftover `carry` is inserted in new highest word.
      _sanityCheck(newData[ai + b.count] == 0)
      newData[ai + b.count] = carry
    }

    lhs._data = newData
    lhs.isNegative = lhs.isNegative != rhs.isNegative
    lhs._standardize()
  }

  /// Divides this instance by `rhs`, returning the remainder.
  @discardableResult
  mutating func _internalDivide(by rhs: _BigInt) -> _BigInt {
    _precondition(!rhs.isZero, "Divided by zero")
    defer { _checkInvariants() }

    // Handle quick cases that don't require division:
    // If `abs(self) < abs(rhs)`, the result is zero, remainder = self
    // If `abs(self) == abs(rhs)`, the result is 1 or -1, remainder = 0
    switch _compareMagnitude(to: rhs) {
    case .lessThan:
      defer { self = 0 }
      return self
    case .equal:
      self = isNegative != rhs.isNegative ? -1 : 1
      return 0
    default:
      break
    }

    var tempSelf = self.magnitude
    let n = tempSelf.bitWidth - rhs.magnitude.bitWidth
    var quotient: _BigInt = 0
    var tempRHS = rhs.magnitude << n
    var tempQuotient: _BigInt = 1 << n

    for _ in (0...n).reversed() {
      if tempRHS._compareMagnitude(to: tempSelf) != .greaterThan {
        tempSelf -= tempRHS
        quotient += tempQuotient
      }
      tempRHS >>= 1
      tempQuotient >>= 1
    }

    // `tempSelf` is the remainder - match sign of original `self`
    tempSelf.isNegative = self.isNegative
    tempSelf._standardize()

    quotient.isNegative = isNegative != rhs.isNegative
    self = quotient
    _standardize()

    return tempSelf
  }

  public static func /=(lhs: inout _BigInt, rhs: _BigInt) {
    lhs._internalDivide(by: rhs)
  }

  // FIXME: Remove once default implementations are provided:

  public static func +(_ lhs: _BigInt, _ rhs: _BigInt) -> _BigInt {
    var lhs = lhs
    lhs += rhs
    return lhs
  }

  public static func -(_ lhs: _BigInt, _ rhs: _BigInt) -> _BigInt {
    var lhs = lhs
    lhs -= rhs
    return lhs
  }

  public static func *(_ lhs: _BigInt, _ rhs: _BigInt) -> _BigInt {
    var lhs = lhs
    lhs *= rhs
    return lhs
  }

  public static func /(_ lhs: _BigInt, _ rhs: _BigInt) -> _BigInt {
    var lhs = lhs
    lhs /= rhs
    return lhs
  }

  public static func %(_ lhs: _BigInt, _ rhs: _BigInt) -> _BigInt {
    var lhs = lhs
    lhs %= rhs
    return lhs
  }

  //===--- BinaryInteger --------------------------------------------------===//

  /// Creates a new instance using the given data array in two's complement
  /// representation.
  init(_twosComplementData: [Word]) {
    guard _twosComplementData.count > 0 else {
      self = 0
      return
    }

    // Is the highest bit set?
    isNegative = _twosComplementData.last!.leadingZeroBitCount == 0
    if isNegative {
      _data = _twosComplementData.map(~)
      self._unsignedAdd(1 as Word)
    } else {
      _data = _twosComplementData
    }
    _standardize()
  }

  /// Returns an array of the value's data using two's complement representation.
  func _dataAsTwosComplement() -> [Word] {
    // Special cases:
    // * Nonnegative values are already in 2's complement
    if !isNegative {
      // Positive values need to have a leading zero bit
      if _data.last?.leadingZeroBitCount == 0 {
        return _data + [0]
      } else {
        return _data
      }
    }
    // * -1 will get zeroed out below, easier to handle here
    if _data.count == 1 && _data.first == 1 { return [~0] }

    var x = self
    x._unsignedSubtract(1 as Word)

    if x._data.last!.leadingZeroBitCount == 0 {
      // The highest bit is set to 1, which moves to 0 after negation.
      // We need to add another word at the high end so the highest bit is 1.
      return x._data.map(~) + [Word.max]
    } else {
      // The highest bit is set to 0, which moves to 1 after negation.
      return x._data.map(~)
    }
  }

  public var words: [UInt] {
    _sanityCheck(UInt.bitWidth % Word.bitWidth == 0)
    let twosComplementData = _dataAsTwosComplement()
    var words: [UInt] = []
    words.reserveCapacity((twosComplementData.count * Word.bitWidth 
      + UInt.bitWidth - 1) / UInt.bitWidth)
    var word: UInt = 0
    var shift = 0
    for w in twosComplementData {
      word |= UInt(extendingOrTruncating: w) << shift
      shift += Word.bitWidth
      if shift == UInt.bitWidth {
        words.append(word)
        word = 0
        shift = 0
      }
    }
    if shift != 0 {
      if isNegative {
        word |= ~((1 << shift) - 1)
      }
      words.append(word)
    }
    return words
  }

  /// The number of bits used for storage of this value. Always a multiple of
  /// `Word.bitWidth`.
  public var bitWidth: Int {
    if isZero {
      return 0
    } else {
      let twosComplementData = _dataAsTwosComplement()

      // If negative, it's okay to have 1s padded on high end
      if isNegative {
        return twosComplementData.count * Word.bitWidth
      }

      // If positive, need to make space for at least one zero on high end
      return twosComplementData.count * Word.bitWidth
        - twosComplementData.last!.leadingZeroBitCount + 1
    }
  }

  /// The number of sequential zeros in the least-significant position of this
  /// value's binary representation.
  ///
  /// The numbers 1 and zero have zero trailing zeros.
  public var trailingZeroBitCount: Int {
    guard !isZero else {
      return 0
    }

    let i = _data.index(where: { $0 != 0 })!
    _sanityCheck(_data[i] != 0)
    return i * Word.bitWidth + _data[i].trailingZeroBitCount
  }

  public static func %=(lhs: inout _BigInt, rhs: _BigInt) {
    defer { lhs._checkInvariants() }
    lhs = lhs._internalDivide(by: rhs)
  }

  public func quotientAndRemainder(dividingBy rhs: _BigInt) ->
    (_BigInt, _BigInt)
  {
    var x = self
    let r = x._internalDivide(by: rhs)
    return (x, r)
  }

  public static func &=(lhs: inout _BigInt, rhs: _BigInt) {
    var lhsTemp = lhs._dataAsTwosComplement()
    let rhsTemp = rhs._dataAsTwosComplement()

    // If `lhs` is longer than `rhs`, behavior depends on sign of `rhs`
    // * If `rhs < 0`, length is extended with 1s
    // * If `rhs >= 0`, length is extended with 0s, which crops `lhsTemp`
    if lhsTemp.count > rhsTemp.count && !rhs.isNegative {
      lhsTemp.removeLast(lhsTemp.count - rhsTemp.count)
    }

    // If `rhs` is longer than `lhs`, behavior depends on sign of `lhs`
    // * If `lhs < 0`, length is extended with 1s, so `lhs` should get extra
    //   bits from `rhs`
    // * If `lhs >= 0`, length is extended with 0s
    if lhsTemp.count < rhsTemp.count && lhs.isNegative {
      lhsTemp.append(contentsOf: rhsTemp[lhsTemp.count..<rhsTemp.count])
    }

    // Perform bitwise & on words that both `lhs` and `rhs` have.
    for i in 0..<Swift.min(lhsTemp.count, rhsTemp.count) {
      lhsTemp[i] &= rhsTemp[i]
    }

    lhs = _BigInt(_twosComplementData: lhsTemp)
  }

  public static func |=(lhs: inout _BigInt, rhs: _BigInt) {
    var lhsTemp = lhs._dataAsTwosComplement()
    let rhsTemp = rhs._dataAsTwosComplement()

    // If `lhs` is longer than `rhs`, behavior depends on sign of `rhs`
    // * If `rhs < 0`, length is extended with 1s, so those bits of `lhs`
    //   should all be 1
    // * If `rhs >= 0`, length is extended with 0s, which is a no-op
    if lhsTemp.count > rhsTemp.count && rhs.isNegative {
      lhsTemp.replaceSubrange(rhsTemp.count..<lhsTemp.count,
        with: repeatElement(Word.max, count: lhsTemp.count - rhsTemp.count))
    }

    // If `rhs` is longer than `lhs`, behavior depends on sign of `lhs`
    // * If `lhs < 0`, length is extended with 1s, so those bits of lhs
    //   should all be 1
    // * If `lhs >= 0`, length is extended with 0s, so those bits should be
    //   copied from rhs
    if lhsTemp.count < rhsTemp.count {
      if lhs.isNegative {
        lhsTemp.append(contentsOf:
          repeatElement(Word.max, count: rhsTemp.count - lhsTemp.count))
      } else {
        lhsTemp.append(contentsOf: rhsTemp[lhsTemp.count..<rhsTemp.count])
      }
    }

    // Perform bitwise | on words that both `lhs` and `rhs` have.
    for i in 0..<Swift.min(lhsTemp.count, rhsTemp.count) {
      lhsTemp[i] |= rhsTemp[i]
    }

    lhs = _BigInt(_twosComplementData: lhsTemp)
  }

  public static func ^=(lhs: inout _BigInt, rhs: _BigInt) {
    var lhsTemp = lhs._dataAsTwosComplement()
    let rhsTemp = rhs._dataAsTwosComplement()

    // If `lhs` is longer than `rhs`, behavior depends on sign of `rhs`
    // * If `rhs < 0`, length is extended with 1s, so those bits of `lhs`
    //   should all be flipped
    // * If `rhs >= 0`, length is extended with 0s, which is a no-op
    if lhsTemp.count > rhsTemp.count && rhs.isNegative {
      for i in rhsTemp.count..<lhsTemp.count {
        lhsTemp[i] = ~lhsTemp[i]
      }
    }

    // If `rhs` is longer than `lhs`, behavior depends on sign of `lhs`
    // * If `lhs < 0`, length is extended with 1s, so those bits of `lhs`
    //   should all be flipped copies of `rhs`
    // * If `lhs >= 0`, length is extended with 0s, so those bits should
    //   be copied from rhs
    if lhsTemp.count < rhsTemp.count {
      if lhs.isNegative {
        lhsTemp += rhsTemp.suffix(from: lhsTemp.count).map(~)
      } else {
        lhsTemp.append(contentsOf: rhsTemp[lhsTemp.count..<rhsTemp.count])
      }
    }

    // Perform bitwise ^ on words that both `lhs` and `rhs` have.
    for i in 0..<Swift.min(lhsTemp.count, rhsTemp.count) {
      lhsTemp[i] ^= rhsTemp[i]
    }

    lhs = _BigInt(_twosComplementData: lhsTemp)
  }

  public static prefix func ~(x: _BigInt) -> _BigInt {
    return -x - 1
  }

  //===--- SignedNumeric --------------------------------------------------===//

  public static prefix func -(x: inout _BigInt) {
    defer { x._checkInvariants() }
    guard x._data.count > 0 else { return }
    x.isNegative = !x.isNegative
  }

  //===--- Strideable -----------------------------------------------------===//

  public func distance(to other: _BigInt) -> _BigInt {
    return other - self
  }

  public func advanced(by n: _BigInt) -> _BigInt {
    return self + n
  }

  //===--- Other arithmetic -----------------------------------------------===//

  /// Returns the greatest common divisor for this value and `other`.
  public func greatestCommonDivisor(with other: _BigInt) -> _BigInt {
    // Quick return if either is zero
    if other.isZero {
      return magnitude
    }
    if isZero {
      return other.magnitude
    }

    var (x, y) = (self.magnitude, other.magnitude)
    let (xLSB, yLSB) = (x.trailingZeroBitCount, y.trailingZeroBitCount)

    // Remove any common factor of two
    let commonPower = Swift.min(xLSB, yLSB)
    x >>= commonPower
    y >>= commonPower

    // Remove any remaining factor of two
    if xLSB != commonPower {
      x >>= xLSB - commonPower
    }
    if yLSB != commonPower {
      y >>= yLSB - commonPower
    }

    while !x.isZero {
      // Swap values to ensure that `x >= y`.
      if x._compareMagnitude(to: y) == .lessThan {
        swap(&x, &y)
      }

      // Subtract smaller and remove any factors of two
      x._unsignedSubtract(y)
      x >>= x.trailingZeroBitCount
    }

    // Add original common factor of two back into result
    y <<= commonPower
    return y
  }

  /// Returns the lowest common multiple for this value and `other`.
  public func lowestCommonMultiple(with other: _BigInt) -> _BigInt {
    let gcd = greatestCommonDivisor(with: other)
    if _compareMagnitude(to: other) == .lessThan {
      return ((self / gcd) * other).magnitude
    } else {
      return ((other / gcd) * self).magnitude
    }
  }

  //===--- String methods ------------------------------------------------===//

  /// Creates a new instance from the given string.
  ///
  /// - Parameters:
  ///   - source: The string to parse for the new instance's value. If a
  ///     character in `source` is not in the range `0...9` or `a...z`, case
  ///     insensitive, or is not less than `radix`, the result is `nil`.
  ///   - radix: The radix to use when parsing `source`. `radix` must be in the
  ///     range `2...36`. The default is `10`.
  public init?(_ source: String, radix: Int = 10) {
    assert(2...36 ~= radix, "radix must be in range 2...36")
    let radix = Word(radix)

    func valueForCodeUnit(_ unit: Unicode.UTF16.CodeUnit) -> Word? {
      switch unit {
      // "0"..."9"
      case 48...57: return Word(unit - 48)
      // "a"..."z"
      case 97...122: return Word(unit - 87)
      // "A"..."Z"
      case 65...90: return Word(unit - 55)
      // invalid character
      default: return nil
      }
    }

    var source = source

    // Check for a single prefixing hyphen
    let negative = source.hasPrefix("-")
    if negative {
      source = String(source.characters.dropFirst())
    }

    // Loop through characters, multiplying
    for v in source.utf16.map(valueForCodeUnit) {
      // Character must be valid and less than radix
      guard let v = v else { return nil }
      guard v < radix else { return nil }

      self.multiply(by: radix)
      self.add(v)
    }

    self.isNegative = negative
  }

  /// Returns a string representation of this instance.
  ///
  /// - Parameters:
  ///   - radix: The radix to use when converting this instance to a string.
  ///     The value passed as `radix` must be in the range `2...36`. The
  ///     default is `10`.
  ///   - lowercase: Whether to use lowercase letters to represent digits
  ///     greater than 10. The default is `true`.
  public func toString(radix: Int = 10, lowercase: Bool = true) -> String {
    assert(2...36 ~= radix, "radix must be in range 2...36")

    let digitsStart = ("0" as Unicode.Scalar).value
    let lettersStart = ((lowercase ? "a" : "A") as Unicode.Scalar).value - 10
    func toLetter(_ x: UInt32) -> Unicode.Scalar {
      return x < 10
        ? Unicode.Scalar(digitsStart + x)!
        : Unicode.Scalar(lettersStart + x)!
    }

    let radix = _BigInt(radix)
    var result: [Unicode.Scalar] = []

    var x = self.magnitude
    while !x.isZero {
      let remainder: _BigInt
      (x, remainder) = x.quotientAndRemainder(dividingBy: radix)
      result.append(toLetter(UInt32(remainder)))
    }

    let sign = isNegative ? "-" : ""
    let rest = result.count == 0
      ? "0"
      : String(String.UnicodeScalarView(result.reversed()))
    return sign + rest
  }

  public var description: String {
    return decimalString
  }

  public var debugDescription: String {
    return "_BigInt(\(hexString), words: \(_data.count))"
  }

  /// A string representation of this instance's value in base 2.
  public var binaryString: String {
    return toString(radix: 2)
  }

  /// A string representation of this instance's value in base 10.
  public var decimalString: String {
    return toString(radix: 10)
  }

  /// A string representation of this instance's value in base 16.
  public var hexString: String {
    return toString(radix: 16, lowercase: false)
  }

  /// A string representation of this instance's value in base 36.
  public var compactString: String {
    return toString(radix: 36, lowercase: false)
  }

  //===--- Comparable -----------------------------------------------------===//

  enum _ComparisonResult {
    case lessThan, equal, greaterThan
  }

  /// Returns whether this instance is less than, greather than, or equal to
  /// the given value.
  func _compare(to rhs: _BigInt) -> _ComparisonResult {
    // Negative values are less than positive values
    guard isNegative == rhs.isNegative else {
      return isNegative ? .lessThan : .greaterThan
    }

    switch _compareMagnitude(to: rhs) {
    case .equal:
      return .equal
    case .lessThan:
      return isNegative ? .greaterThan : .lessThan
    case .greaterThan:
      return isNegative ? .lessThan : .greaterThan
    }
  }

  /// Returns whether the magnitude of this instance is less than, greather
  /// than, or equal to the magnitude of the given value.
  func _compareMagnitude(to rhs: _BigInt) -> _ComparisonResult {
    guard _data.count == rhs._data.count else {
      return _data.count < rhs._data.count ? .lessThan : .greaterThan
    }

    // Equal number of words: compare from most significant word
    for i in (0..<_data.count).reversed() {
      if _data[i] < rhs._data[i] { return .lessThan }
      if _data[i] > rhs._data[i] { return .greaterThan }
    }
    return .equal
  }

  public static func ==(lhs: _BigInt, rhs: _BigInt) -> Bool {
    return lhs._compare(to: rhs) == .equal
  }

  public static func < (lhs: _BigInt, rhs: _BigInt) -> Bool {
    return lhs._compare(to: rhs) == .lessThan
  }

  //===--- Hashable -------------------------------------------------------===//

  public var hashValue: Int {
#if arch(i386) || arch(arm)
    let p: UInt = 16777619
    let h: UInt = (2166136261 &* p) ^ (isNegative ? 1 : 0)
#elseif arch(x86_64) || arch(arm64) || arch(powerpc64) || arch(powerpc64le) || arch(s390x)
    let p: UInt = 1099511628211
    let h: UInt = (14695981039346656037 &* p) ^ (isNegative ? 1 : 0)
#else
    fatalError("Unimplemented")
#endif
    return Int(bitPattern: _data.reduce(h, { ($0 &* p) ^ UInt($1) }))
  }

  //===--- Bit shifting operators -----------------------------------------===//

  static func _shiftLeft(_ data: inout [Word], byWords words: Int) {
    guard words > 0 else { return }
    data.insert(contentsOf: repeatElement(0, count: words), at: 0)
  }

  static func _shiftRight(_ data: inout [Word], byWords words: Int) {
    guard words > 0 else { return }
    data.removeFirst(Swift.min(data.count, words))
  }

  public static func <<=(lhs: inout _BigInt, rhs: Int) {
    defer { lhs._checkInvariants() }
    guard rhs != 0 else { return }
    guard rhs > 0 else {
      lhs >>= -rhs
      return
    }

    // We can add `rhs / bits` extra words full of zero at the low end.
    let extraWords = rhs / Word.bitWidth
    lhs._data.reserveCapacity(lhs._data.count + extraWords + 1)
    _BigInt._shiftLeft(&lhs._data, byWords: extraWords)

    // Each existing word will need to be shifted left by `rhs % bits`.
    // For each pair of words, we'll use the high `offset` bits of the
    // lower word and the low `Word.bitWidth - offset` bits of the higher
    // word.
    let highOffset = rhs % Word.bitWidth
    let lowOffset = Word.bitWidth - highOffset

    // If there's no offset, we're finished, as `rhs` was a multiple of
    // `Word.bitWidth`.
    guard highOffset != 0 else { return }

    // Add new word at the end, then shift everything left by `offset` bits.
    lhs._data.append(0)
    for i in ((extraWords + 1)..<lhs._data.count).reversed() {
      lhs._data[i] = lhs._data[i] << highOffset
        | lhs._data[i - 1] >> lowOffset
    }

    // Finally, shift the lowest word.
    lhs._data[extraWords] = lhs._data[extraWords] << highOffset
    lhs._standardize()
  }

  public static func >>=(lhs: inout _BigInt, rhs: Int) {
    defer { lhs._checkInvariants() }
    guard rhs != 0 else { return }
    guard rhs > 0 else {
      lhs <<= -rhs
      return
    }

    var tempData = lhs._dataAsTwosComplement()

    // We can remove `rhs / bits` full words at the low end.
    // If that removes the entirety of `_data`, we're done.
    let wordsToRemove = rhs / Word.bitWidth
    _BigInt._shiftRight(&tempData, byWords: wordsToRemove)
    guard tempData.count != 0 else {
      lhs = lhs.isNegative ? -1 : 0
      return
    }

    // Each existing word will need to be shifted right by `rhs % bits`.
    // For each pair of words, we'll use the low `offset` bits of the
    // higher word and the high `_BigInt.Word.bitWidth - offset` bits of
    // the lower word.
    let lowOffset = rhs % Word.bitWidth
    let highOffset = Word.bitWidth - lowOffset

    // If there's no offset, we're finished, as `rhs` was a multiple of
    // `Word.bitWidth`.
    guard lowOffset != 0 else {
      lhs = _BigInt(_twosComplementData: tempData)
      return
    }

    // Shift everything right by `offset` bits.
    for i in 0..<(tempData.count - 1) {
      tempData[i] = tempData[i] >> lowOffset |
        tempData[i + 1] << highOffset
    }

    // Finally, shift the highest word and standardize the result.
    tempData[tempData.count - 1] >>= lowOffset
    lhs = _BigInt(_twosComplementData: tempData)
  }

  public static func <<(lhs: _BigInt, rhs: Int) -> _BigInt {
    var lhs = lhs
    lhs <<= rhs
    return lhs
  }

  public static func >>(lhs: _BigInt, rhs: Int) -> _BigInt {
    var lhs = lhs
    lhs >>= rhs
    return lhs
  }
}

//===--- Bit --------------------------------------------------------------===//
//===----------------------------------------------------------------------===//

/// A one-bit fixed width integer.
struct Bit : FixedWidthInteger, UnsignedInteger {
  typealias Magnitude = Bit

  var value: UInt8 = 0

  // Initializers

  init(integerLiteral value: Int) {
    self = Bit(value)
  }

  init(bigEndian value: Bit) {
    self = value
  }

  init(littleEndian value: Bit) {
    self = value
  }

  init?<T: FloatingPoint>(exactly source: T) {
    switch source {
    case T(0): value = 0
    case T(1): value = 1
    default:
      return nil
    }
  }

  init<T: FloatingPoint>(_ source: T) {
    self = Bit(exactly: source.rounded(.down))!
  }

  init<T: BinaryInteger>(_ source: T) {
    switch source {
    case 0: value = 0
    case 1: value = 1
    default:
      fatalError("Can't represent \(source) as a Bit")
    }
  }

  init<T: BinaryInteger>(extendingOrTruncating source: T) {
    value = UInt8(source & 1)
  }

  init(_truncatingBits bits: UInt) {
    value = UInt8(bits & 1)
  }

  init<T: BinaryInteger>(clamping source: T)  {
    value = source >= 1 ? 1 : 0
  }

  // FixedWidthInteger, BinaryInteger

  static var bitWidth: Int {
    return 1
  }

  var bitWidth: Int {
    return 1
  }

  var trailingZeroBitCount: Int {
    return Int(~value & 1)
  }

  static var max: Bit {
    return 1
  }

  static var min: Bit {
    return 0
  }

  static var isSigned: Bool {
    return false
  }

  var nonzeroBitCount: Int {
    return value.nonzeroBitCount
  }

  var leadingZeroBitCount: Int {
    return Int(~value & 1)
  }

  var bigEndian: Bit {
    return self
  }

  var littleEndian: Bit {
    return self
  }

  var byteSwapped: Bit {
    return self
  }

  var words: UInt.Words {
    return UInt(value).words
  }

  // Hashable, CustomStringConvertible

  var hashValue: Int {
    return Int(value)
  }

  var description: String {
    return "\(value)"
  }

  // Arithmetic Operations / Operators

  func _checkOverflow(_ v: UInt8) -> ArithmeticOverflow {
    let mask: UInt8 = ~0 << 1
    return v & mask == 0 ? .none : .overflow
  }
  
  func addingReportingOverflow(_ rhs: Bit) ->
    (partialValue: Bit, overflow: ArithmeticOverflow) {
      let result = value &+ rhs.value
      return (Bit(result & 1), _checkOverflow(result))
  }

  func subtractingReportingOverflow(_ rhs: Bit) ->
    (partialValue: Bit, overflow: ArithmeticOverflow) {
      let result = value &- rhs.value
      return (Bit(result & 1), _checkOverflow(result))
  }

  func multipliedReportingOverflow(by rhs: Bit) ->
    (partialValue: Bit, overflow: ArithmeticOverflow) {
      let result = value &* rhs.value
      return (Bit(result), .none)
  }

  func dividedReportingOverflow(by rhs: Bit) ->
    (partialValue: Bit, overflow: ArithmeticOverflow) {
      return rhs == 0 ? (self, .none) : (self, .overflow)
  }

  func remainderReportingOverflow(dividingBy rhs: Bit) ->
    (partialValue: Bit, overflow: ArithmeticOverflow) {
      fatalError()
  }

  static func +=(lhs: inout Bit, rhs: Bit) {
    let result = lhs.addingReportingOverflow(rhs)
    assert(result.overflow == .none, "Addition overflow")
    lhs = result.partialValue
  }

  static func -=(lhs: inout Bit, rhs: Bit) {
    let result = lhs.subtractingReportingOverflow(rhs)
    assert(result.overflow == .none, "Subtraction overflow")
    lhs = result.partialValue
  }

  static func *=(lhs: inout Bit, rhs: Bit) {
    let result = lhs.multipliedReportingOverflow(by: rhs)
    assert(result.overflow == .none, "Multiplication overflow")
    lhs = result.partialValue
  }

  static func /=(lhs: inout Bit, rhs: Bit) {
    let result = lhs.dividedReportingOverflow(by: rhs)
    assert(result.overflow == .none, "Division overflow")
    lhs = result.partialValue
  }

  static func %=(lhs: inout Bit, rhs: Bit) {
    assert(rhs != 0, "Modulo sum overflow")
    lhs.value = 0 // No remainders with bit division!
  }

  func multipliedFullWidth(by other: Bit) -> (high: Bit, low: Bit) {
      return (0, self * other)
  }

  func dividingFullWidth(_ dividend: (high: Bit, low: Bit)) ->
    (quotient: Bit, remainder: Bit) {
      assert(self != 0, "Division overflow")
      assert(dividend.high == 0, "Quotient overflow")
      return (dividend.low, 0)
  }

  // FIXME: Remove once default implementations are provided:

  public static func +(_ lhs: Bit, _ rhs: Bit) -> Bit {
    var lhs = lhs
    lhs += rhs
    return lhs
  }

  public static func -(_ lhs: Bit, _ rhs: Bit) -> Bit {
    var lhs = lhs
    lhs -= rhs
    return lhs
  }

  public static func *(_ lhs: Bit, _ rhs: Bit) -> Bit {
    var lhs = lhs
    lhs *= rhs
    return lhs
  }

  public static func /(_ lhs: Bit, _ rhs: Bit) -> Bit {
    var lhs = lhs
    lhs /= rhs
    return lhs
  }

  public static func %(_ lhs: Bit, _ rhs: Bit) -> Bit {
    var lhs = lhs
    lhs %= rhs
    return lhs
  }

  // Bitwise operators

  static prefix func ~(x: Bit) -> Bit {
    return Bit(~x.value & 1)
  }

  // Why doesn't the type checker complain about these being missing?
  static func &=(lhs: inout Bit, rhs: Bit) {
    lhs.value &= rhs.value
  }

  static func |=(lhs: inout Bit, rhs: Bit) {
    lhs.value |= rhs.value
  }

  static func ^=(lhs: inout Bit, rhs: Bit) {
    lhs.value ^= rhs.value
  }

  static func ==(lhs: Bit, rhs: Bit) -> Bool {
    return lhs.value == rhs.value
  }

  static func <(lhs: Bit, rhs: Bit) -> Bool {
    return lhs.value < rhs.value
  }

  static func <<(lhs: Bit, rhs: Bit) -> Bit {
    return rhs == 0 ? lhs : 0
  }

  static func >>(lhs: Bit, rhs: Bit) -> Bit {
    return rhs == 0 ? lhs : 0
  }

  static func <<=(lhs: inout Bit, rhs: Bit) {
    if rhs != 0 {
      lhs = 0
    }
  }

  static func >>=(lhs: inout Bit, rhs: Bit) {
    if rhs != 0 {
      lhs = 0
    }
  }
}

//===--- Tests ------------------------------------------------------------===//
//===----------------------------------------------------------------------===//

typealias BigInt = _BigInt<UInt>
typealias BigInt8 = _BigInt<UInt8>

typealias BigIntBit = _BigInt<Bit>

func testBinaryInit<T: BinaryInteger>(_ x: T) -> BigInt {
  return BigInt(x)
}

func randomBitLength() -> Int {
  return Int(arc4random_uniform(1000) + 2)
}

var BitTests = TestSuite("Bit")

BitTests.test("Basics") {
  let x = Bit.max
  let y = Bit.min

  expectTrue(x == 1 as Int)
  expectTrue(y == 0 as Int)
  expectTrue(x < Int.max)

  expectGT(x, y)
  expectEqual(x, x)
  expectEqual(x, x ^ 0)
  expectGT(x, x & 0)
  expectEqual(x, x | 0)
  expectLT(y, y | 1)
  expectEqual(x, ~y)
  expectEqual(y, ~x)

  expectEqual(x, x + y)
  expectGT(x, x &+ x)
  
  expectEqual(1, x.nonzeroBitCount)
  expectEqual(0, y.nonzeroBitCount)

  expectEqual(0, x.leadingZeroBitCount)
  expectEqual(1, y.leadingZeroBitCount)

  expectEqual(0, x.trailingZeroBitCount)
  expectEqual(1, y.trailingZeroBitCount)
}

var BigIntTests = TestSuite("BigInt")

BigIntTests.test("Initialization") {
  let x = testBinaryInit(1_000_000 as Int)
  expectEqual(x._data[0], 1_000_000)

  let y = testBinaryInit(1_000 as UInt16)
  expectEqual(y._data[0], 1_000)

  let z = testBinaryInit(-1_000_000 as Int)
  expectEqual(z._data[0], 1_000_000)
  expectTrue(z.isNegative)

  let z6 = testBinaryInit(z * z * z * z * z * z)
  expectEqual(z6._data, [12919594847110692864, 54210108624275221])
  expectFalse(z6.isNegative)
}

BigIntTests.test("Identity/Fixed point") {
  let x = BigInt(repeatElement(UInt.max, count: 20))
  let y = -x

  expectEqual(x / x, 1)
  expectEqual(x / y, -1)
  expectEqual(y / x, -1)
  expectEqual(y / y, 1)
  expectEqual(x % x, 0)
  expectEqual(x % y, 0)
  expectEqual(y % x, 0)
  expectEqual(y % y, 0)

  expectEqual(x * 1, x)
  expectEqual(y * 1, y)
  expectEqual(x * -1, y)
  expectEqual(y * -1, x)
  expectEqual(-x, y)
  expectEqual(-y, x)

  expectEqual(x + 0, x)
  expectEqual(y + 0, y)
  expectEqual(x - 0, x)
  expectEqual(y - 0, y)

  expectEqual(x - x, 0)
  expectEqual(y - y, 0)
}

BigIntTests.test("Max arithmetic") {
  let x = BigInt(repeatElement(UInt.max, count: 50))
  let y = BigInt(repeatElement(UInt.max, count: 35))
  let (q, r) = x.quotientAndRemainder(dividingBy: y)

  expectEqual(q * y + r, x)
  expectEqual(q * y, x - r)
}

BigIntTests.test("Zero arithmetic") {
  let zero: BigInt = 0
  expectTrue(zero.isZero)
  expectFalse(zero.isNegative)

  let x: BigInt = 1
  expectTrue((x - x).isZero)
  expectFalse((x - x).isNegative)

  let y: BigInt = -1
  expectTrue(y.isNegative)
  expectTrue((y - y).isZero)
  expectFalse((y - y).isNegative)

  expectEqual(x * zero, zero)
  expectCrashLater()
  _ = x / zero
}

BigIntTests.test("Conformances") {
  // Comparable
  let x = BigInt(Int.max)
  let y = x * x * x * x * x
  expectLT(y, y + 1)
  expectGT(y, y - 1)
  expectGT(y, 0)

  let z = -y
  expectLT(z, z + 1)
  expectGT(z, z - 1)
  expectLT(z, 0)

  expectEqual(-z, y)
  expectEqual(y + z, 0)

  // Hashable
  expectNotEqual(x.hashValue, y.hashValue)
  expectNotEqual(y.hashValue, z.hashValue)

  let set = Set([x, y, z])
  expectTrue(set.contains(x))
  expectTrue(set.contains(y))
  expectTrue(set.contains(z))
  expectFalse(set.contains(-x))
}

BigIntTests.test("BinaryInteger interop") {
  let x: BigInt = 100
  let xComp = UInt8(x)
  expectTrue(x == xComp)
  expectTrue(x < xComp + 1)
  expectFalse(xComp + 1 < x)

  let y: BigInt = -100
  let yComp = Int8(y)
  expectTrue(y == yComp)
  expectTrue(y < yComp + (1 as Int8))
  expectFalse(yComp + (1 as Int8) < y)
  // should be: expectTrue(y < yComp + 1), but:
  // warning: '+' is deprecated: Mixed-type addition is deprecated.
  // Please use explicit type conversion.

  let zComp = Int.min + 1
  let z = BigInt(zComp)
  expectTrue(z == zComp)
  expectTrue(zComp == z)
  expectFalse(zComp + 1 < z)
  expectTrue(z < zComp + 1)

  let w = BigInt(UInt.max)
  let wComp = UInt(extendingOrTruncating: w)
  expectTrue(w == wComp)
  expectTrue(wComp == w)
  expectTrue(wComp - (1 as UInt) < w)
  expectFalse(w < wComp - (1 as UInt))
  // should be:
  //  expectTrue(wComp - 1 < w)
  //  expectTrue(w > wComp - 1)
  // but crashes at runtime
}

BigIntTests.test("Huge") {
  let x = BigInt(randomBits: 1_000_000)
  expectGT(x, x - 1)
  let y = -x
  expectGT(y, y - 1)
}

BigIntTests.test("Numeric").forEach(in: [
  ("3GFWFN54YXNBS6K2ST8K9B89Q2AMRWCNYP4JAS5ZOPPZ1WU09MXXTIT27ZPVEG2Y",
   "9Y1QXS4XYYDSBMU4N3LW7R3R1WKK",
   "CIFJIVHV0K4MSX44QEX2US0MFFEAWJVQ8PJZ",
   "26HILZ7GZQN8MB4O17NSPO5XN1JI"),
  ("7PM82EHP7ZN3ZL7KOPB7B8KYDD1R7EEOYWB6M4SEION47EMS6SMBEA0FNR6U9VAM70HPY4WKXBM8DCF1QOR1LE38NJAVOPOZEBLIU1M05",
   "-202WEEIRRLRA9FULGA15RYROVW69ZPDHW0FMYSURBNWB93RNMSLRMIFUPDLP5YOO307XUNEFLU49FV12MI22MLCVZ5JH",
   "-3UNIZHA6PAL30Y",
   "1Y13W1HYB0QV2Z5RDV9Z7QXEGPLZ6SAA2906T3UKA46E6M4S6O9RMUF5ETYBR2QT15FJZP87JE0W06FA17RYOCZ3AYM3"),
  ("-ICT39SS0ONER9Z7EAPVXS3BNZDD6WJA791CV5LT8I4POLF6QYXBQGUQG0LVGPVLT0L5Z53BX6WVHWLCI5J9CHCROCKH3B381CCLZ4XAALLMD",
   "6T1XIVCPIPXODRK8312KVMCDPBMC7J4K0RWB7PM2V4VMBMODQ8STMYSLIXFN9ORRXCTERWS5U4BLUNA4H6NG8O01IM510NJ5STE",
   "-2P2RVZ11QF",
   "-3YSI67CCOD8OI1HFF7VF5AWEQ34WK6B8AAFV95U7C04GBXN0R6W5GM5OGOO22HY0KADIUBXSY13435TW4VLHCKLM76VS51W5Z9J"),
  ("-326JY57SJVC",
   "-8H98AQ1OY7CGAOOSG",
   "0",
   "-326JY57SJVC"),
  ("-XIYY0P3X9JIDF20ZQG2CN5D2Q5CD9WFDDXRLFZRDKZ8V4TSLE2EHRA31XL3YOHPYLE0I0ZAV2V9RF8AGPCYPVWEIYWWWZ3HVDR64M08VZTBL85PR66Z2F0W5AIDPXIAVLS9VVNLNA6I0PKM87YW4T98P0K",
   "-BUBZEC4NTOSCO0XHCTETN4ROPSXIJBTEFYMZ7O4Q1REOZO2SFU62KM3L8D45Z2K4NN3EC4BSRNEE",
   "2TX1KWYGAW9LAXUYRXZQENY5P3DSVXJJXK4Y9DWGNZHOWCL5QD5PLLZCE6D0G7VBNP9YGFC0Z9XIPCB",
   "-3LNPZ9JK5PUXRZ2Y1EJ4E3QRMAMPKZNI90ZFOBQJM5GZUJ84VMF8EILRGCHZGXJX4AXZF0Z00YA"),
  ("AZZBGH7AH3S7TVRHDJPJ2DR81H4FY5VJW2JH7O4U7CH0GG2DSDDOSTD06S4UM0HP1HAQ68B2LKKWD73UU0FV5M0H0D0NSXUJI7C2HW3P51H1JM5BHGXK98NNNSHMUB0674VKJ57GVVGY4",
   "1LYN8LRN3PY24V0YNHGCW47WUWPLKAE4685LP0J74NZYAIMIBZTAF71",
   "6TXVE5E9DXTPTHLEAG7HGFTT0B3XIXVM8IGVRONGSSH1UC0HUASRTZX8TVM2VOK9N9NATPWG09G7MDL6CE9LBKN",
   "WY37RSPBTEPQUA23AXB3B5AJRIUL76N3LXLP3KQWKFFSR7PR4E1JWH"),
  ("1000000000000000000000000000000000000000000000",
   "1000000000000000000000000000000000000",
   "1000000000",
   "0"),
  ])
{ strings in
  let x = BigInt(strings.0, radix: 36)!
  let y = BigInt(strings.1, radix: 36)!
  let q = BigInt(strings.2, radix: 36)!
  let r = BigInt(strings.3, radix: 36)!

  let (testQ, testR) = x.quotientAndRemainder(dividingBy: y)
  expectEqual(testQ, q)
  expectEqual(testR, r)
  expectEqual(x, y * q + r)
}

BigIntTests.test("Strings") {
  let x = BigInt("-3UNIZHA6PAL30Y", radix: 36)!
  expectEqual(x.binaryString, "-1000111001110110011101001110000001011001110110011011110011000010010010")
  expectEqual(x.decimalString, "-656993338084259999890")
  expectEqual(x.hexString, "-239D9D3816766F3092")
  expectEqual(x.compactString, "-3UNIZHA6PAL30Y")

  expectTrue(BigInt("12345") == 12345)
  expectTrue(BigInt("-12345") == -12345)

  expectTrue(BigInt("-3UNIZHA6PAL30Y", radix: 10) == nil)
  expectTrue(BigInt("---") == nil)
  expectTrue(BigInt(" 123") == nil)
}

BigIntTests.test("Randomized arithmetic").forEach(in: Array(1...10)) { _ in
  // Test x == (x / y) * x + (x % y)
  let (x, y) = (
    BigInt(randomBits: randomBitLength()),
    BigInt(randomBits: randomBitLength()))
  if !y.isZero {
    let (q, r) = x.quotientAndRemainder(dividingBy: y)
    expectEqual(q * y + r, x)
    expectEqual(q * y, x - r)
  }

  // Test (x0 + y0)(x1 + y1) == x0x1 + x0y1 + y0x1 + y0y1
  let (x0, y0, x1, y1) = (
    BigInt(randomBits: randomBitLength()),
    BigInt(randomBits: randomBitLength()),
    BigInt(randomBits: randomBitLength()),
    BigInt(randomBits: randomBitLength()))
  let r1 = (x0 + y0) * (x1 + y1)
  let r2 = ((x0 * x1) + (x0 * y1), (y0 * x1) + (y0 * y1))
  expectEqual(r1, r2.0 + r2.1)
}

var BigInt8Tests = TestSuite("BigInt<UInt8>")

BigInt8Tests.test("BinaryInteger interop") {
  let x: BigInt8 = 100
  let xComp = UInt8(x)
  expectTrue(x == xComp)
  expectTrue(x < xComp + 1)
  expectFalse(xComp + 1 < x)

  let y: BigInt8 = -100
  let yComp = Int8(y)
  expectTrue(y == yComp)
  expectTrue(y < yComp + (1 as Int8))
  expectFalse(yComp + (1 as Int8) < y)

  let zComp = Int.min + 1
  let z = BigInt8(zComp)
  expectTrue(z == zComp)
  expectTrue(zComp == z)
  expectFalse(zComp + 1 < z)
  expectTrue(z < zComp + 1)

  let w = BigInt8(UInt.max)
  let wComp = UInt(extendingOrTruncating: w)
  expectTrue(w == wComp)
  expectTrue(wComp == w)
  expectTrue(wComp - (1 as UInt) < w)
  expectFalse(w < wComp - (1 as UInt))
}

BigInt8Tests.test("Randomized arithmetic").forEach(in: Array(1...10)) { _ in
  // Test x == (x / y) * x + (x % y)
  let (x, y) = (
    BigInt8(randomBits: randomBitLength()),
    BigInt8(randomBits: randomBitLength()))
  if !y.isZero {
    let (q, r) = x.quotientAndRemainder(dividingBy: y)
    expectEqual(q * y + r, x)
    expectEqual(q * y, x - r)
  }

  // Test (x0 + y0)(x1 + y1) == x0x1 + x0y1 + y0x1 + y0y1
  let (x0, y0, x1, y1) = (
    BigInt8(randomBits: randomBitLength()),
    BigInt8(randomBits: randomBitLength()),
    BigInt8(randomBits: randomBitLength()),
    BigInt8(randomBits: randomBitLength()))
  let r1 = (x0 + y0) * (x1 + y1)
  let r2 = ((x0 * x1) + (x0 * y1), (y0 * x1) + (y0 * y1))
  expectEqual(r1, r2.0 + r2.1)
}

BigInt8Tests.test("Bitshift") {
  expectEqual(BigInt8(255) << 1, 510)
  expectTrue(BigInt(UInt32.max) << 16 == UInt(UInt32.max) << 16)
  var (x, y) = (1 as BigInt, 1 as UInt)
  for i in 0..<64 {   // don't test 64-bit shift, UInt64 << 64 == 0
    expectTrue(x << i == y << i)
  }

  (x, y) = (BigInt(UInt.max), UInt.max)
  for i in 0...64 {   // test 64-bit shift, should both be zero
    expectTrue(x >> i == y >> i)
  }

  x = BigInt(-1)
  let z = -1 as Int
  for i in 0..<64 {
    expectTrue(x << i == z << i)
  }
}

BigInt8Tests.test("Bitwise").forEach(in: [
  BigInt8(Int.max - 2),
  BigInt8(255),
  BigInt8(256),
  BigInt8(UInt32.max),
  ])
{ value in
  for x in [value, -value] {
    expectTrue(x | 0 == x)
    expectTrue(x & 0 == 0)
    expectTrue(x & ~0 == x)
    expectTrue(x ^ 0 == x)
    expectTrue(x ^ ~0 == ~x)
    expectTrue(x == BigInt8(Int(extendingOrTruncating: x)))
    expectTrue(~x == BigInt8(~Int(extendingOrTruncating: x)))
  }
}

var BigIntBitTests = TestSuite("BigInt<Bit>")

BigIntBitTests.test("Randomized arithmetic").forEach(in: Array(1...10)) { _ in
  // Test x == (x / y) * x + (x % y)
  let (x, y) = (
    BigIntBit(randomBits: randomBitLength() % 100),
    BigIntBit(randomBits: randomBitLength() % 100))
  if !y.isZero {
    let (q, r) = x.quotientAndRemainder(dividingBy: y)
    expectEqual(q * y + r, x)
    expectEqual(q * y, x - r)
  }

  // Test (x0 + y0)(x1 + y1) == x0x1 + x0y1 + y0x1 + y0y1
  let (x0, y0, x1, y1) = (
    BigIntBit(randomBits: randomBitLength() % 100),
    BigIntBit(randomBits: randomBitLength() % 100),
    BigIntBit(randomBits: randomBitLength() % 100),
    BigIntBit(randomBits: randomBitLength() % 100))
  let r1 = (x0 + y0) * (x1 + y1)
  let r2 = ((x0 * x1) + (x0 * y1), (y0 * x1) + (y0 * y1))
  expectEqual(r1, r2.0 + r2.1)
}

BigIntBitTests.test("Conformances") {
  // Comparable
  let x = BigIntBit(Int.max)
  let y = x * x * x * x * x
  expectLT(y, y + 1)
  expectGT(y, y - 1)
  expectGT(y, 0)

  let z = -y
  expectLT(z, z + 1)
  expectGT(z, z - 1)
  expectLT(z, 0)

  expectEqual(-z, y)
  expectEqual(y + z, 0)

  // Hashable
  expectNotEqual(x.hashValue, y.hashValue)
  expectNotEqual(y.hashValue, z.hashValue)

  let set = Set([x, y, z])
  expectTrue(set.contains(x))
  expectTrue(set.contains(y))
  expectTrue(set.contains(z))
  expectFalse(set.contains(-x))
}

BigIntBitTests.test("words") {
  expectEqualSequence([1], (1 as BigIntBit).words)
  expectEqualSequence([UInt.max, 0], BigIntBit(UInt.max).words)
  expectEqualSequence([UInt.max >> 1], BigIntBit(UInt.max >> 1).words)
  expectEqualSequence([0, 1], (BigIntBit(UInt.max) + 1).words)
  expectEqualSequence([UInt.max], (-1 as BigIntBit).words)
}

runAllTests()