rand.nim

import unsigned, math

type
  Random* = generic x
    next(var x) is uint64

proc next*[T](self: var T, n: int): int =
  ## Gets a random number in [0, n). This wastes entropy, so it should
  ## be used with caution in cases where randomness can be exhausted
  assert n > 0
  # Roughly based on http://stackoverflow.com/a/17554531/2299084
  
  if (n and (n-1)) == 0: # Will return true if n is a power of 2
    # Mask is calculated as n-1. We know n is a bitstring where a single bit is
    # set, so
    #   0010_0000
    # - 0000_0001
    # = 0001_1111
    return (self.next() and (n - 1).uint64).int

  let
    limit = 20000'u64
 
  while true:
    let res = self.next()
    if res < limit:
      result = int(res mod n.uint64)
      assert result < n
      assert result >= 0
      break
  
import unittest, xorshift
var state = seed([579247, 34337, 67546, 567546723, 2390230])
for i in 0 .. 10000:
  discard state.next()
var buckets: array[0..999, int]
for i in 1..200000000:
  inc buckets[state.next(1000)]


var
  chiSquare = 0.0
  mean = 200_000
  stdDev = 0.0
for i, elem in buckets:
  let part = ((elem-mean)*(elem-mean))/mean
  chiSquare += part
  echo i, ". ", elem
  stdDev = stdDev + ((elem-mean)*(elem-mean)).float

stdDev /= 1000
stdDev = sqrt(stdDev)
echo stdDev.int
assert chiSquare < 1143.9169
echo chiSquare.int