Нахождение цикла (Ug]k';yuny entlg)

Нахождение цикла — алгоритмическая задача поиска цикла в последовательности значений итеративной функции.

Для любой функции f, отображающей конечное множество S в себя, и для любого начального значения x₀ из S последовательность итеративных значений функции:

$x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots$

должна в конечном счёте использовать одно значение дважды, то есть должна существовать такая пара индексов i и j, что x_i = x_j. Как только это случится, последовательность будет продолжаться периодически, повторяя ту же самую последовательность значений от x_i до x_{j − 1}. Нахождение цикла — это задача поиска индексов i и j при заданной функции f и начальном значении x₀.

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

Задача нахождения цикла используется для проверки качества генераторов псевдослучайных чисел и криптографических хеш-функций, в алгоритмах вычислительной теории чисел, для определения бесконечных циклов в компьютерных программах и периодических конфигураций клеточных автоматов, а также для автоматического анализа формы связных списков.

Пример

Функция из множества {0,1,2,3,4,5,6,7,8} в то же множество и соответствующий функциональный граф

Рисунок показывает функцию f, отображающую множество S = {0,1,2,3,4,5,6,7,8} на себя. Если начать с точки x₀ = 2 и повторять применение функции f к получаемым значениям, увидим последовательность значений

2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....

Цикл в этой последовательности значений — 6, 3, 1.

Определения

Пусть S — конечное множество, f — некая функция, отображающая S в то же самое множество, а x_i — любой элемент из S. Для любого i > 0 пусть x_i = f(x_{i − 1}). Пусть μ — наименьший индекс, для которого значение x_μ повторяется бесконечное число раз в последовательности значений x_i, и пусть λ (длина цикла) — наименьшее положительное целое число, такое, что x_μ = x_{λ + μ}. Задача нахождения цикла — это задача поиска λ и μ.

Можно рассматривать эту задачу как задачу теории графов, если построить функциональный граф (то есть ориентированный граф, в котором каждая вершина имеет единственную исходящую дугу), вершины которого являются элементами множества S, а рёбра соответствуют отображению элементов в соответствующие значения функции, как показано на рисунке. Множество вершин, достижимых из стартовой вершины x₀ образуют подграф в форме, похожем на греческую букву ро (ρ) — путь длины μ от x₀ до цикла из λ вершин.

Представление в компьютере

Обычно f не задаётся в виде таблицы значений, как показано на рисунке выше. Скорее алгоритм определения цикла может получить на входе либо последовательность значений x_i, либо подпрограмму вычисления f. Задача состоит в нахождении λ и μ с проверкой малого числа значений последовательности, либо с обращением к процедуре вычисления значения как можно меньшее число раз. Обычно важна также ёмкостная сложность алгоритма задачи нахождения цикла: желательно использовать память, значительно меньшую по сравнению с размером последовательности целиком.

В некоторых приложениях, и, в частности, в ро-алгоритме Полларда для факторизации целых чисел, алгоритм имеет очень ограниченный доступ к S и f. В ро-алгоритме Полларда, например, S — это множество сравнимых по неизвестному простому множителю числа, который следует разложить на множители, так что даже размер множества S для алгоритма неизвестен. Чтобы алгоритм нахождения цикла работал в таких стеснённых условиях, он должен разрабатываться на основе следующих возможностей. Первоначально алгоритм имеет в памяти объект, представляющий указатель на начальное значение x₀. На любом шаге алгоритм может осуществлять одну из трёх действий: он может копировать любой указатель в любой другой объект памяти, он может вычислить значение f и заменить любой указатель на указатель на вновь образованный объект из последовательности, или использовать процедуру проверки совпадения значений, на которые указывают два указателя.

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

Алгоритмы

