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 private import std.c.linux.linux; 00071 } 00072 00073 class Random 00074 { 00075 private static uint kiss_x = 1; 00076 private static uint kiss_y = 2; 00077 private static uint kiss_z = 4; 00078 private static uint kiss_w = 8; 00079 private static uint kiss_carry = 0; 00080 private static uint kiss_k; 00081 private static uint kiss_m; 00082 00083 /********************************************************************** 00084 00085 **********************************************************************/ 00086 00087 static this () 00088 { 00089 ulong s; 00090 00091 version (Posix) 00092 { 00093 timeval tv; 00094 00095 gettimeofday (&tv, null); 00096 s = tv.tv_usec; 00097 } 00098 version (Win32) 00099 QueryPerformanceCounter (&s); 00100 00101 seed (s); 00102 } 00103 00104 /********************************************************************** 00105 00106 **********************************************************************/ 00107 00108 static final void seed (uint seed) 00109 { 00110 kiss_x = seed | 1; 00111 kiss_y = seed | 2; 00112 kiss_z = seed | 4; 00113 kiss_w = seed | 8; 00114 kiss_carry = 0; 00115 } 00116 00117 /********************************************************************** 00118 00119 **********************************************************************/ 00120 00121 static final uint get (uint limit) 00122 { 00123 return get() % limit; 00124 } 00125 00126 /********************************************************************** 00127 00128 **********************************************************************/ 00129 00130 static final uint get () 00131 { 00132 kiss_x = kiss_x * 69069 + 1; 00133 kiss_y ^= kiss_y << 13; 00134 kiss_y ^= kiss_y >> 17; 00135 kiss_y ^= kiss_y << 5; 00136 kiss_k = (kiss_z >> 2) + (kiss_w >> 3) + (kiss_carry >> 2); 00137 kiss_m = kiss_w + kiss_w + kiss_z + kiss_carry; 00138 kiss_z = kiss_w; 00139 kiss_w = kiss_m; 00140 kiss_carry = kiss_k >> 30; 00141 return kiss_x + kiss_y + kiss_w; 00142 } 00143 } 00144