Специальный простой генератор случайных чисел

Question

Как создать функцию, которая при каждом вызове генерирует случайное целое число? Это число должно быть максимально случайным (в соответствии с равномерное распределение ). Разрешается использовать только одну статическую переменную и не более 3 элементарных шагов, где каждый шаг состоит только из одной базовой арифметической операции arity 1 или 2.

Пример:

int myrandom(void){
  static int x;
  x = some_step1;
  x = some_step2;
  x = some_step3;
  return x;
}

Основные арифметические операции: +, -,%, а не, xor, или, сдвиг влево, сдвиг вправо, умножение и деление. Конечно, никакие rand (), random () или подобные вещи не допускаются.

Answer 1

Линейные конгруэнтные генераторы являются одним из самых старых и простых методов:

int seed = 123456789;

int rand()
{
  seed = (a * seed + c) % m;
  return seed;
}

Только несколько инструкций с основными арифметическими операциями, это все, что вам нужно.

Помните, что этот алгоритм работает нормально, только если a , c и m выбраны особым образом!

Чтобы гарантировать максимально возможный период этой последовательности, c и m должны быть взаимно простыми, a -1 должно делиться на все простые множители м , а также на 4, если м делится на 4.

Некоторые примеры параметров показаны в Википедии: например, ANSI C для некоторых компиляторов предлагает m = 2³¹, a = 1103515245 и с = 12345.

Answer 2

public long randomLong() {
  x ^= (x << 21);
  x ^= (x >>> 35);
  x ^= (x << 4);
  return x;
}

Семя не может быть 0. Источник: http://www.javamex.com/tutorials/random_numbers/xorshift.shtml#.VlcaYzKwEV8

Дополнительная информация в вики: https://en.wikipedia.org/wiki/Xorshift

Answer 3

Вы могли бы взглянуть на это .Это далеко от того, чтобы быть «идеальным» генератором случайных чисел, но насколько я понимаю, он действительно отвечает вашим требованиям.

Здесь вы можете найти дополнительную информацию о генерации случайных чисел.

Answer 4

Я использую это

SUBROUTINE GNA(iiseed)
    USE Variaveis
    parameter (ia=843314861,ib=453816693,m=1073741824, r231=1./2147483648.)
    INTEGER :: iiseed

    iiseed = ib + ia*iiseed
    if (iiseed.lt.0) iiseed = (iiseed+m) + m
    RndNum = iiseed*r231

END SUBROUTINE GNA

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

Это очень хороший трюк!

Answer 5

Если я напишу man rand, я смогу прочитать возможный пример, приведенный в POSIX.1-2001, для реализации rand () и srand ().См. Например здесь .Если вам нужно что-то более сложное, взгляните на Научная библиотека GNU ;Вы, конечно, можете скачать код и увидеть реализацию (ы).

Answer 6

Вот функция с равномерным распределением по всему диапазону int:

int rand()
{
  static int random = 0;
  return random++;
}

Answer 7

Boost имеет очень хорошую библиотеку случайных чисел, и исходный код доступен, так что вы можете попробовать поискать там и использовать то, что вам нужно (то есть вырезать и вставить).