Линейный конгруэнтный генератор в Python
Я пишу функцию LCG в Python, которую я буду использовать для симуляции типа Монте-Карло для подбрасывания монет и генерации прогонов. Проблема, с которой я сталкиваюсь, состоит в том, что, когда я генерирую список случайных чисел, числа формируются по шаблону так, что шансы и четности чередуются. Я не знаю, является ли это свойством самой функции LCG или ошибкой в том, как я генерирую числа.
def seedLCG(initVal): global rand rand = initVal def lcg(): a = 1140671485 c = 128201163 m = 2**24 global rand rand = (a*rand + c) % m return rand seedLCG(1) for i in range(10): print lcg() 10581448 11595891 1502322 14136437 11348076 1403015 9622582 11013417 11529808 15836891 Я предполагаю, что мне не нужно беспокоиться о переполнении и размере, потому что int и long взаимозаменяются по мере необходимости в Python.
2 ответа
a*rand умножает rand на нечетное число, поэтому результат всегда нечетный, когда rand странно, и даже когда rand даже. Затем вы добавляете нечетное число c , который меняется с нечетного на четный и наоборот. Модуль не влияет на последний бит. Итак, каждый звонок lcg переворачивается rand от нечетного к четному или от четного к нечетному.
Если вы серьезно относитесь к случайным числам (но вам не нужны криптостойкие), рассмотрите возможность использования numpy.random ,
Немного поздно на вечеринку, но может быть интересно другим. В Python 3 генератор псевдослучайных чисел можно построить, определив следующие две функции:
def LCG(a, c, m, seed): xi = seed while True: xf = (a * xi + c) % m xi = xf yield xf def random_sample(n, interval, seed = 20200420162000): lower, upper = interval[0], interval[1] sample = [] glibc = LCG(1103515245, 12345, 2 ** 32, seed) # parameters as in GNU C Library for i in range(n): observation = (upper - lower) * (next(glibc) / (2 ** 32 - 1)) + lower sample.append(int(observation)) return sample Первая функция — это фактическая LCG, реализованная как генератор (т. Е. Функция, возвращающая итерируемый объект), тогда как вторая функция выполняет итерацию по объекту-генератору для получения выборки. Последняя функция обычно вызывается конечным пользователем для генерации случайных чисел в пределах заданного интервала.
После определения обеих функций их можно использовать следующим образом:
sample = random_sample(100, [30, 90]) # 100 random numbers between 30 and 90 print(sample) [54, 77, 41, 61, 74, 49, 65, 66, 86, 39, 53, 69, 88, 75, 56, 67, 73, 63, 81, 56, 81, 42, 43, 56, 35, 58, 72, 61, 84, 88, 49, 77, 85, 58, 87, 61, 48, 41, 41, 70, 49, 64, 73, 47, 51, 56, 32, 66, 55, 61, 79, 72, 83, 60, 83, 74, 84, 59, 82, 56, 71, 47, 34, 53, 72, 82, 75, 34, 70, 33, 46, 66, 55, 45, 64, 40, 46, 71, 82, 35, 77, 66, 87, 88, 58, 45, 80, 30, 37, 69, 31, 68, 89, 68, 85, 58, 65, 54, 57, 51] Генерация — псевдослучайные данные. Линейные конгруэнтные генераторы
Пытаюсь выполнить задание.
1. Используя метод вычетов, сгенерировать последовательность из 1000 псевдослучайных чисел.
2. Осуществить проверку полученного генератора.
■ Оценить математическое ожидание полученной последовательности.
■ Оценить дисперсию полученной последовательности.
■ Оценить корреляционную функцию полученной последовательности по графикам При построении первого графика ограничиться первыми 20 значениями, второй график строится для всего множества сгенерированных значений.
■ Используя метод гистограмм, проверить гипотезу о законе распределения
Вот учебник
Но дело в следующем, меня смущает генерация. Подскажите как сгенерировать псевдослучайные данные, По условию у нас даны рекомендуемые параметры:
m = 231-1 =2 147 483 647
а = 630 360 016
Z0 = 4
Таким образом, наша функция приобретает вид:
Zi+1 = (a*Zi ) (mod m),
Вот тут какую функцию использовать .
r = random.randint(0, (a*Zmod1) % m, N)
print((r*r) % m)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
import math import cmath import matplotlib.pyplot as plt from numpy import random # Переменные из задания N = 1000 m = 2147483647 a = 630360016 Z0 = 4 Zmod1 = (a*Z0) % m #Вычисление модуля для Z0 (373 956 417) r = random.randint(0, (a*Zmod1) % m, N) print((r*r) % m) #radnom.seed((a*Zmod1) % m) #y = [random.uniform(-1,Z) for i in x] x = range(N) plt.plot(x, r, 'o') plt.show() y = [random.random() for i in range(1000)] plt.hist(y, 20) plt.show() from numpy import random, mean, var, std xm = mean(r) xv = var(r) xs = std(r) print (N, xm, xv, xs)
Linear Congruential Generator in Python
I am writing a LCG function in Python that I will use for a Monte Carlo type simulation for coin flips and generating runs. The problem I am facing is that when I generate a list of random numbers, the numbers are patterned such that odds and evens alternate. I don’t know whether that is a property of the LCG function itself or a mistake in how I am generating the numbers. Here is my code:
def seedLCG(initVal): global rand rand = initVal def lcg(): a = 1140671485 c = 128201163 m = 2**24 global rand rand = (a*rand + c) % m return rand seedLCG(1) for i in range(10): print lcg() 10581448 11595891 1502322 14136437 11348076 1403015 9622582 11013417 11529808 15836891 I’m assuming I don’t need to worry about overflow and size because int and long are interchanged as needed by Python.
Why do you want to implement your own rather than using python’s built-in generator or numpy’s options?
I am simply trying to learn how an LCG works. I did the same simulation with the built in generator as well.
3 Answers 3
a*rand multiplies rand by an odd number, so the result is always odd when rand is odd, and even when rand is even. You then add in the odd number c , which changes odd to even and vice versa. The modulo has no effect on the last bit. So, every call to lcg flips rand from odd to even or from even to odd.
If you’re serious about random numbers (but you don’t need crypto-strength ones), consider using numpy.random .
Okay, that makes sense. I have a couple follow up questions. Why does modulo have no effect on the last bit? Is this then a property of all LCG generators or would changing the parameter «a» change «a*rand» to always have an even value have an effect?
@SiddharthDhingra: because modulo 2^k never affects the lower-order k bits. As for a*rand , that would multiply by an odd number, having no effect on the evenness.
A tad late to the party, but it might be interesting to others. In Python 3, a pseudorandom number generator can be constructed by defining the following two functions:
def lcg(x, a, c, m): while True: x = (a * x + c) % m yield x def random_uniform_sample(n, interval, seed=0): a, c, m = 1103515245, 12345, 2 ** 31 bsdrand = lcg(seed, a, c, m) lower, upper = interval[0], interval[1] sample = [] for i in range(n): observation = (upper - lower) * (next(bsdrand) / (2 ** 31 - 1)) + lower sample.append(round(observation)) return sample The first function is the actual LCG implemented as a generator (i.e. a function returning an iterable object), while the second function iterates over the generator object to obtain a sample. The latter function would typically be called by an end user to generate pseudorandom numbers within a given interval.
After defining both functions, they can be employed as follows:
# 30 numbers between 0 and 100 rus = random_uniform_sample(30, [0, 100]) print(rus) [0, 66, 30, 67, 11, 52, 49, 60, 37, 26, 37, 83, 17, 30, 64, 79, 99, 80, 46, 54, 63, 25, 70, 72, 98, 33, 45, 71, 74, 17]