рандомный генератор не повторяющихся чисел

Тема в разделе "WASM.A&O", создана пользователем wsd, 27 окт 2010.

  1. wsd

    wsd New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2007
    Сообщения:
    2.824
    возможен ли сабж без проверки новосгенерированного числа в уже перед этим сгенирированных ?
    пусть генератор за один круг будет покрывать всего 60% допустимого диапазона, но обязательно уникальных
    и без проверок в базе уже сгенерированных?
     
  2. MSoft

    MSoft New Member

    Публикаций:
    0
    Регистрация:
    16 дек 2006
    Сообщения:
    2.854
    на васме уже поднималась эта тема. Поищи. Но чего-то похожего на решение я не помню. Хотя какие-то формулы там давались
     
  3. wsd

    wsd New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2007
    Сообщения:
    2.824
    MSoft
    что то не ишется, видать мы по разному темы называли

    чёрт с 60% , увеличу допустимый диапазон, пусть хоть 5% будет, но гарантированно
     
  4. gazlan

    gazlan Member

    Публикаций:
    0
    Регистрация:
    22 май 2005
    Сообщения:
    414
    Гарантию дает только страховый полис... А так
    Код (Text):
    1. for (ii = 0; ii < MAX_VALUE; ++ii)
    2. {
    3.    RndVal = Hash(ii);
    4. }
    Для MD5 вероятность коллизии 1 / (2^64). Для чисел небольшой разрядности неплохие результаты показывает Hsieh Hash (h**p://w*w.azillionmonkeys.com/qed/hash.html). Если не нравится простой цикл - поставьте MT (h**p://en.wikipedia.org/wiki/Mersenne_twister)
     
  5. MSoft

    MSoft New Member

    Публикаций:
    0
    Регистрация:
    16 дек 2006
    Сообщения:
    2.854
    поищи по словам "перестановки", "размещение"
    http://wasm.ru/forum/viewtopic.php?id=26149
    http://wasm.ru/forum/viewtopic.php?pid=351130#p351130
     
  6. wsd

    wsd New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2007
    Сообщения:
    2.824
    MSoft gazlan
    огромное спасибо!

    MSoft
    добавления лучше отдельным постом делать, а не правкой.
    а то в списке новых сообщений не видно
     
  7. MSoft

    MSoft New Member

    Публикаций:
    0
    Регистрация:
    16 дек 2006
    Сообщения:
    2.854
    да флудить не хотелось
     
  8. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Генераторы, у которых период равен 2^32 или 2^32-1, то есть простейшие конгруэнтный или crc-гамма дают числа во всем диапазоне ни разу не повторяясь, пока не пробегут всевозможные значения, в чем вопрос?
     
  9. MSoft

    MSoft New Member

    Публикаций:
    0
    Регистрация:
    16 дек 2006
    Сообщения:
    2.854
    вопрос в случайности. Если вызвать этот генератор несколько раз, будут ли 2 ряда чисел отличаться?
     
  10. n0name

    n0name New Member

    Публикаций:
    0
    Регистрация:
    5 июн 2004
    Сообщения:
    4.336
    Адрес:
    Russia
    persicum
    в том чтоб свести к некратному диапазону.
     
  11. Clerk

    Clerk Забанен

    Публикаций:
    0
    Регистрация:
    4 янв 2008
    Сообщения:
    6.689
    Адрес:
    РБ, Могилёв
    Тоже не понимаю смысла задачи. Ввести глобальную переменную, содержащую опорный Seed. Иначе всегда будет вероятность повторения, ибо опорное значение рандомно.
     
  12. kropalik

    kropalik New Member

    Публикаций:
    0
    Регистрация:
    27 апр 2005
    Сообщения:
    155
    Адрес:
    msk
    Взять последовательность 1,2,3... (считаем что все числа - 64бит)
    и зашифровать блочным шифром с размером блока 64 и рандомным ключом.
     
  13. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    ага, теперь немного понятно. Разумеется, генераторы с периодом 2^32 будут повторятся после пробега по всему пространству - давать ту же самую последовательность.

    Значит можно взять те же простейшие быстрейшие генераторы, но с периодом 2^64, которые имеют SEED 64 бит. Их проекции на 32 бит тогда НЕ БУДУТ ПОВТОРЯТСЯ.
     
  14. AsmGuru62

    AsmGuru62 Member

    Публикаций:
    0
    Регистрация:
    12 сен 2002
    Сообщения:
    689
    Адрес:
    Toronto
    persicum
    Если есть 2^64 РАЗНЫХ чисел и 32-бита из них не будут повторяться?
    Это сомнительно. Скорее, они повторятся, но в псевдо-случайном порядке.
     
  15. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Праильна, вот зашел чтобы поправится =)))
    Если нужны неповторяющиеся числа, но повторяющаяся периодичность, бери период 2^32
    Если нужена именно неповторяющаяся последовательность, но возможны повторения отдельных чисел, то бери 64 бит генератор и младшие 32 бит.

    А чтобы угодить и тем и другим построй конгруентный генератор с периодом 2^48, тогда разделив его выдачу на 2^48 получишь неповторяющиеся вещественные с периодом 2^48 - очень большой период, можно считать что устроит. А если совсем круто, то делай генератор с периодом 2^52 или чтобы не было нуля 2^52-1, сувай в double - и период будет офигенным и ни одно число не будет повторяться.
     
  16. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Нужно особенно подчеркнуть, что хороший вещественный генератор теоретически невозможен на базе вещественной математики. Хороший вещественный генератор возможен только на базе дискретной математики. Поэтому смотри, скока целых бит вмещается в double - 52 бита мантисса. Поэтому нужно построить целочисленный генератор именно на 52 бита и разделить его выдачу на 2^52.
     
  17. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    тут есть 2е проблемы.
    рандомный генератор будет давать повторяющиеся числа.
    генератор последовательностей предсказуем при повторном пробеге (#13).

    в первом случае можно чекать по таблице (32 число - 16м таб)
    во втором бежать по последовательности с неким некратным шагом. шаг выбирать в 0 позиции поледовательности произвольно. для упрощения саму длину последовательности можно выбрать простой

    можно еще их собирать вручную из 2х-3х случайных целых.
     
  18. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    933
    Существует множество "плохих" генераторов которые дают в пределах модуля (N) непересекающиеся петли. Например:

    Xi+1=((Xi ror A) mul B) mod N.

    При задании разных X0 они образуют множества (петли) внутри N, причем эти петли не пересекаются.

    Единственная проблема - нужно помнить номер "петли" (внутри функции или вызывющий). Возможно как-то можно аналитически получить элемент не принадлежащий к данной петле = func(A,B,Xi).
     
  19. leo

    leo Active Member

    Публикаций:
    0
    Регистрация:
    4 авг 2004
    Сообщения:
    2.542
    Адрес:
    Russia
    MSoft
    qqwe
    Насколько я понимаю, сама задача #1 предусматривает только один пробег (просто получение очередного квазислучайного числа, отличного от всех предыдущих). Если так, то достаточно взять генератор последовательности нужной длины и "просто" запоминать его состояние, чтобы при последующих вызовах генерить последовательность дальше
     
  20. persicum

    persicum New Member

    Публикаций:
    0
    Регистрация:
    2 фев 2007
    Сообщения:
    947
    Пытался переосмыслить правила построения конгруэнтного генератора применительно к 2^n.

    x = ( a x + b) mod 2^n, достаточно взять b нечетное и чтобы (a-1) делилось на 4. Так?