2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 
Сообщение23.03.2008, 02:49 
Заслуженный участник
Аватара пользователя


17/10/05
3709
: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 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 
Сообщение23.03.2008, 03:30 
Заслуженный участник
Аватара пользователя


17/10/05
3709
: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 
Модератор
Аватара пользователя


11/01/06
5660
незваный гость писал(а):
Если только датчик линейно-конгруэнтный. Что отнюдь не гарантируется.

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

 Профиль  
                  
 
 
Сообщение23.03.2008, 08:21 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
maxal писал(а):
незваный гость писал(а):
Если только датчик линейно-конгруэнтный. Что отнюдь не гарантируется.

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

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

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

 Профиль  
                  
 
 
Сообщение23.03.2008, 15:22 


24/12/06
59
незваный гость писал(а):
: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 
Заслуженный участник
Аватара пользователя


17/10/05
3709
: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 


24/12/06
59
незваный гость писал(а):
: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 
Заслуженный участник
Аватара пользователя


17/10/05
3709
: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 


24/12/06
59
незваный гость писал(а):
: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 
Заслуженный участник
Аватара пользователя


17/10/05
3709
: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 


24/12/06
59
Код:
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 
Заслуженный участник
Аватара пользователя


17/10/05
3709
: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 


24/12/06
59
незваный гость писал(а):
: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 
Заслуженный участник
Аватара пользователя


17/10/05
3709
:evil:
Марк писал(а):
- на выходи не получаем значение ($x_{i+1}$) послдедовательности в чистом виде... а в $rnd()$ мы как раз его и предеаем...

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

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 33 ]  На страницу Пред.  1, 2, 3  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group