2014 dxdy logo

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

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




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

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

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

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

 
 
 
 Python 2 С++
Сообщение21.03.2008, 08:59 
помогите перевести код из 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)

 
 
 
 
Сообщение21.03.2008, 10:26 
Аватара пользователя
Вот отсканировал из "Алгебраической Алгоритмики" первые три странички из п. 4.3:

Изображение

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

 
 
 
 
Сообщение21.03.2008, 23:13 
Аватара пользователя
:evil:
Код:
power = lam = 1
Тоже самое, что и в С: последовательное присваивание.

Код:
tortoise, hare = x0, f(x0)
Это уже хитрее: это покомпонентное присваивание. Оно эквивалентно (в данном случае)
Код:
tortoise = x0
hare = f(x0)
Полной эквивалентности нет, поскольку правая часть вычисляется раньше левой, что позволяет писать
Код:
a, b = b, a
для перестановки.

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

 
 
 
 
Сообщение22.03.2008, 02:59 
maxal, да, спасибо - это то, что я искал...

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

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

 
 
 
 
Сообщение22.03.2008, 03:05 
Аватара пользователя
loop там не оператор, а ключевое слово, появляющееся в начале и конце цикла - как begin ... end в паскале или скобки { ... } в C.

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

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

 
 
 
 Re: Python 2 С++
Сообщение22.03.2008, 04:19 
Аватара пользователя
:evil:
Код:
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) в конце просто напечатал результат.

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

 
 
 
 
Сообщение22.03.2008, 14:09 
Аватара пользователя
$$x\mapsto 10x\bmod{7^2}$$

 
 
 
 
Сообщение22.03.2008, 19:28 
Аватара пользователя
темы объединены.

 
 
 
 
Сообщение22.03.2008, 20:26 
вот и замечательно, а то снова задумался в какой теме задать вопрос... в след. раз буду аккуратнее...

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

Но Ваша версия мне нравится больше, только есть несколько вопросов:
  • 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}$ или еще как-то преобразовывается...

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

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

Код:
T* ff(T* item) {
  return item->next;
}

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


Марк писал(а):
Есть необходимость…

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

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


см. тут

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

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

maxal писал(а):
см. тут

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

 
 
 
 
Сообщение23.03.2008, 02:17 
Аватара пользователя
Марк писал(а):
или как 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;
}


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

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


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