Алгоритм. Метод Брента

[незваный гость]

Марк писал(а):

т.е. $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()

[maxal]

незваный гость писал(а):

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

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

[незваный гость]

Если только датчик линейно-конгруэнтный. Что отнюдь не гарантируется.

Строго говоря, 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() будет ма́ло.

[maxal]

незваный гость писал(а):

Если только датчик линейно-конгруэнтный. Что отнюдь не гарантируется.

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

[незваный гость]

maxal писал(а):

незваный гость писал(а):

Если только датчик линейно-конгруэнтный. Что отнюдь не гарантируется.

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

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

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

[Марк]

незваный гость писал(а):

: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$.

[незваный гость]

Марк писал(а):

период равен 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}$. Это не так уж просто обеспечить с датчиками случайных чисел. По меньшей мере, библиотечные функции С/С++ этого не обеспечивают.

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

[Марк]

незваный гость писал(а):

: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}$. Это не так уж просто обеспечить с датчиками случайных чисел. По меньшей мере, библиотечные функции С/С++ этого не обеспечивают.

с этим понял.

незваный гость писал(а):

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

а вот тут нечего не ясно

[незваный гость]

Марк писал(а):

я так понял, 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()?

[Марк]

незваный гость писал(а):

: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$.

[незваный гость]

Конечно, не соответствует. Именно это я и пытался Вам так долго сказать.

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

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);

[Марк]

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()$;

[незваный гость]

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. Это приводит к любопытному вопросу: можно ли при помощи алгорифмов Флойда, Брента проверять датчики случайных чисел? Чем больше думаю, тем больше сомневаюсь.

[Марк]

незваный гость писал(а):

: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})$, в СП такой зависимость не должно быть...

[незваный гость]

Марк писал(а):

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

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

Марк писал(а):

я не совсем понимаю...

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

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