Равномерный рандом

Как-то было дело — я столкнулся с тем, что стандартный Math.random() меня не устраивает. Дело в том, что числовые значения, получаемые при его использовании распределены по нормальному закону.
По-русски говоря, это значит, что если, например, создать генератор случайных целых чисел от 0 до 10, используя лишь штатный random(), то некоторые из получаемых чисел будут выпадать гораздо чаще остальных. Конечно, если необходимо сгенерировать лишь несколько случайных значений, это проканает, но если игра основана на случайности, то повышенная повторяемость некоторых «избранных» чисел начинает бросаться в глаза (((

Порыв интернет и перекопав старые политеховские лекции, я на скорую руку соорудил для себя класс, позволяющий получить случайные числа, распределенные по равномерному закону.
И опять же, если сказать по-русски, то частоты выпадения различных чисел, генерируемых этим классом, стремятся быть одинаковыми ))))

Для тех, кто еще не успел изобрести подобный велосипед и/или не собирается этого делать, я выкладываю код своего класса:
public class RND {
        private var val:uint;
        static var maxValue:uint = 2147483647;
        private var k:uint = 1220703125;
        private var b:uint = 7;
        private var m:uint;
        
        public function RND(modul:uint = 2147483647) {
                this.m = modul;
                var t:Date = new Date();
                var s:String = t.time.toString();
                s = s.substr(s.length-3,3);
                this.val = uint(s);
        }
        
        public function get Value() {
                val = ((k * val + b) % maxValue);
                return val % m;
        }
}
Кстати есть особенность — генератор случайных чисел, реализованный в этом классе, будет выдавать случайные целые, неповторяющиеся числа от 0 до modul-1 с периодом, равным 7 миллионам. Думаю, для решения большинства задач этого достаточно.

При создании экземпляра этого класса получаем очередной генератор случайных чисел. Конструктору передается в качестве аргумента верхний предел случайных значений.

Напимер:
private var rnd:RND = new RND(100);
Данный экземпляр будет генерировать целые случайные числа от 0 до 99.
Кстати, как видно из кода класса, если аргумент в конструктор не передавать, то максимальное число, которое может сгенерировать это творение рук человеческих (и уж поверьте — рано или поздно оно это сделает) по умолчанию равно
2147483647 - 1 = 2147483646
.
Ну а получить очередное случайное число можно простым обращением к свойству Value:
rnd.Value
ВАЖНО! при каждом обращении к свойству Value получаем новое случайное число!!!

Я не претендую на оригинальность или совершенство идеи — может кто-то предложит лучший вариант (кстати буду рад — пишите, «есличо»), но я очень доволен результатами работы этого класса. )

Вот, вроде бы и все…
На последок скажу, что если внезапно у кого возникнет (возможно, по пьяни) непреодолимое желание поглубже вгрызться в физический смысл и механизм работы сварганенного мною класса, то можете поискать информацию о линейном конгруэнтном методе и линейных конгруэнтных последовательностях — ибо я при написании сего класса опирался именно на них

ПС: Буду искренне рад, если моя писанина хоть кому-нибудь поможет
  • +10

Комментарии (38)

+1
молоток! спасибо! Хотя… я наверное сделал бы иначе и скорей всего совсем не правильно))
0
но если игра основана на случайности
В таком случае начальные коэффициенты для генерации должны быть более менее недетерминированы, например, отталкиваться от системного времени или от периода изменения координат мышки и т.д. А так при каждом запуске игры последовательность будет повторятся, что в «игре основанной на случайностях» — фэил. В других случаях адобовский рандом имеет смысл переписывать только из-за его тормознутости, есть неплохая реализация на ксорах.
0
Может я тебя неправильно понял, но если вглядеться в конструктор, то там (о, чудо!) идет отталкивание именно от времени. Конечно, там берутся всего три последние цифры… но при желании легким движением руки можно и доработать — скажем, брать шесть последних цифр. Куда уж недетерменированнее-та?
0
вот что я имею в виду:

    var t:Date = new Date();
    var s:String = t.time.toString();
    s = s.substr(s.length-3,3);
    this.val = uint(s);

Таким образом происходит инициализация генератора

ПС: А ссылочку про ксоры не могбы кинуть?
0
А, сорри, просмотрел. Бегло увидел, что k и b константы, а конструктор и не посмотрел, тогда с рандомностью все ОК.

XOR
0
Пасиб за ссылочку :):):)
0
А это:
var t:Date = new Date();

Разве не системное время?
0
Опоздал, извиняйте :)
0
В своё время взял код рендома из HGE, портировал на AS3, haXe и ObjC. Отличный управляемый рендом. На нём основана игра Helirocket.
0
опубликовать не желаешь? мне бы было интересно :)
+1
0
Пасиб :):):)
0
Спасибо за хороший класс.
Но так как вы решились публично выложить код, есть пару вопросов:
Почему название класса заглавными? Аббревиатура?
Почему имя геттера с большой, а переменных класса с маленькой?
Почему для статической переменной не указана область видимости? Да, по-умолчанию сейчас она internal.

