2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2, 3  След.
 
 
Сообщение23.03.2008, 02:49 
Аватара пользователя
:evil:
Марк писал(а):
т.е. $x_0 = rand();$ потом вызываем $srand(x_0);$ и получаем $x_1=rand();$?
или как seed меняется с каждым вызовом rand()?

Увы, нет. Нужно что-то такое:
Код:
class T {
  int randomValue;
  unsigned long int seed;

  T() {
    seed = 1; // whatever
    update();
  }

  void update() {
    srand(seed);
    randomValue = rand();
    seed = __seed; // this is implementation dependent
  }

}

Одна из не бросающихся в глаза проблем — не существует стандартного (а значит, переносимого) способа прочитать seed из библиотеки. Выставить-то его просто — srand()

 
 
 
 
Сообщение23.03.2008, 03:04 
Аватара пользователя
незваный гость писал(а):
Одна из не бросающихся в глаза проблем — не существует стандартного (а значит, переносимого) способа прочитать seed из библиотеки. Выставить-то его просто — srand()

При желании seed можно вычислить по нескольким последовательным значениям rand(), хотя это не такая уж и тривиальная задача.

 
 
 
 
Сообщение23.03.2008, 03:30 
Аватара пользователя
:evil:
Если только датчик линейно-конгруэнтный. Что отнюдь не гарантируется.

Строго говоря, srand() задаёт некоторое начальное состояние датчика. Легко себе представить датчик, состояние которого не эквивалентно seed. Например, перевычисление состояния $s'_k = (a_k s_k + c_k) \mod m_k$, $rand(): \frac{RAND\_MAX}{K} \sum_{k=1}^K \frac{s_k}{m_k}$, $srand(): s_k = seed$. В этом случае нужно сохранять / восстанавливать все $s_k$, и srand() будет ма́ло.

 
 
 
 
Сообщение23.03.2008, 03:54 
Аватара пользователя
незваный гость писал(а):
Если только датчик линейно-конгруэнтный. Что отнюдь не гарантируется.

В данном случае речь идёт о Borland Turbo C++ 3.0, для которого это так.

 
 
 
 
Сообщение23.03.2008, 08:21 
Аватара пользователя
:evil:
maxal писал(а):
незваный гость писал(а):
Если только датчик линейно-конгруэнтный. Что отнюдь не гарантируется.

В данном случае речь идёт о Borland Turbo C++ 3.0, для которого это так.

И для которого период известен теоретически, так что программировать вообще ничего не надо.

Я полагаю, что речь идёт о программировании алгоритма (и понимании его работы), а датчик случайных чисел выбран как пример (не очень удачный, на мой вкус) генератора последовательности.

 
 
 
 
Сообщение23.03.2008, 15:22 
незваный гость писал(а):
:evil:
maxal писал(а):
незваный гость писал(а):
Если только датчик линейно-конгруэнтный. Что отнюдь не гарантируется.

В данном случае речь идёт о Borland Turbo C++ 3.0, для которого это так.

И для которого период известен теоретически, так что программировать вообще ничего не надо.

период равен RAND_MAX? или m?

незваный гость писал(а):
:evil:
Я полагаю, что речь идёт о программировании алгоритма (и понимании его работы), а датчик случайных чисел выбран как пример (не очень удачный, на мой вкус) генератора последовательности.

для примера я взял: $(4096 x_i + 150889)\mod 714025$
А относительно rand(): мне было интересно, какой будет получен период, если в функцию brent() подавать результат rand();

Вернусь к алгоритму: какое значение имеет параметр x0, если его изменение не влияет на занчение lambda и mu, по крайне мере для последовательности $(4096 x_i + 150889)\mod 714025$.

 
 
 
 
Сообщение23.03.2008, 20:51 
Аватара пользователя
:evil:
Марк писал(а):
период равен RAND_MAX? или m?

В конкретном случае Borland Turbo C++ 3.0, он должен быть $m$.

Марк писал(а):
А относительно rand(): мне было интересно, какой будет получен период, если в функцию brent() подавать результат rand();

Вернусь к алгоритму: какое значение имеет параметр x0, если его изменение не влияет на занчение lambda и mu, по крайне мере для последовательности $(4096 x_i + 150889)\mod 714025$.

Мне кажется, Вам надо внимательно разобраться в том, как работает алгоритм(ы).

Основное предположение: мы имеем дело с рекурентно заданной последовательностью, $x_0, x_{i+1} = f(x_i)$, и пытаемся определить, периодична ли она (начиная с некоторого места). Отсюда два параметра у функций brent() и floid().

Обратите внимание: неявно предполагается, что если $f()$ получила на вход $x_i$, она всегда выдаст на выходе $x_{i+1}$. Это не так уж просто обеспечить с датчиками случайных чисел. По меньшей мере, библиотечные функции С/С++ этого не обеспечивают.

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

 
 
 
 
Сообщение25.03.2008, 01:08 
незваный гость писал(а):
:evil:
Марк писал(а):
какое значение имеет параметр x0, если его изменение не влияет на занчение lambda и mu, по крайне мере для последовательности $(4096 x_i + 150889)\mod 714025$.