Если вход задан как подпрограмма вычисления f, задачу нахождения цикла можно тривиально решить, сделав только λ + μ вызовов функции просто путём вычисления последовательности значений x_i и использования структуры данных такой, как хеш-таблица, для запоминания этих значений и теста, что каждое последующее значение ещё не запомнено. Однако ёмкостная сложность данного алгоритма пропорциональна λ + μ, и эта сложность излишне велика. Кроме того, чтобы использовать этот метод для алгоритма указателей, потребуется использовать тест на равенство для каждой пары значений, что приведёт к квадратичному времени. Таким образом, исследования в этой области преследуют две цели: использовать меньше места, чем этот бесхитростный алгоритм, и найти алгоритм указателей, который использует меньше проверок на равенство.

Черепаха и заяц

Алгоритм Флойда поиска цикла «черепаха и заяц», применённый у последовательности 2, 0, 6, 3, 1, 6, 3, 1, …

Алгоритм Флойда поиска цикла — это алгоритм указателей, который использует только два указателя, которые передвигаются вдоль последовательности с разными скоростями. Алгоритм называется также алгоритмом «черепахи и зайца» с намёком на басню Эзопа «Черепаха и заяц».

Алгоритм назван именем Роберта Флойда, которому Дональд Кнут приписывает изобретение метода. Однако алгоритм не был опубликован в работах Флойда, и, возможно, это ошибка атрибуции: Флойд описывает алгоритмы для перечисления всех простых циклов в ориентированном графе в статье 1967 года, но в этой статье не описана задача нахождения цикла в функциональных графах, являющихся объектами рассмотрения статьи. Фактически утверждение Кнута, сделанное в 1969 году и приписывающее алгоритм Флойду без цитирования, является первым известным упоминанием данного алгоритма в печати, и, таким образом, алгоритм может оказаться математическим фольклором, не принадлежащим определённой личности.

Основная идея алгоритма заключается в том, что для любых целых i ≥ μ и k ≥ 0, x_i = x_{i + kλ}, где λ — длина цикла, а μ — индекс первого элемента в цикле. В частности, i = kλ ≥ μ тогда и только тогда, когда x_i = x_2i.

Таким образом, чтобы найти период ν повторения, который будет кратен λ, алгоритму нужно проверять на повторение лишь значения этого специального вида — одно значение вдвое дальше от начала, чем второе.

Как только период ν будет найден, алгоритм пересматривает последовательность с начальной точки, чтобы найти первое повторяющееся значение x_μ в последовательности, используя факт, что λ делит ν, а потому x_μ = x_{μ + v}. Наконец, как только значение μ станет известно, легко найти длину λ кратчайшего цикла повторения путём нахождения первой позиции μ + λ, для которой x_{μ + λ} = x_μ.

Алгоритм использует два указателя в заданной последовательности: один (черепаха) идёт по значениям x_i, а другой (заяц) по значениям x_2i. На каждом шаге алгоритма индекс i увеличивается на единицу, передвигая черепаху на один элемент вперёд, а зайца — на два элемента, после чего значения в этих точках сравниваются. Наименьшее значение i > 0, для которого черепаха и заяц будут указывать на одинаковые значения, является искомым значением ν.

Следующая программа на языке Python показывает, каким образом идея может быть реализована.

def floyd(f, x0):
    # Основная часть алгоритма: находим повторение x_i = x_2i.
    # Заяц движется вдвое быстрее черепахи,
    # и расстояние между ними увеличивается на единицу от шага к шагу.
    # Однажды они окажутся внутри цикла, и тогда расстояние между ними
    # будет делиться на λ.
    tortoise = f(x0) # f(x0) является элементом, следующим за x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
  
    # В этот момент позиция черепахи ν, 
    # которая равна расстоянию между черепахой и зайцем,
    # делится на период λ. Таким образом, заяц, двигаясь 
    # по кольцу на одну позицию за один раз, 
    # и черепаха, опять начавшая движение со стартовой точки x0 и
    # приближающаяся к кольцу, встретятся в начале кольца
    # Находим позицию μ встречи.    
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Заяц и черепаха двигаются с одинаковой скоростью
        mu += 1
 
    # Находим длину кратчайшего цикла, начинающегося с позиции x_μ
    # Заяц движется на одну позицию вперёд, 
    # в то время как черепаха стоит на месте.
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, mu

