import random, math
import times, std/monotimes, strformat, strutils


proc formatNum(n: SomeNumber): string =
  let s = $(n.round)
  let t = s[0 .. s.len - 3]
  var count = 1
  for i in countdown(t.high, 0):
    result.insert($t[i], 0)
    if count mod 3 == 0 and i != 0:
      result.insert(",", 0)
    count += 1


proc formatRate(n: Natural, d: Duration): string =
  result = formatNum(1_000_000'f64 * n.float64 / d.inMicroseconds.float64)


const upperBound = uint64(uint32.high)


proc fastRand*[T: Natural](r: var Rand, x: T): T =
  # Nim ranges are usually inclusive, but this algorithm is exclusive
  let x = x.uint64 + 1
  let num = if x <= upperBound:
    ((r.next shr 32) * x.uint64) shr 32
  else:
    r.next mod x.uint64
  result = T(num)


proc fastRand*(r: var Rand; x, y: Natural): Natural =
  let lim = (y - x)
  result = fastRand(r, lim) + x


proc fastRand*[T](r: var Rand, slice: HSlice[T, T]): T =
  let n = fastRand(r, slice.a.Natural, slice.b.Natural)
  result = T(n)


proc testFastRand(num = 1_000_000_000): Duration =
  var r = initRand(rand(int64))
  let start = getMonoTime()
  for i in 1 .. num:
    discard r.fastRand(5)
  result = getMonoTime() - start
  # echo "fastrand execution rate: ",  1000 * num / dur.inMilliseconds.int, " generated per second."


proc testStdRand(num = 1_000_000_000): Duration =
  var r = initRand(rand(int64))
  let start = getMonoTime()
  for i in 1 .. num:
    discard r.rand(4)
  result = getMonoTime() - start
  # echo "std rand execution rate: ", 1000 * num / dur.inMilliseconds.int, " generated per second."


when isMainModule:
  randomize()
  var r = initRand(rand(int64))
  let runs = 100_000_000
  var totals: array[5..9, int]
  for i in 1 .. runs:
    let n = r.fastRand(5..9)
    totals[n] += 1
  echo totals

  # let fr = testFastRand(runs)
  # echo "fastrand execution rate: ", formatNum(1_000_000 * runs / fr.inMicroseconds.int)
  # let sr = testStdRand(runs)
  # echo "standard execution rate: ", formatNum(1_000_000 * runs / sr.inMicroseconds.int)