Генерация случ. величины с равномерным распределением

Тема в разделе "WASM.A&O", создана пользователем XshStasX, 14 июн 2010.

  1. XshStasX

    XshStasX New Member

    Публикаций:
    0
    Регистрация:
    9 авг 2008
    Сообщения:
    991
    Нужно на интервале от 1...20 равномерно генерировать случ. величину.
    Я так понимаю функция random(20) +1 , не даст равномерного распределения ?
    Или я ошибаюсь??
    Если да то как можно свести в более равномерном расп. чем у radom() ??

    Собственно задание на уровни курсака.
     
  2. AsmGuru62

    AsmGuru62 Member

    Публикаций:
    0
    Регистрация:
    12 сен 2002
    Сообщения:
    689
    Адрес:
    Toronto
    Теоретически функция random() даёт равномерное распределение. На практике, это зависит от того как эта функция "сделана" компилятором. Многие компиляторы используют LCG:

    http://en.wikipedia.org/wiki/Linear_congruential_generator

    Но LCG не проходит, так называемые Diehard Tests - тесты, по которым определяют качество генерации случайных чисел:

    http://en.wikipedia.org/wiki/Diehard_tests

    Есть более качественные генераторы, которые проходят все Diehard тесты:

    http://en.wikipedia.org/wiki/Mersenne_twister
    http://en.wikipedia.org/wiki/Xorshift
     
  3. paralvic

    paralvic Пархоменко Александр Викторович

    Публикаций:
    0
    Регистрация:
    20 ноя 2010
    Сообщения:
    294
    Адрес:
    Нижний Новгород
    Код (Text):
    1.     .686p
    2.     .MMX
    3.     .XMM
    4.     .model flat, stdcall
    5.     option casemap :none  ; регистрозависимы
    6. .code
    7. rdtsc    ;eax-результат
    8. ret
    Кто-нибудь проверял равномерное распределение?
     
  4. iamlamer

    iamlamer New Member

    Публикаций:
    0
    Регистрация:
    20 июн 2005
    Сообщения:
    273
    Адрес:
    Russia
    У программного RNG или rdtsc?
    У RNG - да.
    У rdtsc оно ни разу не равномерно ни теоретически, ни практически, и даже проверять не имеет смысла.
     
  5. Maratyszcza

    Maratyszcza New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2006
    Сообщения:
    32
    AsmGuru62
    XorShift не проходит Diehard тесты, об этом сказано в статье Marsaglia, где он и предложен (http://www.jstatsoft.org/v08/i14/paper)
    Более подробный анализ статистистических проблем XorShift'а есть в http://www.iro.umontreal.ca/~lecuyer/myftp/papers/xorshift.pdf
     
  6. AsmGuru62

    AsmGuru62 Member

    Публикаций:
    0
    Регистрация:
    12 сен 2002
    Сообщения:
    689
    Адрес:
    Toronto
    Maratyszcza
    Из первого документа следует, что не все генераторы такого типа проходят все тесты, но приведены и те, которые действительно проходят. Неплохой документ.