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

[Марк]

Ищу Алгоритм Брента определения длины $\lambda$ периода последовательности вида $X_{i+1}=f(x_i)$
Что-то похожее есть в книге Ноден П., Китте К. "Алгебраическая алгоритмика (с упражнениями и решениями)"
Глава IV. Некоторые методы алгебраической алгоритмики
4.3 Нахождение периода методом Брента

Хотелось бы ознакомится с этим алгоритмом. Но может кто-то подскажет альтернативный вариант определения длины периода...

Добавлено спустя 1 час 53 минуты 24 секунды:

В общем кое-что нашел но не на русском... и алгоритм на Python'е, может кто-то поможет с разъяснениями?
http://en.wikipedia.org/wiki/Cycle_dete ... _algorithm

[Марк]

помогите перевести код из Python в С++

def brent(f, x0):
    # main phase: search successive powers of two
    power = lam = 1
    tortoise, hare = x0, f(x0)
    while tortoise != hare:
        if power == lam:   # time to start a new power of two?
            tortoise = hare
            power = power + power
            lam = 0
        hare = f(hare)
        lam = lam + 1
 
    # Find the position of the first repetition of length lambda
    mu = 0
    tortoise = hare = x0
    for i in range(lam):
        hare = f(hare)
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu = mu + 1
 
    return lam, mu

Источник: http://en.wikipedia.org/wiki/Cycle_dete ... _algorithm

в частности, что значит такая вот запись:

    power = lam = 1
    tortoise, hare = x0, f(x0)

[maxal]

Вот отсканировал из "Алгебраической Алгоритмики" первые три странички из п. 4.3:



Дальше там оценка сложности этого метода выводится, ничего особого интересного.

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

power = lam = 1

Тоже самое, что и в С: последовательное присваивание.

tortoise, hare = x0, f(x0)

Это уже хитрее: это покомпонентное присваивание. Оно эквивалентно (в данном случае)

tortoise = x0
hare = f(x0)

Полной эквивалентности нет, поскольку правая часть вычисляется раньше левой, что позволяет писать

a, b = b, a

для перестановки.

Я посмотрю, если будет время — переведу.

[Марк]

maxal, да, спасибо - это то, что я искал...

теперь бы еще разобраться:

каким образом работает оператор $loop$ (я только понял, что он оргнаизует цикл)
что означают записи $j\gets 1$, $x\gets x_0$, $x' \gets x$ и т.д.
И назначение переменной $x'$.

[maxal]

loop там не оператор, а ключевое слово, появляющееся в начале и конце цикла - как begin ... end в паскале или скобки { ... } в C.

Стрелки типа такой $j\gets 1$ - это присвоение переменной значения. В данном случае полагают $j$ равным $1$.

В $x'$ хранится старое значение $x$, потом оно используется в операторе сравнения if $x=x'$ then...

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

typedef T* P;
typedef P (*NextFunction)(P);

void brent(NextFunction f, P x0)
{
   int power, lambda, mu;

   power = lambda = 1;
   P tortoise, hare;

   tortoise = x0; hare = f(x0);
   while (tortoise != hare) {
      if (power == lambda) {
         tortoise = hare;
         power *= 2;
         lambda = 0;
      }
      hare = f(hare); ++lambda;
   }

    // Find the position of the first repetition of length lambda
   mu = 0;
   tortoise = hare = x0;
   for (int ix = 0; ix < lambda; ++ix) {
      hare = f(hare);
   }
   while (tortoise != hare) {
      tortoise = f(tortoise);
      hare = f(hare);
      ++mu;
   }

   printf("lambda = %d, mu = %d\n", lambda, mu);
}

Я заменил lam на lambda (в оригинальном коде использование lam обусловлено тем, что lambda — ключевое слово Python'а), а вместо возвращения пары (lambda, mu) в конце просто напечатал результат.

[Марк]

в примере (из "копии" книги) есть функция десятичной записи числа $1/7^2$:
$***10x\mod 7^2 - там, где звечдочки - плохо отсканилось, если не сложно, что там должно быть?

[maxal]

$$x\mapsto 10x\bmod{7^2}$$

[нг]

темы объединены.

[Марк]

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

незваный гость, благодарю за алгоритм... правда, я еще ночью перекодил, но почему-то не работало... решил подождать Вашу версию... нечего не изменилось... оказалось, что последовательность с которой я сверял, выводил ее, как $ x_{i+1} = f(i), i = {0...n}$, вместо $ x_{i+1} = f(x_i)$

Но Ваша версия мне нравится больше, только есть несколько вопросов:

• typedef T* P; - T* - тип возвращяемого значения ($ x_{i+1}$) функции?
• ++lambda; - я обычно использую постфикс - сдесь это имеет значение?
• Как осуществить вызов функции brent, что указывать в качестве параметра NextFunction f

И вопрос с оффтопом:
Есть необходимость посчитать период функции rand();
в качестве компилятора используется Borland Turbo C++ 3.0, библиотека stdlib.h не подскажете параметры генератора: a, c и m, и возвращается сразу $ x_{i+1}$ или еще как-то преобразовывается...

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

Я как-то подсознательно предполагал, что речь идёт об обработки списков, поэтому имел в виду, что T — это тип элемента списка, а P, соответственно — указатель на него. В общем случае можно считать, что P — просто тип объекта (правда, при этом возникают нюансы — например, этот тип должен как-то хранить информацию о следующем элементе).

Префикс/постфикс в данном случае не важны, но я считаю, что следует писать префикс всегда, кроме тех случаев когда постфикс нужен.

 T* ff(T* item) {
  return item->next;
}

main() {
  brent(ff, item);
}

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

Есть необходимость…

Вам придётся создать класс, который будет хранить вместе с текущим значением случайной величины ещё и значение seed генератора, и каждый раз его обновлять. Алгоритмы (и Флойда, и Брента) не предполагают побочного эффекта вызываемой функции, а random() — типичный пример функции с побочным эффектом.

[maxal]

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

Есть необходимость посчитать период функции rand();
в качестве компилятора используется Borland Turbo C++ 3.0, библиотека stdlib.h не подскажете параметры генератора: a, c и m, и возвращается сразу $ x_{i+1}$ или еще как-то преобразовывается...

см. тут

[Марк]

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

Вам придётся создать класс, который будет хранить вместе с текущим значением случайной величины ещё и значение seed генератора, и каждый раз его обновлять. Алгоритмы (и Флойда, и Брента) не предполагают побочного эффекта вызываемой функции, а random() — типичный пример функции с побочным эффектом.

т.е. $x_0 = rand();$ потом вызываем $srand(x_0);$ и получаем $x_1=rand();$?
или как seed меняется с каждым вызовом rand()?

maxal писал(а):

см. тут

только не понимаю, как получается $m = 2^{32}$, если взять unsigned int, максимум получим $m = 2^{32} - 1$

[maxal]

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

или как seed меняется с каждым вызовом rand()?

maxal писал(а):

см. тут

только не понимаю, как получается $m = 2^{32}$, если взять unsigned int, максимум получим $m = 2^{32} - 1$

Все правильно. Вычеты по модулю $m$ образуют множество $\{0,1,\dots,m-1\}$. То есть, для $m=2^{32}$ как раз получается множество чисел представимых типом unsigned int.

А генератор работает примерно так:

static unsigned int seed;

void srand(unsigned int x) {  
   seed = x; 
}

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

Учтите, что это только пример. На практике все немного сложнее из-за того, что приходится старательно избегать переполнений.