Мне кажется, Вам надо внимательно разобраться в том, как работает алгоритм(ы).
я так понял, x0, играет роль только в тех случаях, когда последовательность не сразу входит в цикл, как в примере на вики: 2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ...

незваный гость писал(а):
Основное предположение: мы имеем дело с рекурентно заданной последовательностью, $x_0, x_{i+1} = f(x_i)$, и пытаемся определить, периодична ли она (начиная с некоторого места). Отсюда два параметра у функций brent() и floid().

Обратите внимание: неявно предполагается, что если $f()$ получила на вход $x_i$, она всегда выдаст на выходе $x_{i+1}$. Это не так уж просто обеспечить с датчиками случайных чисел. По меньшей мере, библиотечные функции С/С++ этого не обеспечивают.
с этим понял.

незваный гость писал(а):
Возможны варианты: например, убедиться, что алгоритм и константы известны, и реализовать датчик случайных чисел как класс. В этом случае мы имеем имеем два независимых экземпляра датчика, выдающих одинаковую последовательность.
а вот тут нечего не ясно :oops:

 
 
 
 
Сообщение25.03.2008, 05:37 
Аватара пользователя
:evil:
Марк писал(а):
я так понял, x0, играет роль только в тех случаях, когда последовательность не сразу входит в цикл, как в примере на вики: 2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ...

Абсолютно неверно. Рассмотрите классическую последовательность Колатца:
Код:
long colatz(long k) {
  if (k <= 0)     return k-1;
  else if (k & 1) return 3*k + 1;
  else            return k / 2;
}

Очевидно, что результат алгоритма сильно зависит от выбора $x_0$: при $x_0 \le 0$ последовательность не имеет циклов, при $x_0 > 0$ — предположительно имеет. (Я игнорирую переполнение.)

Марк писал(а):
а вот тут нечего не ясно

Хорошо, давайте по шагам. Как Вы предполагаете написать функцию вызывающую rand(), которую Вы передадите параметром в brent()?

 
 
 
 
Сообщение26.03.2008, 03:56 
незваный гость писал(а):
:evil:
Марк писал(а):
я так понял, x0, играет роль только в тех случаях, когда последовательность не сразу входит в цикл, как в примере на вики: 2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ...

Абсолютно неверно. Рассмотрите классическую последовательность Колатца:
Код:
long colatz(long k) {
  if (k <= 0)     return k-1;
  else if (k & 1) return 3*k + 1;
  else            return k / 2;
}

Очевидно, что результат алгоритма сильно зависит от выбора $x_0$: при $x_0 \le 0$ последовательность не имеет циклов, при $x_0 > 0$ — предположительно имеет. (Я игнорирую переполнение.)

достаточно убедительно :) спасибо

незваный гость писал(а):
Марк писал(а):
а вот тут нечего не ясно

Хорошо, давайте по шагам. Как Вы предполагаете написать функцию вызывающую rand(), которую Вы передадите параметром в brent()?

изначально я пробывал так:
Код:
typedef long int FType;
typedef FType (*NextFunction)(FType);

FType rnd(FType seek){
   return rand();
}

int main(){
   srand(seek);      //x0 = seek;
   brent(rnd,1); //x0 - седсь уже не важно, что предадим как x0
   return 0;
}
получал:
    seek = 1 : lambda = 2274, mu = 47490
    seek = 5 : lambda = 5217, mu = 18208
    seek = 11: lambda = 12475, mu = 1832
я предпологал, что в конце выполненя rand() делает что-то подобное:
Код:
__seek = xi;
return xi;
но это оказалось неверно, и я решил сам переопределять __seek, подобным образом:
Код:
FType rnd(FType seek){
   srand(seek);
   return rand();
}

int main(){
   brent(rnd,seek);
}
получал:
    seek = 1: lambda = 424, mu = 105
    seek = 5: lambda = 39, mu = 1
    seek: 11: lambda = 424, mu = 408
Но и в первом и во втором случаи, полученный результат не соответствует теоретическому:
незваный гость писал(а):
В конкретном случае Borland Turbo C++ 3.0, он должен быть $m$.

 
 
 
 
Сообщение26.03.2008, 04:23 
Аватара пользователя
:evil:
Конечно, не соответствует. Именно это я и пытался Вам так долго сказать.

Давайте сделаем следующий шаг:

Код:
srand(1);
printf("%d %d\n", rand(), rand());

srand(1);
int x = rnd(1);
int y = rnd(x);
printf("%d %d\n", x, y);


Почему результаты разные?

Кстати, обратите внимание: я не использую brent(). Разделяй и властвуй — это один из основных приёмов в анализе программ. В данном случае, нам исключительно важно убедиться, что у нас правильная функция f() до того, как мы начали тестировать brent().

Добавлено спустя 6 минут 44 секунды:

В идеальном случае, мы должны иметь что-то такое:

Код:
srand(1);
printf("%d %d %d\n", rand(), rand(), rand());

srand(1);
int x1 = f(x0);
int x2 = f(x1);
int x3 = f(x2);