Данный код получает доступ к последовательности лишь запоминанием и копированием указателей, вычислением функции и проверкой равенства. Таким образом, алгоритм является алгоритмом указателей. Алгоритм использует O(λ + μ) операций этих типов и O(1) памяти .

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

Ричард Брент описал альтернативный алгоритм нахождения цикла, которому, подобно алгоритму черепахи и зайца, требуется лишь два указателя на последовательность . Однако он основан на другом принципе — поиске наименьшей степени 2ⁱ числа 2, которая больше как λ, так и μ.

Для i = 0, 1, 2, ..., алгоритм сравнивает x_2ⁱ−1 со значениями последовательности вплоть до следующей степени двух, останавливая процесс, когда найдётся совпадение. Алгоритм имеет два преимущества по сравнению с алгоритмом черепахи и зайца: во-первых, он находит правильную длину λ цикла сразу и не требуется второй шаг для её определения, а во-вторых, на каждом шаге вызов функции f происходит только один раз, а не три раза .

Следующая программа на языке Python более детально показывает, как эта техника работает.

def brent(f, x0):
    # Основная фаза: ищем степень двойки
    power = lam = 1
    tortoise = x0
    hare = f(x0)  # f(x0) — элемент/узел, следующий за x0.
    while tortoise != hare:
        if power == lam:  # время начать новую степень двойки?
            tortoise = hare
            power *= 2
            lam = 0
        hare = f(hare)
        lam += 1

    # Находим позицию первого повторения длины λ
    mu = 0
    tortoise = hare = x0
    for i in range(lam):
    # range(lam) образует список со значениями 0, 1, ... , lam-1
        hare = f(hare)
    # расстояние между черепахой и зайцем теперь равно λ.

    # Теперь черепаха и заяц движутся с одинаковой скоростью, пока не встретятся
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
 
    return lam, mu

Подобно алгоритму черепахи и зайца, этот алгоритм является алгоритмом указателей, использующим O(λ + μ) проверок и вызовов функций и памяти O(1). Несложно показать, что число вызовов функции никогда не превзойдёт числа вызовов в алгоритме Флойда.

Брент утверждает, что в среднем его алгоритм работает примерно на 36 % быстрее алгоритма Флойда, и что он обгоняет ро-алгоритм Полларда примерно на 24 %. Он осуществил анализ среднего варианта вероятностной версии алгоритма, в котором последовательность индексов, проходимых медленным указателем, не является степенью двойки, а является степенью двойки, умноженной на случайный коэффициент. Хотя основной целью его алгоритма была разложение числа на множители, Брент также обсуждает приложение алгоритма для проверки псевдослучайных генераторов.

Время в обмен на память

Много авторов изучали техники для нахождения цикла, использующих большее количество памяти, чем у методов Флойда и Брента, но, зато, работающих быстрее. В общем случае эти методы запоминают некоторые ранее вычисленные значения последовательности и проверяют, не совпадает ли новое значение с одним из запомненных. Чтобы делать это быстро, обычно они используют хеш-таблицы или подобные структуры данных, а потому такие алгоритмы не являются алгоритмами указателей (в частности, обычно их нельзя приспособить к ро-алгоритму Полларда). Чем эти методы отличаются, так это способом определения, какие значения запоминать. Следуя Нивашу, мы кратко рассмотрим эти техники.

Брент уже описывал вариации своей техники, в которых индексы запомненных значений последовательности являются степенями числа R, отличного от двух. При выборе R ближе к единице и, запоминая значения последовательности с индексами, близкими к последовательным степеням R, алгоритм нахождения цикла может использовать число вызовов функции, которое не превосходит произвольно малого множителя оптимального значения λ + μ.

Седжвик, Шиманьский и Яо предложили метод, который использует M ячеек памяти и требует в худшем случае только $(\lambda +\mu )(1+cM^{-1/2})$ вызовов функции с некоторой постоянной c, для которой она показала оптимальность. Техника использует числовой параметр d, запоминая в таблице только те позиции последовательности, которые кратны d. Таблица очищается, а значение d удваивается, если число запомненных значений слишком велико.

