medfall

commit 894dfcb81e3296d0311cfa0f9f050b9b61c1527e
parent 35527c4411de80ed8c291062ad4e0fac6ce28dfb
Author: Michael Savage <mikejsavage@gmail.com>
Date:   Sat Jul 15 13:35:56 +0300

Much simpler rng_uniform, rename to rng_mod

Diffstat:
rng/rng_utils.h
 | 
40
++++------------------------------------
stats.cc
 | 
3
++-
2 files changed, 6 insertions(+), 37 deletions(-)
diff --git a/rng/rng_utils.h b/rng/rng_utils.h
@@ -23,49 +23,17 @@ bool rng_p( T * rng, double p ) {
 	return rng_next( rng ) < u32( p * U32_MAX );
 }
 
-/*
- * Copyright (c) 2008, Damien Miller <djm@openbsd.org>
- *
- * Permission to use, copy, modify, and distribute this software for any
- * purpose with or without fee is hereby granted, provided that the above
- * copyright notice and this permission notice appear in all copies.
- *
- * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
- * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
- * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
- * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
- * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
- * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
- * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
- */
-
 template< typename T >
-u32 rng_uniform( T * rng, u32 upper_bound ) {
-	if( upper_bound < 2 ) return 0;
-
-	/* 2**32 % x == (2**32 - x) % x */
-	u32 min = (~upper_bound + 1) % upper_bound;
-
-	/*
-	 * This could theoretically loop forever but each retry has
-	 * p > 0.5 (worst case, usually far better) of selecting a
-	 * number inside the range we need, so it should rarely need
-	 * to re-roll.
-	 */
-	u32 r;
-	for( ;; ) {
-		r = rng_next( rng );
-		if( r >= min ) break;
-	}
-
-	return r % upper_bound;
+u32 rng_mod( T * rng, u32 n ) {
+	u32 r = rng_next( rng );
+	return u32( ( u64( r ) * n ) >> u64( 32 ) );
 }
 
 // [min, max)
 template< typename T >
 u32 rng_uniform( T * rng, u32 lower_bound, u32 upper_bound ) {
 	ASSERT( lower_bound <= upper_bound );
-	return rng_uniform( rng, upper_bound - lower_bound ) + lower_bound;
+	return rng_mod( rng, upper_bound - lower_bound ) + lower_bound;
 }
 
 template< typename T >
diff --git a/stats.cc b/stats.cc
@@ -5,6 +5,7 @@
 #include "intrinsics.h"
 #include "stats.h"
 #include "ggformat.h"
+#include "rng/well512.h"
 
 void stats_init( Stats * stats ) {
 	*stats = { };
@@ -41,7 +42,7 @@ void stats_record( Stats * stats, double x ) {
 		double p = ( double ) STATS_NUM_QUART_SAMPLES / ( stats->num_records + 1.0 );
 
 		if( rng_p( &stats->rng, p ) ) {
-			u32 i = rng_uniform( &stats->rng, STATS_NUM_QUART_SAMPLES );
+			u32 i = rng_mod( &stats->rng, STATS_NUM_QUART_SAMPLES );
 			stats->samples[ i ] = x;
 		}
 	}