Блог пользователя Perlik

"Длинный" rand на отрезке
Автор Perlik, 13 лет назад, По-русски
Кто-нибудь может подсказать, как реализовать rand на отрезке [l;r], где l,r приблизительно равны 10^200?
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Может сперва rand()'ом определить длину, назовем ее N. А дальше просто заполнить массив длины N случайными цифрами 0..9. И надо учесть, что число не может начинаться с 0. Ну, конечно, сделать так, чтобы рандомное число находилось между l и r.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Полученное число не обязательно будет лежать в данном отрезке.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Если нужно, дополним первое число нулями так, чтобы L и R были одинаковой длины.
Поддерживаем булевский флаг equal (сначала равен true).
Идем по числу слева направо. Если цифры равны и equal == true, ничего поменять нельзя и записываем их в ответ.
Если L[i] != R[i], то флаг equal сбрасываем и генерируем рандомное число в промежутке [L[i], R[i]], обозначим его gen.
Рассмотрим три случая:
  • gen == L[i] - тогда следующая цифра может быть от L[i + 1] до 9 включительно
  • gen == R[i] - тогда следующая цифра может быть от 0 до R[i + 1] включительно
  • L[i] < gen < R[i] - тогда все оставшиеся цифры числа произвольные
Для того, чтобы обрабатывать первые два случая, заведем переменные lower и upper.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    печаль, ответ запостился не там, где нужно

    http://codeforces.net/blog/entry/2564#comment-53483
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      И вправду, неравномерное распределение.

      А как тогда правильно делать?
      → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Надо посчитать сколько чисел можно сгенерировать, если взять L[i] и R[i], для промежуточных оно равно между собой, а потом найти вероятность в соответствии с мощностью множеств для возможных чисел L[i]..R[i].

    Вот да, если диапазон 09..19, то вероятность получтиь 09 будет 50% при исходном алгоритме.

    А при моём, 0 -> 1 число, 1 -> 9 чисел, тогда если rand < 0.1, то выбираем 0, иначе 1.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
при заданном диапазоне [99..999] кажется, что число 99 будет выскакивать достаточно часто =)
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

если генерировать длину равновероятно, то сгенерированное число не будет равновероятно распределено в [L..R]. Вообще алгоритм генерируемый длину должен сильно зависеть от L и R. Если хотите получить равновероятностное распределение на [L, R], то лучше всего сгенерировать равновероятно распределенное в [0,R - L] число, и затем прибавить к нему L  

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А как сделать от 0 до [R-L]? Использовать что-то типа rand() ^ (rand()<<15) только делать так несколько раз и в "длинной" вариации?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      пусть нам нужно сгенерировать число равновероятно распределенное на 0..n
      мы генерируем число Y длины A бит, равновероятно распределенное на [0,2^A - 1]
      и вычисляем X = Y % n. Ясно что у нас есть 2^A равновероятных возможностей выбрать число Y.
      если 2^A делится на n то все круто, и числа будут выпадать с одинаковой вероятностью.
      если не делиться, то обозначим остаток как d, 0 < d < n. фиксированное число из [0,d - 1]
      будет выпадать в (2^A / n) + 1 случаях, а число из [d,n - 1] в 2^A / n случаях.
      таким образом вероятность выпадения тех и других отличается на 1 / 2^A
      → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
думаю да, остается некоторая погрешность, но для её смягчения генерируем Y как число на 15 бит длиннее чем R - L, вычисляем X как остаток от деления Y на R - L. Думаю такая погрешность подойдет, хотя я не знаю вашей задачи.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
1. сгенерировать случайную 1000-значную строку из цифр, допустим 123456789...
2. считать эту строку, как дробную часть десятичной дроби, т.е. coeff = 0.123456789...
3. домножить R - L на это число coeff, получившееся число округлить в случайную сторону
4. прибавить L

