From 615038114f0c6502b2ce3c76bf71ce4fb6f1a8e5 Mon Sep 17 00:00:00 2001 From: Stefan O'Rear Date: Sun, 8 Nov 2009 09:45:24 -0800 Subject: Remove the bias from random2() Worst case for the old version was random2(65535) == 65534, which had a 1 in 2^30 chance of being true. --- crawl-ref/source/random.cc | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-) (limited to 'crawl-ref/source/random.cc') diff --git a/crawl-ref/source/random.cc b/crawl-ref/source/random.cc index fad30322de..758f5ea599 100644 --- a/crawl-ref/source/random.cc +++ b/crawl-ref/source/random.cc @@ -95,7 +95,16 @@ int random2(int max) if (max <= 1) return (0); - return (static_cast(random_int() / (0xFFFFFFFFUL / max + 1))); + unsigned long partn = 0xFFFFFFFFUL / max; + + while (true) + { + unsigned long bits = random_int(); + unsigned long val = bits / partn; + + if (val < (unsigned long)(max)) + return val; + } } bool coinflip(void) -- cgit v1.2.3-54-g00ecf