Все что выше я написал — просто подсказки :)
0
Ну да! Грешен! Ну не владею я культурой оформления кода *убился ап стену со стыда* Впредь буду стараться правильнее оформлять код *торжественно клянется* :)
0
ну а если серьезно, то спасибо — я действительно чет об этом не подумал, хотя сам люблю, когда в коде все прописано :) как с компа вылезу (сейчас с телефона) — обязательно исправлю
+1
Если тебе выпали тузы два раза подряд, это не значит, что твои шансы получить тузы третий раз поменялись — основной принцип покера.

Вероятности не меняются, основываясь на предыдущих результатах.
0
Как раз значит, вероятность будет коррелировать, так как количество тузов и количество карт в колоде уменьшилось и их отношение изменилось.
0
их кто-то съест в следующий хенд? :)
0
При следующей раздаче шансы, конечно, не изменятся, хотя есть стратегии игры, которые опираются на результаты предыдущих раздач, значит там все-таки что-то коррелирует. Я имел ввиду что изменятся шансы, например при обмене, если есть на руках два туза, то шансы что придет еще один — меньше, чем если бы на руках вообще их не было.
0
Вероятность меняется. Даже можно это доказать.
Имеется колода карт(36 штук), какова вероятность что выпадет n количество тузов из трех карт.
В данной задачи, w — сочетание.

Случай с n = 1:
A = среди трех взятых карт — 1 туз.
N = C(3 и 36) = (36*35*34)/(1*2*3) = 7140 (перерасчеты делать не будем, т.к. количество карт взятых и карт в колоде остается неизменным)
M = C(1 и 4) * C(2 и 32) = 4/1 * (32*31)/(1*2) = 1984
P(A) = 1984 / 7120 ~ 0.28 (или 28%)

Случай с n = 2:
A = среди трех взятых карт — 2 туза.
M = C(2 и 4) * C(1 и 32) = (4*3)/(1*2) * 32/1 = 192
P(A) = 192/7140 ~ 0.03 (или 3%)

Случай с n = 3:
A = среди трех взятых карт — 3 туза.
M = C(3 и 4) * C(0 и 32) = (4*3*2)/(1*2*3) = 4
P(A) = 0.0005 (или 0.05%)

Вуаля!

А так по сути да, велосипед) Но плюсую.
0
Ребята, вы тут про что-то совсем не то ))

Я говорю про холдем или омаху, где каждый раз колода тусуется.

Естественно, если говорить про то, что у меня два туза на руках — то шанс тузу на доске выпасть весьма мал (поймать сет).
0
http://lab.polygonal.de/2007/04/21/a-good-pseudo-random-number-generator-prng/
Я вот тут брал.
  • ryzed
  • ryzed
0
и тебе пасиб :):):)
+1
Дело в том, что числовые значения, получаемые при его использовании распределены по нормальному закону.
Функция распределения Math.random()
+1
По равномерному:)
0
О_о офигеть!!!
я не смогу сейчас назвать источник — давно эт было, но я собственными глазами читал о НОРМАЛЬНОМ характере распределения Math.random()!!!
В любом случае результаты, выдаваемые штатным рандомом весьма гавеные и уж очень далеки от равномерного закона — проведи эксперимент и ты увидишь ;)
0
угумс, чтото действительно странно, я тоже считал функцию рандома именно нормальным распределением, потому как на практике начальные и конечные состояния всегда были в нулях, а средние значения в избытке. Мои скромные знания твимса вытягивали картинку с синусойдами)
Поэтому я с радостью заюзал самописный рендом как только предложили) Что собственно дало тот самый результат равномерного распределения =)
0
Кстати, психология человека это довольно прикольная штука. Мне тоже неоднократно казалось, что дефолтовый рандом какой-то неравномерный :), но я знаю всякие пробросы восприятия…
Например, если посадить человека писать произвольное действительное число, и параллельно сгенерить его компом — то сторонний человек может всегда легко выпасти, где человек генерил, а где комп (если конечно человек не сидел и не кидал монетку, только из ума генерил).
Выпасти просто: человек интуитвно не верит в частое появление длинных последовательностей одинаковых цифр, типа 1111, 22222, 33333333. И их избегает, думая что это не рандом получится.
0
уж очень далеки от равномерного закона
Ну в общем-то я и провёл эксперимент и график оказался прямой, а не горкой:) Так что чисто эмперически эксперимент показывает, что он всё таки ну очень близок к равномерному. Шатание видно в паре мест на 1 пиксель на картинке. При меньшем числе испытаний картинка представляет из себя более дрожащий график, и всё же дрожит он около горизонтальной прямой, а не около горки.

А где вы читали про нормалное распределение? Можете поделиться ссылкой?:)