Некоторые авторы описали методы отмеченных точек, которые запоминают в таблице значения функции, опираясь на критерии, использующие значения, а не индексы (как в методе Седжвика и др.). Например, могут запоминаться значения по модулю от некоторого числа d. Более просто, Ниваш приписывает Вудруфу предложение запоминать случайно выбранное предыдущее значение, делая подходящий случайный выбор на каждом шаге.

Ниваш описывает алгоритм, который не использует фиксированного количества памяти, но для которого ожидаемое количество используемой памяти (в предположении, что входная функция случайна) логарифмически зависит от длины последовательности. По этой технике элемент записывается в таблицу, если никакой предыдущий элемент не имеет меньшего значения. Как показал Ниваш, элементы в этой технике можно располагать в стеке, и каждое последующее значение нужно сравнивать только с элементом на вершине стека. Алгоритм прекращает работу, когда повторение элемента с меньшим значением найдено. Если использовать несколько стеков и случайную перестановку значений внутри каждого стека, получаем выигрыш в скорости за счёт памяти аналогично предыдущим алгоритмам. Однако даже версия алгоритма с одним стеком не является алгоритмом указателей, поскольку требуется знать, какое из значений меньше.

Любой алгоритм нахождения цикла, запоминающий максимум M значений из входной последовательности, должен сделать по меньшей мере $(\lambda +\mu )(1+{\frac {1}{M-1}})$ вызовов функций.

Приложения

Нахождение цикла используется во многих приложениях.

Определение длины цикла генератора псевдослучайных чисел является одной из мер его силы. Об этом приложении говорил Кнут при описании метода Флойда. Брент описал результат тестирования линейного конгруэнтного генератора. Период генератора оказался существенно меньше афишированного. Для более сложных генераторов последовательность значений, в которых находят цикл, может не представлять вывод генератора, а лишь его внутреннее состояние.

Некоторые алгоритмы теории чисел опираются на нахождение цикла, включая ро-алгоритм Полларда для факторизации целых чисел и связанный с ним алгоритм «кенгуру» для задачи дискретного логарифмирования.

В криптографии возможность найти два различных значения x_μ−1 и x_λ+μ−1, отображающихся некоторой криптографической функцией ƒ в одно и то же значение x_μ, может говорить о слабости ƒ. Например, Кискатр и Делессаилле применили алгоритмы нахождения цикла для поиска сообщения и пары ключей DES, которые отображают это сообщение в одно и то же зашифрованное значение. Калиски, Ривест и Шерман также использовали алгоритмы нахождения цикла для атаки на DES. Техника может быть использована для поиска коллизий в криптографической хеш-функции.

Нахождение циклов может быть полезно как путь обнаружения бесконечных циклов в некоторых типах компьютерных программ.

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

Анализ формы связных списков является техникой проверки корректности алгоритма, использующего эти структуры. Если узел в списке ссылается некорректно на более ранний узел в том же списке, структура образует цикл, который может быть найден с помощью таких алгоритмов. В языке Common Lisp принтер S-выражений при переменной *print-circle* обнаруживает зацикленные списковые структуры и печатает их компактно.

Теске описывает приложение в вычислительной теории групп для вычисления структуры абелевой группы по множеству её генераторов. Криптографические алгоритмы Калиски и др. можно рассматривать также как попытку раскрыть структуру неизвестной группы.

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

Литература

