[BigInt] Using tests from “Violet - Python VM written in Swift”

[LiarPrincess]

[BigInt] Using tests from “Violet - Python VM written in Swift”

[LiarPrincess]

[3.2.2023] EDIT to main issue:

• [BigInt tests] 💀 Init from float 754
• [BigInt tests] ✅🐰 Codable
• many changes in performance tests

[LiarPrincess]

Things to do in Helpers (but I'm not going to update 15 PRs, so we will do it later):

• add reserveCapacity in generate[Big]Ints - this does not matter in normal tests (count ~1000), but it matters in performance tests where we need to generate 100_000 values

• rename BigIntPrototype.compare -> BigIntPrototype.compareMagnitude

• rewrite BigIntPrototype.create - shifts 10x faster than multiplication:

  internal static func create<T: FixedWidthInteger>(
    isPositive: Bool,
    magnitude: [T]
  ) -> BigInt {
    assert(!T.isSigned)
    var result = BigInt()
  
    for (index, word) in magnitude.enumerated() {
      var bits = BigInt(word)
      bits <<= index * T.bitWidth
      result |= bits
    }
  
    if !isPositive {
      result.negate()
    }
  
    return result
  }

  If we use sign+magnitude with UInt as Word then there is another possible optimisation that avoids calculations altogether.

[LiarPrincess]

I wrote Violet XsProMax which is a Violet implementation with following changes:

• no small inlined integer (Smi) - magnitude is always stored on the heap
• no restrictions on the size - isNegative is stored in-line (and not on the heap like in Violet); count and capacity are on the heap because I don't want to stray too much from Violet.

Which gives us:

struct BigInt {
  struct Header {
    var count: UInt32
    var capacity: UInt32
  }

  var flags: UInt8
  var buffer: ManagedBufferPointer<Header, UInt>
}

I updated the performance PR with the results.

[mgriebling]

The issue below (from @LiarPrincess) appears fixed in my latest updates (see pull request #261)

// -9223372036854775808 = Int64.min, obviously '-Int64.min' overflows
let int: Int64 = -9223372036854775808
let big = BigInt(int)
XCTAssertEqual(-big, big * -1)

[mgriebling]

All remaining issues (at least the published ones) appear to have been fixed with the pull request #262.
There were some problems with division/modulo signs, initialization, corner-case fixes.