00001 /******************************************************************************* 00002 00003 @file Random.d 00004 00005 Copyright (c) 2004 Kris Bell 00006 00007 This software is provided 'as-is', without any express or implied 00008 warranty. In no event will the authors be held liable for damages 00009 of any kind arising from the use of this software. 00010 00011 Permission is hereby granted to anyone to use this software for any 00012 purpose, including commercial applications, and to alter it and/or 00013 redistribute it freely, subject to the following restrictions: 00014 00015 1. The origin of this software must not be misrepresented; you must 00016 not claim that you wrote the original software. If you use this 00017 software in a product, an acknowledgment within documentation of 00018 said product would be appreciated but is not required. 00019 00020 2. Altered source versions must be plainly marked as such, and must 00021 not be misrepresented as being the original software. 00022 00023 3. This notice may not be removed or altered from any distribution 00024 of the source. 00025 00026 4. Derivative works are permitted, but they must carry this notice 00027 in full and credit the original source. 00028 00029 00030 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 00031 00032 00033 @version Initial version, April 2004 00034 @author various 00035 00036 00037 *******************************************************************************/ 00038 00039 module mango.utils.Random; 00040 00041 00042 /****************************************************************************** 00043 00044 KISS (via George Marsaglia & Paul Hsieh) 00045 00046 the idea is to use simple, fast, individually promising 00047 generators to get a composite that will be fast, easy to code 00048 have a very long period and pass all the tests put to it. 00049 The three components of KISS are 00050 00051 x(n)=a*x(n-1)+1 mod 2^32 00052 y(n)=y(n-1)(I+L^13)(I+R^17)(I+L^5), 00053 z(n)=2*z(n-1)+z(n-2) +carry mod 2^32 00054 00055 The y's are a shift register sequence on 32bit binary vectors 00056 period 2^32-1; The z's are a simple multiply-with-carry sequence 00057 with period 2^63+2^32-1. 00058 00059 The period of KISS is thus 2^32*(2^32-1)*(2^63+2^32-1) > 2^127 00060 00061 ******************************************************************************/ 00062 00063 version (Win32) 00064 { 00065 extern(Windows) int QueryPerformanceCounter (ulong *); 00066 } 00067 00068 version (Posix) 00069 { 00070 version (linux) 00071 private import std.c.linux.linux; 00072 00073 version (darwin) 00074 private import std.c.darwin.darwin; 00075 } 00076 00077 class Random 00078 { 00079 private static uint kiss_x = 1; 00080 private static uint kiss_y = 2; 00081 private static uint kiss_z = 4; 00082 private static uint kiss_w = 8; 00083 private static uint kiss_carry = 0; 00084 private static uint kiss_k; 00085 private static uint kiss_m; 00086 00087 /********************************************************************** 00088 00089 **********************************************************************/ 00090 00091 static this () 00092 { 00093 ulong s; 00094 00095 version (Posix) 00096 { 00097 timeval tv; 00098 00099 gettimeofday (&tv, null); 00100 s = tv.tv_usec; 00101 } 00102 version (Win32) 00103 QueryPerformanceCounter (&s); 00104 00105 seed (s); 00106 } 00107 00108 /********************************************************************** 00109 00110 **********************************************************************/ 00111 00112 static final void seed (uint seed) 00113 { 00114 kiss_x = seed | 1; 00115 kiss_y = seed | 2; 00116 kiss_z = seed | 4; 00117 kiss_w = seed | 8; 00118 kiss_carry = 0; 00119 } 00120 00121 /********************************************************************** 00122 00123 **********************************************************************/ 00124 00125 static final uint get (uint limit) 00126 { 00127 return get() % limit; 00128 } 00129 00130 /********************************************************************** 00131 00132 **********************************************************************/ 00133 00134 static final uint get () 00135 { 00136 kiss_x = kiss_x * 69069 + 1; 00137 kiss_y ^= kiss_y << 13; 00138 kiss_y ^= kiss_y >> 17; 00139 kiss_y ^= kiss_y << 5; 00140 kiss_k = (kiss_z >> 2) + (kiss_w >> 3) + (kiss_carry >> 2); 00141 kiss_m = kiss_w + kiss_w + kiss_z + kiss_carry; 00142 kiss_z = kiss_w; 00143 kiss_w = kiss_m; 00144 kiss_carry = kiss_k >> 30; 00145 return kiss_x + kiss_y + kiss_w; 00146 } 00147 } 00148