// результаты должны совпасть
printf("%d %d %d\n", x1, x2, x3);

int y1 = f(x0);
int y2 = f(y1);
int y3 = f(y2);

// результаты должны совпасть
printf("%d %d %d\n", y1, y2, y3);

int z2 = f(y1);
int z3 = f(z2);

// результаты должны совпасть
printf("%d %d %d\n", y1, z2, z3);

 
 
 
 
Сообщение26.03.2008, 04:58 
Код:
srand(1);
printf("%d %d %d\n", rand(), rand(), rand());

srand(1);
int x1 = f(x0);
int x2 = f(x1);
int x3 = f(x2);

// результаты должны совпасть
printf("%d %d %d\n", x1, x2, x3);

int y1 = f(x0);
int y2 = f(y1);
int y3 = f(y2);

// результаты должны совпасть
printf("%d %d %d\n", y1, y2, y3);

int z2 = f(y1);
int z3 = f(z2);

// результаты должны совпасть
printf("%d %d %d\n", y1, z2, z3);

$f()$ я так понял - это $rnd()$ (с внутреннем переопределение __seek)...
Тогда, как и ожидалось, во всех трех случаях вызова $rnd()$ для $x, y$ и $z$ получилось $x = y = z$; но результат не совпал с "чистым" вызовом $rand()$;

 
 
 
 
Сообщение26.03.2008, 05:50 
Аватара пользователя
:evil:
f() — это та функция, которую Вы передаёте параметром в brent().

Марк писал(а):
Тогда, как и ожидалось, во всех трех случаях вызова $rnd()$ для $x, y$ и $z$ получилось $x = y = z$; но результат не совпал с "чистым" вызовом $rand()$;

Значит…

P.S. Есть ещё один куплет: результаты, выдаваемые датчиком случайных чисел могут повторятся, и это не свидетельствует о его периодичности. Рассмотрите однобитный датчик: он может иметь любой период, но не позже третьего элемента Вы найдёте повторение: 0, 1, 1, 0, 1, 0, 0, 0… В частности, для Борландовского датчика $RAND\_MAX \ll m$.

P.P.S. Это приводит к любопытному вопросу: можно ли при помощи алгорифмов Флойда, Брента проверять датчики случайных чисел? Чем больше думаю, тем больше сомневаюсь.

 
 
 
 
Сообщение27.03.2008, 03:33 
незваный гость писал(а):
:evil:
f() — это та функция, которую Вы передаёте параметром в brent().
Марк писал(а):
Тогда, как и ожидалось, во всех трех случаях вызова $rnd()$ для $x, y$ и $z$ получилось $x = y = z$; но результат не совпал с "чистым" вызовом $rand()$;

Значит…

maxal писал(а):
Код:
unsigned short int rand() {   
  seed = (seed * a + c) % m;     // здесь возможно переполнение!
  return (seed >> 16) & 0x7FFF;
}

- на выходи не получаем значение ($x_{i+1}$) послдедовательности в чистом виде... а в $rnd()$ мы как раз его и предеаем...
незваный гость писал(а):
P.S. Есть ещё один куплет: результаты, выдаваемые датчиком случайных чисел могут повторятся, и это не свидетельствует о его периодичности. Рассмотрите однобитный датчик: он может иметь любой период, но не позже третьего элемента Вы найдёте повторение: 0, 1, 1, 0, 1, 0, 0, 0… В частности, для Борландовского датчика $RAND\_MAX \ll m$.

P.P.S. Это приводит к любопытному вопросу: можно ли при помощи алгорифмов Флойда, Брента проверять датчики случайных чисел? Чем больше думаю, тем больше сомневаюсь.

я не совсем понимаю... из того чему нас учили, датчик СЧ программным образом реализовать невозможно... и понятие случайность, в данном случаи относительное: если последовательность имеет период намного больше чем необходимое нам число "случайных чисел" и мы не знаем алгоритм генерации последовательности, то можно считать что она случайна для данной конкретной задачи...
А если брать истинно случайную последовательность. Алгоритм ведь предполагает вычисления $x_{i} = f(x_{i+1})$, в СП такой зависимость не должно быть...

 
 
 
 
Сообщение27.03.2008, 03:49 
Аватара пользователя
:evil:
Марк писал(а):
- на выходи не получаем значение ($x_{i+1}$) послдедовательности в чистом виде... а в $rnd()$ мы как раз его и предеаем...

Вы путаете две разных сущности: состояние датчика случайных чисел и выдаваемое им значение. Конкретно в Borland C 3.0, состояние — это 32 бита unsigned long, а выдаваемое значение — 15 бит signed int. Естественно, попытка трактовать выдаваемое значение как состояние не может увенчаться успехом.

Марк писал(а):
я не совсем понимаю...

Проблема, затронутая мной, состоит в том, что для датчика случайных чисел являются нормальными повторы. Например, Вы кидаете кубик семь раз. Какое-нибудь из чисел обязательно выпадет дважды. Но это не значит, что следом за ним выпадет то же число, что и в первый раз. Может выпасть, может и не выпасть.

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

 
 
 [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group