collatzing

main.swift

import Foundation

#if os(macOS)
import BigInt

typealias CollatzType = BigInt
#else
typealias CollatzType = Int
#endif

typealias InterestingN = (n: Int, found: Int)

struct InterestingCollatz: CustomStringConvertible {
  var n = 1
  var iteration = 1
  var peak = CollatzType(1)
  var seriesCount = 1

  var description: String {
    return "n: \(n); series length: \(seriesCount); peak: \(peak); found: \(iteration)"
  }
}

func createRanges(numRanges: Int, max: Int = .max) -> [ClosedRange<Int>] {
  let perRange = max / numRanges
  var ranges = [ClosedRange<Int>]()

  var startN = 0

  for _ in 0..<numRanges-1 {
    startN += 1

    // print("range \(i) starts at \(startN) and ends at \(startN+perRange)")
    ranges.append(startN...startN+perRange)

    startN += perRange
  }

  return ranges + [startN+1...max]
}

private let timer = DispatchSource.makeTimerSource()
private let start = Date().timeIntervalSince1970
private let ranges = createRanges(numRanges: 100_000)

private var lastInterestingThing = Date().timeIntervalSince1970
private var rng = MTRandom()
private var i = 1
private var longestSeries: InterestingCollatz!
private var largestN: InterestingCollatz!
private var largestPeak: InterestingCollatz!

private var shortestSeries: InterestingCollatz!
private var smallestPeak: InterestingCollatz!
private var smallestN: InterestingCollatz!

func stringFromTimeInterval(_ interval: TimeInterval) -> String {
  let interval = Int(interval)
  let seconds = interval % 60
  let minutes = (interval / 60) % 60
  let hours = (interval / 3600)

  return String(format: "%02d:%02d:%02d", hours, minutes, seconds)
}

func calculateInterestingThings(n: Int, seriesCount: Int, peak: CollatzType) {
  let interesting = InterestingCollatz(n: n, iteration: i, peak: peak, seriesCount: seriesCount)
  var wasInteresting = false

  if longestSeries == nil {
    // set first iteration
    longestSeries = interesting
    largestN = interesting
    largestPeak = interesting

    shortestSeries = interesting
    smallestPeak = interesting
    smallestN = interesting
    lastInterestingThing = Date().timeIntervalSince1970

    return
  }

  if n > largestN.n {
    print("\(i): New largest n")

    wasInteresting = true
    largestN = interesting
  } else if n < smallestN.n {
    print("\(i): New smallest n")

    wasInteresting = true
    smallestN = interesting
  }

  if seriesCount > longestSeries.seriesCount {
    print("\(i): New longest series")

    wasInteresting = true
    longestSeries = interesting
  } else if seriesCount < shortestSeries.seriesCount {
    print("\(i): New shortest series")

    wasInteresting = true
    shortestSeries = interesting
  }

  if peak > largestPeak.peak {
    print("\(i): New largest peak")

    wasInteresting = true
    largestPeak = interesting
  } else if peak < smallestPeak.peak {
    print("\(i): New smallest peak")

    wasInteresting = true
    smallestPeak = interesting
  }

  if wasInteresting {
    lastInterestingThing = Date().timeIntervalSince1970
  }
}

func randomCollatz() {
  let range = ranges.randomElement(using: &rng)!
  let n = Int.random(in: range)

  print("\(i): n = \(n) from range \(range)")

  let (series, peak) = collatz(CollatzType(n))

  print("\(i): series length: \(series.count); peak: \(peak)")
  print()

  calculateInterestingThings(n: n, seriesCount: series.count, peak: peak)
  print()

  print("\(i): Largest n = \(largestN!)")
  print("\(i): Longest Series = \(longestSeries!)")
  print("\(i): Largest Peak = \(largestPeak!)")
  print()
  print("\(i): Smallest n = \(smallestN!)")
  print("\(i): Shortest Series = \(shortestSeries!)")
  print("\(i): Smallest Peak = \(smallestPeak!)")
}

timer.setEventHandler {
  let timeRunningStr = stringFromTimeInterval(Date().timeIntervalSince1970 - start)
  let lastInterestingStr = stringFromTimeInterval(Date().timeIntervalSince1970 - lastInterestingThing)

  print("\u{001B}[2J\u{001B}[f", terminator: "")
  print("Starting \(i); Time running: \(timeRunningStr); Time since last interesting thing: \(lastInterestingStr)")

  let (_, t) = ClockTimer.time(randomCollatz)

  print("\(i): took \(t.duration)s")

  i += 1
}

timer.schedule(deadline: .now(), repeating: .milliseconds(15))
timer.activate()

dispatchMain()

MTRandom.swift

import Foundation

public struct MTRandom: RandomNumberGenerator {
  private var index = 312
  private var mt = [UInt64](repeating: 0, count: 312)

  public init(seed: UInt64 = .random(in: .min ... .max)) {
    mt[0] = seed

    for i in 1..<312 {
      mt[i] = 6364136223846793005 &* (mt[i - 1] ^ (mt[i - 1] >> 62)) + UInt64(i)
    }
  }

  public mutating func next() -> UInt64 {
    if index >= 312 {
      twist()
    }

    var y = mt[index]

    y ^= y >> 29 & 0x5555555555555555
    y ^= y << 17 & 0x71D67FFFEDA60000
    y ^= y << 37 & 0xFFF7EEE000000000
    y ^= y >> 1

    index += 1

    return y
  }

  private mutating func twist() {
    index = 0

    for i in 0..<312 {
      let y = (mt[i] & 0x7FFFFFFF) + (mt[(i + 1) % 312] & ~0x7FFFFFFF)

      mt[i] = mt[(i + 156) % 312] ^ y >> 1

      if y % 2 != 0 {
        mt[i] ^= 0xB5026F5AA96619E9
      }
    }
  }
}

ncollatz.swift

@inlinable
public func collatz<T: BinaryInteger>(_ n: T) -> (series: [T], peak: T) {
  var series = [n]
  var n = n
  var peak = n

  while n != 1 {
    if n & 1 == 0 {
      n /= 2
    } else {
      n = 3*n + 1
    }

    peak = max(n, peak)

    series.append(n)
  }

  return (series, peak)
}

time.swift

import Foundation

public struct TimeResult {
  public var clocks: Int

  @usableFromInline
  init(clocks: Int) {
    self.clocks = clocks
  }

  public var duration: Double {
    return Double(clocks) / Double(CLOCKS_PER_SEC)
  }
}

extension TimeResult: CustomStringConvertible {
  public var description: String {
    return "TimeResult(clocks: \(clocks), duration: \(duration)s)"
  }
}

public struct ClockTimer {
  @inlinable
  public static func time<T>(_ f: () throws -> T) rethrows -> (T, TimeResult) {
    let s = clock()
    let res = try f()
    let e = clock() - s

    return  (res, TimeResult(clocks: Int(e)))
  }
}