Здравствуйте, понимаю что не совсем по теме, но вот показали мне код и спросили, а действительно ли функция Shift_Registr возвращает случайную величину с равномерным распределением?

type
  TRegType = array [1..200] of Bool;

//...


// Начальная инициалиция регистра сдвига для дальнейшего
// формирования ПСП

procedure Init_Registr(var reg: TRegType);
var
  i: Integer;
begin
  Randomize;
  Reg[1] := 1;
  for i := 2 to 200 do
    Reg[i] := Random(2);
end;


// Сдвиг регистра и получение СВ с равномерным распределением
// в интервале (0,1)

function Shift_Registr(m, n: Integer; var reg: TRegType): Real;
var
  i: Integer;
  r: Real;
  b: Bool;
  step: Integer;
  MaxValue: Longint;
begin
  step := 1;
  MaxValue := 0;
  r := 0;
  for i := 1 to m do
  begin
    r := r + step * Reg[i];
    MaxValue := MaxValue + step;
    step := step * 2;
  end;
  r := r / MaxValue;
  b := Reg[n] xor Reg[m];

  for i := m downto 2 do
    Reg[i] := Reg[i - 1];

  Reg[1] := b;
  Result := r;
end;

Что-либо против сказать не смог, но результаты получаемые с помощью этого кода не совсем адекватные...

A>Что-либо против сказать не смог, но результаты получаемые с помощью этого кода не совсем адекватные...

1) Гм, во-первых, неясно, с какими параметрами вызывается функция Shift_Registr?
2) Навскидку — бросается в глаза то, что переменные step и MaxValue могут переполняться (длина регистра — 200, что явно превышает размерность целочисленных типов даже в 64-битных компиляторах).
3) В качестве быстрого неплохого теста можно взять построение "случайных" точек на плоскости, где координаты X и Y берутся от тестируемого генератора. Любая неравномерность/сильная корреляция будут явно видны на глаз. Насколько плохо всё бывает — можно посмотреть тут (кубик с визуализацией):
http://en.wikipedia.org/wiki/Linear_congruential_generator
4) А вообще, конструирование хороших ГПСЧ — дело очень тонкое. Тут самое разумное — взять готовое проверенное решение (если, конечно, это не вопрос с собеседования)

Здравствуйте, andy1618, Вы писали:

A>>Что-либо против сказать не смог, но результаты получаемые с помощью этого кода не совсем адекватные...

A>1) Гм, во-первых, неясно, с какими параметрами вызывается функция Shift_Registr?
A>2) Навскидку — бросается в глаза то, что переменные step и MaxValue могут переполняться (длина регистра — 200, что явно превышает размерность целочисленных типов даже в 64-битных компиляторах).
A>3) В качестве быстрого неплохого теста можно взять построение "случайных" точек на плоскости, где координаты X и Y берутся от тестируемого генератора. Любая неравномерность/сильная корреляция будут явно видны на глаз. Насколько плохо всё бывает — можно посмотреть тут (кубик с визуализацией):
A>http://en.wikipedia.org/wiki/Linear_congruential_generator
A>4) А вообще, конструирование хороших ГПСЧ — дело очень тонкое. Тут самое разумное — взять готовое проверенное решение (если, конечно, это не вопрос с собеседования)



Спасибо! Это не вопрос с собеседования, это с научной работы одного студента (нет не моей ) в которой что-то реально не так — а вот мне сказали — "разбирись"...

A>Спасибо! Это не вопрос с собеседования, это с научной работы одного студента (нет не моей ) в которой что-то реально не так — а вот мне сказали — "разбирись"...

Научная работа? Круто!
Может, конечно, все эти переполнения и т.п. специально были заложены в код генератора, и на самом деле он выдаёт идеальные результаты, но что-то мне подсказывает, что это не так.
Убедиться в качестве (а точнее, в его отсутствии), как я уже писал выше, легко. В качестве образца для сравнения можно взять стандартный генератор компилятора — для большинства применений его вполне хватает.

Ну а если хочется с этим кодом разобраться, то про генераторы на сдвиговых регистрах можно почитать вот тут (к сожалению, русской странички пока нет):
http://en.wikipedia.org/wiki/Linear_feedback_shift_register

Если же цель — создать свой качественный ГПСЧ, то нахваливают генератор на основе "Вихря Мерсенна":
http://en.wikipedia.org/wiki/Mersenne_twister (там слева есть ссылка и на русскую сокращённую версию)

Здравствуйте, andy1618, Вы писали:

A>>Спасибо! Это не вопрос с собеседования, это с научной работы одного студента (нет не моей ) в которой что-то реально не так — а вот мне сказали — "разбирись"...

A>Научная работа? Круто!
A>Может, конечно, все эти переполнения и т.п. специально были заложены в код генератора, и на самом деле он выдаёт идеальные результаты, но что-то мне подсказывает, что это не так.
A>Убедиться в качестве (а точнее, в его отсутствии), как я уже писал выше, легко. В качестве образца для сравнения можно взять стандартный генератор компилятора — для большинства применений его вполне хватает.

A>Ну а если хочется с этим кодом разобраться, то про генераторы на сдвиговых регистрах можно почитать вот тут (к сожалению, русской странички пока нет):
A>http://en.wikipedia.org/wiki/Linear_feedback_shift_register

