Отправлено DASM 06 июля 2005 г. 13:36

Нужен приличный генератор. Взял регистр сдвига 39 бит максимальной длины (отвод от 35 и 39-го бита)
Период 5.5e11 тактов. Для получения псевдослучайного числа 0..2^32 сдвигаю 32 раза, выход накапливаю. Это дает длину 1.7e10 чисел.
Все хорошо, решил проверить - генерю две точки X и Y и рисую её на плоскости. И вместо равномерного закрашивания вижу этот узор :-( Явно не свидетельствущий в пользу высокого качества последовательности :-( Что не так ?

• Вот очень хороший набор тестов на случайность — vmp   (06.07.2005 15:10 62.117.78.2, пустое, ссылка)
• Кажется дошло (+++): — argus98   (06.07.2005 15:09 81.22.205.230, 481 байт)
• Может диод 8=) ? — Ralex   (06.07.2005 13:48 213.183.101.54, пустое)
  • 2Г401Б. Желательно 2 канала. — vmp   (06.07.2005 14:07 62.117.78.2, пустое)
• Псевдослучайность этой последовательности (+) — SM   (06.07.2005 13:43 213.141.159.26, 449 байт)
  • накапливаю - 32 бита с выхода беру и побитно в свой аккумулятор кладу. АКФ красивая, без всплесков на выборке из пары тысяч, вблизи нуля ( нормирую СЧ -0.5 < x < 0.5) — DASM   (06.07.2005 13:59 217.118.78.1, пустое)
    • Так сделал бы LFSR сразу нужной тебе длины и брал бы прямо из него. А так (+) — SM   (06.07.2005 14:05 213.141.159.26, 280 байт)
      • ай, сам ступил. Регистр то у меня 39 бит, а я с него выдвигаю только 32. Оставшиеся 7 явно дадут вполне предсказуемое влияние на след выборку. Насчет LFSR нужной длины - не понял. Тогда соседние выборки будут отличатся одним сдвигом и старшим битом - тут уж точно зависимость будет жуткая — DASM   (06.07.2005 14:09 217.118.78.1, пустое)
        • да уж...я тоже не понял, ты так уверенно объяснял что делаешь что взять 32 из 39 это уже само собой разумеющееся...убаюкал:)) — ы   (06.07.2005 14:14 80.92.98.211, пустое)
        • Старший бит это очень много :) Соседние выборки могут отличаться ой-ой на сколько. — SM   (06.07.2005 14:13 213.141.159.26, пустое)
          • ты предлагаешь делать снимок регистра на каждом сдвиге ? Ну совсем неслучайно выйдет. На двумерном графике - две наклонные линии выходят, хотя автокореляцция прекрасно около нуля сидит — DASM   (06.07.2005 14:18 217.118.78.1, пустое)
            • Не упускай, что я говорил про поле Галуа, там выход регистра не один бит, а сразу сколько надо. — SM   (06.07.2005 14:19 213.141.159.26, пустое)
              • Вот сейчас беру снимок этого 39 битного регистра, но не после каждого сдвига, а после 39-ти. То есть как бы совсем новый. И все равно гадость такая. С Галуа еще разбираться ночь надо, ибо не в курсах — DASM   (06.07.2005 14:32 217.118.78.1, пустое, картинка)
                • Ну правильно - ты берешь не все значения, часть выкидываешь, отсюда и белые полосы. В идеале все должно почернеть. — SM   (06.07.2005 14:34 213.141.159.26, пустое)
                  • ну так если брать все значения то вообще две линии выходят — DASM   (06.07.2005 14:35 217.118.78.1, пустое)
                    • Так я наверное не понял... Ты как делаешь? Я бы так проверял (+) — SM   (06.07.2005 14:38 213.141.159.26, 70 байт)
                      • не, x = XMAX * (myrand() / RAND_MAX) . В double все ессно конвертировано — DASM   (06.07.2005 14:40 217.118.78.1, пустое)
                        • А Y? — SM   (06.07.2005 14:43 213.141.159.26, пустое)
                          • аналогично. По сути рисуется зависимость следущего от предыдущего — DASM   (06.07.2005 14:48 217.118.78.1, пустое)
                            • вот посмотрел сурцы rand из NET. Это какой класс алгоритмов ? (+) — DASM   (06.07.2005 14:58 217.118.78.1, 349 байт)
                              • Это линейный конгруэнтный генератор. — SM   (06.07.2005 15:07 213.141.159.26, пустое)
                                • а что у него с периодом ? Распределение вроде на первой взгляд ничего — DASM   (06.07.2005 15:10 217.118.78.1, пустое)
                                  • Максимум это (+) — SM   (06.07.2005 15:29 213.141.159.26, 196 байт)
                                    • ок, всем спасибо и тебе в частности — DASM   (06.07.2005 15:32 217.118.78.1, пустое)
                    • и вообще, для "хорошей" псевдослучайности последовательности не все ли равно, подряд брать или с прорежевинием ? — DASM   (06.07.2005 14:36 217.118.78.1, пустое)
                      • Конечно не все равно. При прореживании часть чисел просто никогда не появится на выходе прореживателя. Соотв. изменится распределение. — SM   (06.07.2005 14:43 213.141.159.26, пустое)
  • Причем АКФ при накапливании расползается и получаются узоры. — argus98   (06.07.2005 13:48 81.22.205.230, пустое)
    • Ну эт естессно, накопление это есть фильтрация... и спектр становится совсем другим. — SM   (06.07.2005 13:51 213.141.159.26, пустое)
      • да не накапливаю, просто беру выборку 32 бита, получаю случайное число, где все биты - случайны — DASM   (06.07.2005 14:00 217.118.78.1, пустое)
• чето не понятно говоришь точки а там линии какие то — ы   (06.07.2005 13:41 80.92.98.211, пустое)
  • да точки это, просто их 5 миллионов — DASM   (06.07.2005 13:44 217.118.78.1, пустое)
    • хм...а может ты с выводом чегото напутал..округления там всякие — ы   (06.07.2005 14:03 80.92.98.211, пустое)
      • и потом выводить надо после каждого такта а не через 32 раза? — ы   (06.07.2005 14:07 80.92.98.211, пустое)
• Возьми какой-нибудь алгоритм шифрования или хеш и пропускай через него твой алгоритм. Должно быть лучше. Но медленно. — БУБУ   (06.07.2005 13:39 195.131.84.202, пустое)
  • Только нахрена еще и алгоритм приплетать? ГОСТ 28147-89 в режиме гаммирования - прекрасный генератор случайных чисел. — vmp   (06.07.2005 13:51 62.117.78.2, 60 байт)
    • Для крутизны. :) — БУБУ   (06.07.2005 14:30 195.131.84.202, пустое)
• Видмо накапливать не надо... — argus98   (06.07.2005 13:39 81.22.205.230, пустое)