random.nim: added shuffle proc; fixes 'mod' bias

1 files changed, 12 insertions, 2 deletions

diff --git a/lib/pure/random.nim b/lib/pure/random.nim
index 67f085dac..9484557a9 100644
--- a/lib/pure/random.nim
+++ b/lib/pure/random.nim
@@ -1,7 +1,7 @@
 #
 #
 #            Nim's Runtime Library
-#        (c) Copyright 2016 Andreas Rumpf
+#        (c) Copyright 2017 Andreas Rumpf
 #
 #    See the file "copying.txt", included in this
 #    distribution, for details about the copyright.
@@ -22,6 +22,8 @@ when defined(JS):
 else:
   type ui = uint64
 
+const randMax = 18_446_744_073_709_551_615u64
+
 type
   RandomGenState = object
     a0, a1: ui
@@ -72,7 +74,10 @@ proc random*(max: int): int {.benign.} =
   ## random number is always the same, unless `randomize` is called
   ## which initializes the random number generator with a "random"
   ## number, i.e. a tickcount.
-  result = int(next(state) mod uint64(max))
+  while true:
+    let x = next(state)
+    if x < randMax - (randMax mod uint64(max)):
+      return int(x mod uint64(max))
 
 proc random*(max: float): float {.benign.} =
   ## Returns a random number in the range 0..<max. The sequence of
@@ -99,6 +104,11 @@ proc randomize*(seed: int) {.benign.} =
   state.a0 = ui(seed shr 16)
   state.a1 = ui(seed and 0xffff)
 
+proc shuffle*[T](x: var seq[T]) =
+  for i in countdown(x.high, 0):
+    let j = random(i + 1)
+    swap(x[i], x[j])
+
 when not defined(nimscript):
   import times