A>Если же цель — создать свой качественный ГПСЧ, то нахваливают генератор на основе "Вихря Мерсенна":
A>http://en.wikipedia.org/wiki/Mersenne_twister (там слева есть ссылка и на русскую сокращённую версию)



Еще раз спасибо за ответ. Вы правы, это научная работа по теме "Meteor Burst Communication" (Метеорный канал связи, ну а точнее создание его програмной модели). Начинал это не я, но исправлять теперь мне. Вся проблема в том, что (судя по всему именно из за этого кода) при построении характеристик, которые должны расти по экспоненте, наблюдается "завал", а этого быть не должно... Вот и ищу "баги"

>Здравствуйте, понимаю что не совсем по теме, но вот показали мне код и спросили, а действительно ли функция Shift_Registr возвращает случайную величину с равномерным распределением?
юзай матстатистику, раздел "проверка статистических гипотез" — там как раз есть примеры проверки, является ли выборка реализацией случайной величины с требуемым распределением.

только деталей сообщить не могу, ибо.... за 5 лет всё забылось

A>Еще раз спасибо за ответ. Вы правы, это научная работа по теме "Meteor Burst Communication" (Метеорный канал связи, ну а точнее создание его програмной модели). Начинал это не я, но исправлять теперь мне. Вся проблема в том, что (судя по всему именно из за этого кода) при построении характеристик, которые должны расти по экспоненте, наблюдается "завал", а этого быть не должно... Вот и ищу "баги"

1. Можно заменить этот код заведомо "хорошим" генератором случайных чисел и посмотреть результат. Если "завал" уйдет, скорее всего проблема именно в исходном алгоритме.

2. Еще можно проверить опытным путем сам алгоритм на больших количествах генерируемых чисел

Здравствуйте, aleckstein, Вы писали:

A>Здравствуйте, понимаю что не совсем по теме, но вот показали мне код и спросили, а действительно ли функция Shift_Registr возвращает случайную величину с равномерным распределением?
A>Что-либо против сказать не смог, но результаты получаемые с помощью этого кода не совсем адекватные...

Хехе, ну и вопрос. Оценка ГПСЧ — это работа научная. То что тебе дали алгоритм — это еще не говорит ни о чем.
Есть три способа оценить правильность ГПСЧ:
1. Эмпирический
2. Теоритический
3. Не помню

Вторым способом ты точно не решишь, просто уверен в этом. Первым способом — тебе надо нагенерить случайных велечин этим генератором и на основе этой выборки сделать оценку.
Во-первых, надо оценить всего два параметра:
1. Независимость выборки
2. Равномерность распределения.

Детали как оценивать независимость выборки и отсутствие корреляций — смотри в книгах. С помощью стат-прог можно построить двумрный и трехмерный plot и посмотреть на корреляции. Обычно зависимые данные сразу видно так как они уладываются плоскости.

По равномерности распределения — надо выдвинуть гипотезу и ее проверить. Есть три критерия по-моему для этой проверки.

Как это сделаешь, нагенери еще две три разные большие выборки и сделай на них тоже самое. Собственно все.

Во-вторых можно сразу проверить на цикличность. Это поможет только случае, если код который тебе дали имеет очень маленький цикл и зацикливается быстро. Тогда обнаружив это ты можешь сазать что это плохой генератор без проверки независимости и равномерности. Успехов.

Здравствуйте, aleckstein, Вы писали:

A>Здравствуйте, понимаю что не совсем по теме, но вот показали мне код и спросили, а действительно ли функция Shift_Registr возвращает случайную величину с равномерным распределением?

конечно нет. Так как это не сдвиговый регистр, а линейный сдвиговый регистр. imho

A>

A>type
A>  TRegType = array [1..200] of Bool;

A>//...


A>// Начальная инициалиция регистра сдвига для дальнейшего
A>// формирования ПСП

A>procedure Init_Registr(var reg: TRegType);
A>var
A>  i: Integer;
A>begin
A>  Randomize;
A>  Reg[1] := 1;
A>  for i := 2 to 200 do
A>    Reg[i] := Random(2);
A>end;


A>// Сдвиг регистра и получение СВ с равномерным распределением
A>// в интервале (0,1)

A>function Shift_Registr(m, n: Integer; var reg: TRegType): Real;
A>var
A>  i: Integer;
A>  r: Real;
A>  b: Bool;
A>  step: Integer;
A>  MaxValue: Longint;
A>begin
A>  step := 1;
A>  MaxValue := 0;
A>  r := 0;
A>  for i := 1 to m do
A>  begin
A>    r := r + step * Reg[i];
A>    MaxValue := MaxValue + step;
A>    step := step * 2;
A>  end;
A>  r := r / MaxValue;
A>  b := Reg[n] xor Reg[m];

A>  for i := m downto 2 do
A>    Reg[i] := Reg[i - 1];

A>  Reg[1] := b;
A>  Result := r;
A>end;
A>

A>Что-либо против сказать не смог, но результаты получаемые с помощью этого кода не совсем адекватные...

"b := Reg[n] xor Reg[m];"

период будет длинным только в случае, если числа m n образуют примитивный полином.