• Allender, Eric W.; Klawe, Maria M.  Improved lower bounds for the cycle detection problem // Theoretical Computer Science. — 1985. — Vol. 36, no. 2–3. — doi:10.1016/0304-3975(85)90044-1. — P. 231—237.
• Auguston, Mikhail; Hon, Miu Har. . Assertions for Dynamic Shape Analysis of List Data Structures // AADEBUG '97, Proceedings of the Third International Workshop on Automatic Debugging. — Linköping University, 1997. — (Linköping Electronic Articles in Computer and Information Science). — P. 37—42.
• Aumasson, Jean-Philippe; Meier, Willi; Phan, Raphael C.-W.; Henzen, Luca. . The Hash Function BLAKE. — Heidelberg, New York, Dordrecht, London: Springer, 2015. — (Information security and Cryptography). — ISBN 978-3-662-44756-7.
• Brent R. P.  An improved Monte Carlo factorization algorithm // BIT Numerical Mathematics. — 1980. — Vol. 20, no. 2. — P. 176—184. — doi:10.1007/BF01933190.
• Fich, Faith Ellen. . Lower bounds for the cycle detection problem // Proc. 13th ACM Symposium on Theory of Computing. — 1981. — doi:10.1145/800076.802462. — P. 96—105.
• Floyd R. W.  Non-deterministic Algorithms // Journal of ACM. — 1967. — Vol. 14, no. 4. — P. 636—644. — doi:10.1145/321420.321422.
• Joux, Antoine. . Algorithmic Cryptanalysis. — CRC Press, 2009. — P. 223. — ISBN 9781420070033.
• Kaliski, Burton S. Jr.; Rivest, Ronald L.; Sherman Alan T.  Is the Data Encryption Standard a group? (Results of cycling experiments on DES) // Journal of Cryptology. — 1988. — Vol. 1, no. 1. — P. 3—36. — doi:10.1007/BF00206323.
• Knuth, Donald E. . The Art of Computer Programming, vol. II: Seminumerical Algorithms. — Addison-Wesley, 1969. — P. 7, exercises 6 and 7.
  • Русский перевод: Кнут Д. Э. . Искусство программирования. 3-е изд. Т. 2. Получисленные алгоритмы. — Вильямс, 2005. — ISBN 5-8459-0081-6.
• Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. . Handbook of Applied Cryptography. — CRC Press, 1996. — ISBN 0-8493-8523-7.
• Nivasch, Gabriel.  Cycle detection using a stack // Information Processing Letters. — 2004. — Vol. 90, no. 3. — P. 135—140. — doi:10.1016/j.ipl.2004.01.016.
• Pollard J. M.  A Monte Carlo method for factorization // BIT. — 1975. — Vol. 15, no. 3. — P. 331—334. — doi:10.1007/BF01933667.
• Pollard J. M.  Monte Carlo methods for index computation (mod p) // Mathematics of Computation. — American Mathematical Society, 1978. — Vol. 32, no. 143. — P. 918—924. — doi:10.2307/2006496. — .
• Quisquater J.-J., Delescaille J.-P. . How easy is collision search? Application to DES // Advances in Cryptology — EUROCRYPT '89, Workshop on the Theory and Application of Cryptographic Techniques. — Springer-Verlag, 1989. — P. 429—434. — (Lecture Notes in Computer Science, vol. 434). (недоступная ссылка)
• Schnorr, Claus P.; Lenstra, Hendrik W.  A Monte Carlo factoring algorithm with linear storage // Mathematics of Computation. — 1984. — Vol. 43, no. 167. — P. 289—311. — doi:10.2307/2007414. — .
• Sedgewick, Robert; Szymanski, Thomas G.; Yao, Andrew C.-C.  The complexity of finding cycles in periodic functions // SIAM Journal on Computing. — 1982. — Vol. 11, no. 2. — P. 376—390. — doi:10.1137/0211030.
• Teske, Edlyn.  A space-efficient algorithm for group structure computation // Mathematics of Computation. — 1998. — Vol. 67, no. 224. — P. 1637—1663. — doi:10.1090/S0025-5718-98-00968-5.
• Van Gelder, Allen.  Efficient loop detection in Prolog using the tortoise-and-hare technique // Journal of Logic Programming. — 1987. — Vol. 4, no. 1. — P. 23—31. — doi:10.1016/0743-1066(87)90020-3.
• van Oorschot, Paul C.; Wiener, Michael J.  Parallel collision search with cryptanalytic applications // Journal of Cryptology. — 1999. — Vol. 12, no. 1. — P. 1—28. — doi:10.1007/PL00003816.

Ссылки

• Gabriel Nivasch, Задача нахождения цикла и стековый алгоритм
• Черепаха и заяц, Portland Pattern Repository
• Floyd’s Задача нахождения цикла (Черепаха и заяц)
• Brent’s Задача нахождения цикла (Черепаха и заяц)