Кстати даже исходя из бонального удобства — зачем создавать штатный рандом с нормальным распределением? Из равномерного нормальное (или какое-то еще, если требуется) делается на раз-два, а вот из нормального сделать равномерное — нужно еще постараться. Это было бы просто неразумно — делать штатный рандом со «сложной» функцией распределения. В большинстве случаев требуется равномерное распределение, и заставлять разработчиков изгаляться было бы неуважительно.

Вы уж простите, что вступаю в спор, но мне кажется вы написали не совсем верную информацию:)

Буду очень рад выслушать аргументацуию в пользу нормальности распределения штатного рандома:)
0
у меня было так:
нужно было склепать горстку фишек 6 окрасок, порядка сотни штук. окраска бралась рандомно из массива возможных окрасок. На протяжении двух дней, пока разбирался с другими задачами и параллельно тестил, заметил, что первая и последняя окраски в массиве встречаются на порядок меньше. Собственно бросалось в глаза то, что всё поле забито в основном двумя цветами из центра массива)
хотел решить проблему увеличением диапозона рандома и отсечением крайних значений, но вовремя появились эти темки)
За что очень благодарен авторам)
0
А можете привести кусок кода?
0
если мне, то у меня так:

private function randomCell():String {
        return _nameCells[RandUtils.getInt(0, levelColors)];
}

раньше вместо RandUtils.getInt(0, levelColors) стояло округление Math.random()*levelColors
мне кажется чтото в стандартном рандоме всётаки есть, раз несколько разных человек задавались этим вопросом =)
0
И у вас Math.ranom()*length не работал должным образом? Простите, я просто не могу в это всё поверить, после того, как тот же самый что и у вас Math.random() на ста миллионах итераций выдал мне чёткий прямой график:) Может быть сторонники нормального распределения как-то прокомментируют тогда результат на картинке? Почему распределение нормальное, а график от равномерного?
0
Вернул в функцию стандартный рандом, добавил пустой массив и туда сохранял каждое вхождение цвета, запустил десяток раз и получил чтото типа такого:


9       15      18      14      23      8
6       16      17      21      24      7
9       26      17      17      21      12
9       13      22      18      13      8
11      21      32      26      25      6
8       16      24      16      21      8
11      18      13      20      18      9
11      13      17      15      23      12
9       18      20      20      17      9
8       14      23      13      17      7
___________________________________________
9,1     17      20,3    18      20,2    8,6


Исследованиями и спорами может заняться кто-нить у кого есть на это время
меня же вполне устроил предложенный в соседнем топике класс, и я получив что требовалось, продолжил разработку дальше)
+1
Округление как раз и оставляет крайним значениям в два раза меньше шансов выпасть, чем некрайним. К ним округлятся числа, лежащие в интервале длинной 0.5*длину массива (только 0.5 с одной стороны), а к некрайним округлятся лежащие в интервале длиной 1.0*длину массива (по 0.5 с обеих сторон). Использовав округление вы просто поделили вероятность выпадения крайних на два. Умножьте в своей табличке крайние значения на два, и увидите, что даже при такой маленькой выборке числа расходятся только чуть-чуть.
0
стояло округление
может в этом не состыковка, округлять не нужно, просто отсекать дробную часть (floor или просто приведением к int)
0
Однако)
а мне из за небольшого количества вариантов виделся метод распределения, а не обычный косяк в округлении =)
0
Кстати даже исходя из бонального удобства — зачем создавать штатный рандом с нормальным распределением? Из равномерного нормальное (или какое-то еще, если требуется) делается на раз-два, а вот из нормального сделать равномерное — нужно еще постараться. Это было бы просто неразумно — делать штатный рандом со «сложной» функцией распределения. В большинстве случаев требуется равномерное распределение, и заставлять разработчиков изгаляться было бы неуважительно.
Аргумент реально весомый…

Я, конечно, не проверял на ста миллионах итераций…
Расскажу, как дело было:
Писал я игру наподобие Wack-A-Mole про Муму и злого Герасима:
www.newgrounds.com/portal/view/541007
игра провалилась, но не в этом суть — в игре случайным образом в девяти местах всплывают собаки и бомбы (далее — с/б). так вот сначала я пользовался штатным рандомом. после того как процесс всплывания с/б был запрограммирован, я решил немного потестить будущее детище и заметил неприятную особенность — начиная где-то с итерации 60й..70й с/б начали всплывать в 90 процентах случаев в строгой последовательности мест (простите за каламбур) — то есть, например:
собака во второй позиции;
собака в пятой позиции;
собака в шестой позиции;
собака в восьмой позиции;
бомба в третьей позиции;
собака в первой позиции…
и все зацикливается.
конечно нормальным законом тут пахнет мало. про нормальный закон штатного рандома я нагуглил непосредственно после вскрытия вышеописанного неприятного факта. к сожалению, ссылку ща дать не могу — я не помню на какой сайт меня привел гугл

По большому счету мне не важно по какому закону штатный рандом выдает значения. Меня интересовали всего лишь первые пару сотен случайный значений в рамках создаваемой игры и он моих надежд не оправдал. А написанный мною рандом удовлетворил мои запросы.
Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.