Вихрь Мерсенна (Mersenne twister) — генератор псевдослучайных чисел
Запись от drnet_ua размещена 13.10.2010 в 20:24
навеяно этой темой
пример в первом посте я не заметил, вернее глянул мельком, показалось что на С, и както "грязненько", как многое сишное
полез в википедию, почитал.
20-25 минут был первый вариант, потом в течении дня с перерывами на работу вылизывал исходник.
как там в школе было: Проделав данную работу, я научился работать со статическими методами(т.е. работа с классом без явного создания инстанса), писать комментарии для автогенерации хелпа, ну и освежил в памяти bitwise операции.
по скорости работы - генерация целого в пределах 0-0xFFFFFFFF:
пример - 100%
статический вызов - 85%
через переменную - 67%
по скорости работы генерация "real" в пределах 0-1:
пример - 100%
статический вызов - 48%
через переменную - 34%
график распределения прилагается.
покритикуйте исходник.
package { /** * ... * @author drnet_ua * * Usage example: * * trace( MersenneTwister.IntRange(10, 50) ); * * or * * var mt:MersenneTwister = new MersenneTwister(); * trace( mt.mt.RandomSign()); * */ public class MersenneTwister { // constants private const MaxNumber:Number = Number.MAX_VALUE; private const MaxUint:uint = 0xFFFFFFFF; private const HalfMaxUint:uint = 0x7FFFFFFF; private const bit32nd:uint = 0x80000000; private const last31bits:uint = 0x7FFFFFFF; private const MagicNumber:uint = 0x6C078965; // coefficients for MT19937 private const n:uint = 624; private const m:uint = 397; private const r:uint = 31 private const a:uint = 0x9908B0DF; private const u:uint = 11; private const s:uint = 7; private const b:uint = 0x9D2C568016 private const t:uint = 15; private const c:uint = 0xEFC6000016; private const l:uint = 18; // variables private var MT:Array; private var index:uint = 0; private static var instance:MersenneTwister; // Static calls public static function getInstance():MersenneTwister { if(instance == null) { instance = new MersenneTwister(); } return instance; } /** * Generates random sign +1 or -1 * @return **/ public static function Sign():Number { return getInstance().RandomSign(); } /** * Generates random floating-point Number in [0..1) * @return **/ public static function Random():Number { return getInstance()._Random(); } /** * Generates random floating-point Number in [0..MAX_NUMBER) * @return **/ public static function Real():Number { return getInstance().randomReal(); } /** * Generates random floating-point Number in [Min..Max] * @return **/ public static function RealRange(Min:Number,Max:Number):Number { return getInstance().randomRealRange(Min,Max); } /** * Generates random integer Number in [0..MAX_NUMBER) * @return **/ public static function Int():Number { return getInstance().randomInt(); } /** * Generates random integer Number in [Min..Max] * @return **/ public static function IntRange(Min:Number, Max:Number):Number { return getInstance().randomIntRange(Min,Max); } /** * Generates random uint in [0..0xFFFFFFFF] * @return **/ public static function Uint():uint { return getInstance().ExtractNumber(); } /** * Setting new, user-defined starting seed, re-initializes Twister * @return **/ public static function Seed(NewSeed:uint):void { getInstance().SetSeed(NewSeed); } /** * Setting new, random starting seed, re-initializes Twister * @return **/ public static function Randomize():void { getInstance().RandomSeed(); } /** * Constructor method, starts with random seed * @return **/ public function MersenneTwister() { MT = new Array(n) SetSeed(Math.random() * MaxUint); } // Public calls /** * Generates random sign +1 or -1 * @return **/ public function RandomSign():Number { if (ExtractNumber() > HalfMaxUint) { return 1 } else { return -1}; } /** * Generates random floating-point Number in [0..1) * @return **/ public function _Random():Number { return ExtractNumber() / MaxUint; } /** * Generates random floating-point Number in [0..MAX_NUMBER) * @return **/ public function randomReal():Number { return _Random() * MaxNumber; } /** * Generates random floating-point Number in [Min..Max] * @return **/ public function randomRealRange(Min:Number, Max:Number):Number { if (Min == Max) { return Min; } if (Min > Max) { var Swap:Number = Min; Min = Max; Max = Swap; } return Min + _Random() * (Max - Min); } /** * Setting new, random starting seed, re-initializes Twister * @return **/ public function RandomSeed():void { SetSeed(Math.round(Math.random() * MaxUint)); } /** * Setting new, user-defined starting seed, re-initializes Twister * @return **/ public function SetSeed(seed:uint):void { index = 0; MT[0] = seed; for (var i:uint = 1; i < 624; i++) { MT[i] = (MagicNumber * (MT[i-1] ^ (MT[i-1] >> 30)) + i); } } /** * Generates random integer Number in [0..MAX_NUMBER) * @return **/ public function randomInt():Number { return Math.round(randomReal()); } public function randomIntRange(Min:Number, Max:Number):Number { return Math.round(randomRealRange(Min, Max)); } // twister routines private function GenerateNumbers():void { var y:uint; for (var i:uint = 0 ; i < n; i++) { y = (MT[i] & bit32nd) + (MT[(i + 1) % n] & last31bits); MT[i] = MT[(i + m) % n] ^ (y >> 1); if ((y % 2) == 1) { MT[i] ^= a; } } } private function ExtractNumber():uint { if (index == 0) { GenerateNumbers() } var y:uint = MT[index]; y ^= (y >> u); y ^= (y << s) & b; y ^= (y << t) & c; y ^= (y << l); index = (index + 1) % n; return y; } } }
Всего комментариев 53
Комментарии
Последние записи от drnet_ua
- Singleton и с чем его едят. (20.12.2010)
- Вихрь Мерсенна (Mersenne twister) — генератор псевдослучайных чисел (13.10.2010)