кажется весьма хорошим способом
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Хм. Пусть R = 5, L=1 а строка будет не 1000-значной а 1-значной (считайте это первым символом 1000-значной строки). К 5-ке будут "случайно округляться" 5 чисел, а к остальным только 4. Не слишком большая неравномерность, но всё же похоже что "случайное округление" придётся придумывать гораздо аккуратнее.
    → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Щито?
      R-L = 4
      res = 4 * [ 0, 1 ) = случайное распределение чисел от 0 до 4.
      res + L = required
      → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      1. просили генерить большие числа. как известно, что верно в пределе - чаще всего неверно в крайности.
      2. это набросок алгоритма, а детали зависят от потребностей

      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да не, я не то чтоб с целью напасть и опорочить идею... %)

        Но в принципе чтобы не возиться с округлением, возможно можно предпочесть генерацию числа из диапазона, покрывающего необходимый. Если получившееся число не попадает в требуемые рамки, то повторяем процесс.

        При таком подходе "неравномерность" округления переходит в "неравномерность" времени выполнения, конечно... И для любого произвольно длинного отрезка времени существует ненулевая вероятность что генерация затянется как минимум на такое время... ;-)
        → Ответить
  • 13 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    А если брать R-L+1, тогда у нас будет отрезок, содержащий R-L+1 числа (все нужные).
    Тогда делаем точно так же и округляем всегда вниз - каждый полуинтервал [ T, T + 1 ) отвечает ровно за одно число T + L.
    → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
На самом деле мне нужно получить случайное число на отрезке [l;4*l+2] для генерации простого.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Для больших чисел и вероятностных алгоритмов теории чисел на больших числах правильнее заюзать нормальный генератор случайных числе, а не встроенный rand(), существуют другие псевдослучайные генераторы, но с большим периодом. Хотя для лабораторной по тестированию Миллера-Рабина и прочего в общем-то хватит и стандартного rand().
    → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Тебе случайно не для криптографических целей? Если так, то это отдельная история.
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да. Хочу написать RSA, уже все сделал - и длинку, и шифрование-расшифрование написал. Нигде не могу найти нормального алгоритма генерации большого случайного простого. Сейчас делаю так: беру какое-нибудь простое Мерсенна, равное x, и генерю рандомное на отрезке r=[x;4*x+2], а затем проверяю x*r+1 Миллером-Рабином. Просто на питоне rand вполне может и большие числа генерить, а на плюсах уже думать приходится)
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Для криптографических целей очень плохая идея использовать стандартные генераторы случайных чисел.
        Гугли специальные криптографические генераторы.
        Хотя, конечно, написание RSA - велосипед, он даже на php есть.
        → Ответить
        • 13 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Это конечно да, но захотелось попрактиковаться в написании не олимпиадного гавнокода, плюс заодно RSA вспомнил. За совет - спасибо.

          UPD. И правда, надо было вначале погуглить по теме...
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Где наш GrammarNazi? вторая буква не а, а о :)

            Практиковаться лучше на не математическом кодировании.
            Попробуй, например, написать какие-нибудь крестики-нолики на большом поле с plaggable AI или в духе. А потом нормальный AI для него :)
            → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
     Сначала надо бы понять, зачем он нужен, этот самый генератор и какие будут способы его проверки на случайность.
    Согласно теореме из теории вероятностей, берем генератор с любым известным непрерывным распределением, и легким движением руки  (с помощью функции, обратной к функции распределения) превращаем его в равномерное сначала на [0,1],  а потом и на [a,b] (банальным домножением, например). Оно конечно, будут получаться числа с почти что 200 нулями на конце, но если не трогать первые штук 10, а остальные рандомно поменять, то будет нечто вполне похожее на требуемое (как известно, первая цифры равномерно распределенного числа не будет равномерно распределена, распределение второй уже гораздо ближе к равномерному и т.д. ) 
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а в каком виде даны L и R? Если, например, в виде десятичных строк, то можно так:
Пусть T = R-L. Достаточно сгенерировать случайное число от 0 до T.
Путь k - минимальное натуральное число, такое, что T < 10^k.
1. Сгенерировать случайное число от 0 до (10^k)-1, это делается за O(k).
2. Проверить лежит ли оно в промежутке [0,T] - это тоже делается за O(k).
3. Если лежит - вернуть это число, иначе вернуться к пункту 1.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Если можно оперировать двоичным представлением этих чисел - тем лучше, работать будет в среднем 2 итерации (в худшем случае, когда T = 2^{k-1}), а не 10.
    → Ответить