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 00027 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 00028 00029 00030 @version Initial version, April 2004 00031 @author various 00032 00033 00034 *******************************************************************************/ 00035 00036 module mango.utils.Random; 00037 00038 00039 /****************************************************************************** 00040 00041 KISS (via George Marsaglia & Paul Hsieh) 00042 00043 the idea is to use simple, fast, individually promising 00044 generators to get a composite that will be fast, easy to code 00045 have a very long period and pass all the tests put to it. 00046 The three components of KISS are 00047 00048 x(n)=a*x(n-1)+1 mod 2^32 00049 y(n)=y(n-1)(I+L^13)(I+R^17)(I+L^5), 00050 z(n)=2*z(n-1)+z(n-2) +carry mod 2^32 00051 00052 The y's are a shift register sequence on 32bit binary vectors 00053 period 2^32-1; The z's are a simple multiply-with-carry sequence 00054 with period 2^63+2^32-1. 00055 00056 The period of KISS is thus 2^32*(2^32-1)*(2^63+2^32-1) > 2^127 00057 00058 ******************************************************************************/ 00059 00060 version (Win32) 00061 { 00062 extern(Windows) int QueryPerformanceCounter (ulong *); 00063 } 00064 00065 version (linux) 00066 { 00067 private import std.c.linux.linux; 00068 } 00069 00070 class Random 00071 { 00072 private static uint kiss_x = 1; 00073 private static uint kiss_y = 2; 00074 private static uint kiss_z = 4; 00075 private static uint kiss_w = 8; 00076 private static uint kiss_carry = 0; 00077 private static uint kiss_k; 00078 private static uint kiss_m; 00079 00080 /********************************************************************** 00081 00082 **********************************************************************/ 00083 00084 static this () 00085 { 00086 ulong s; 00087 00088 version (linux) 00089 { 00090 timeval tv; 00091 00092 gettimeofday (&tv, null); 00093 s = tv.tv_usec; 00094 } 00095 version (Win32) 00096 QueryPerformanceCounter (&s); 00097 00098 seed (s); 00099 } 00100 00101 /********************************************************************** 00102 00103 **********************************************************************/ 00104 00105 static final void seed (uint seed) 00106 { 00107 kiss_x = seed | 1; 00108 kiss_y = seed | 2; 00109 kiss_z = seed | 4; 00110 kiss_w = seed | 8; 00111 kiss_carry = 0; 00112 } 00113 00114 /********************************************************************** 00115 00116 **********************************************************************/ 00117 00118 static final uint get (uint limit) 00119 { 00120 return get() % limit; 00121 } 00122 00123 /********************************************************************** 00124 00125 **********************************************************************/ 00126 00127 static final uint get () 00128 { 00129 kiss_x = kiss_x * 69069 + 1; 00130 kiss_y ^= kiss_y << 13; 00131 kiss_y ^= kiss_y >> 17; 00132 kiss_y ^= kiss_y << 5; 00133 kiss_k = (kiss_z >> 2) + (kiss_w >> 3) + (kiss_carry >> 2); 00134 kiss_m = kiss_w + kiss_w + kiss_z + kiss_carry; 00135 kiss_z = kiss_w; 00136 kiss_w = kiss_m; 00137 kiss_carry = kiss_k >> 30; 00138 return kiss_x + kiss_y + kiss_w; 00139 } 00140 } 00141