Algorithm-Ish 001: Cycle Detection & Brent’s Algorithm
Warning: I am by no means an expert in computer science or related disciplines covered in these posts. But I do think this stuff is cool, and I am going to try to write about it anyways.
Quick! Throw this on to get yourself in the mood for this post:
Good — now that Mr. Vandross is flowing through the veins, let’s talk about cycles. A cycle consists of repeating values within a sequence of numbers generated by a function that maps a finite set to itself (see below, definition courtesy of Wikipedia):
So, every value in the sequence is based upon the value prior, transformed by some type of mapping function. The catch is that when this gets applied to a finite set, and given a starting value (x.0), the function will eventually fall into a repeating sequence (aka a cycle). Cycle detection is all about identifying how far into a sequence (from the initial starting value), Mu, it takes to fall into that repetition, and how long that repeating sequence is, Lambda.
Luckily, some sharp people have done the heavy lifting to formulate approaches to detecting cycles. Robert W. Floyd’s solution, the ‘Tortoise and Hare algorithm,’ is a popular tactic for finding cycles — though some historical evidence suggests that it is a folk theorem, as Floyd never formally published the algorithm itself (scandalous). Another approach is that of Richard P. Brent. Brent’s algorithm employs an exponential search to step through the sequence — this allows for the calculation of cycle length in one stage (as opposed to Floyd’s, where a subsequent stage is needed to identify length) and only requires the evaluation of the function once per step (whereas Floyd’s involves three per). Below is a Python implementation of Brent’s algorithm (credit to Wikipedia again), which I put to use later on.
def brent(f, x0):
# main phase: search successive powers of two
power = lam = 1
tortoise = x0
hare = f(x0) # f(x0) is the element/node next to x0.
while tortoise != hare:
if power == lam: # time to start a new power of two?
tortoise = hare
power *= 2
lam = 0
hare = f(hare)
lam += 1
# Find the position of the first repetition of length λ
tortoise = hare = x0
for i in range(lam):
# range(lam) produces a list with the values 0, 1, ... , lam-1
hare = f(hare)
# The distance between the hare and tortoise is now λ.
# Next, the hare and tortoise move at same speed until they agree
mu = 0
while tortoise != hare:
tortoise = f(tortoise)
hare = f(hare)
mu += 1
return lam, muOk, so what does this look like in practice? I used a couple helper functions: one generates a random set of unique integers, given a range of possible numbers and a desired set size (credit to this Stack Overflow thread). The other is a ‘mapper’ method to generate a random mapping function based on a finite set.
#generate random unique list of sampleSize nums from posNums range
def genSet(posNums, sampleSize):
answer = []
answerSize = 0
while answerSize < sampleSize:
r = random.randint(0, posNums)
if r not in answer:
answerSize += 1
answer.append(r)
return answer#assumes nums is a set of unique values, returns mapped function
def mapper(nums):
fn = {}
for key in nums:
fn[key] = nums[random.randint(0,len(nums)-1)]
return fn
For example, running the genSet function with the inputs of posNums = 100, sampleSize = 10 will produce a set of 10 unique values taken from the range of 0–99. Running the mapper function on that random set will produce a dictionary mapping, such as the following:
numSet = genSet(posNums, sampleSize)
fn = mapper(numSet)
print('Set:', numSet)
print('Function:', fn)Set: [57, 65, 16, 25, 80, 90, 62, 76, 47, 77]Function: {57: 47, 65: 80, 16: 62, 25: 25, 80: 65, 90: 90, 62: 80, 76: 90, 47: 77, 77: 47}
Now with the set and function generators in place, we can see Brent’s algorithm in action. Let’s create a new random set and mapping function of 10 values taken from 0–99. Additionally, choose a random value from the generated set as the starting point of the sequence (x.0). Finally, run the Brent algorithm with the function and x.0 as inputs. This will produce the following:
x0 = numSet[random.randint(0,len(numSet)-1)]
print('Start-x0:',x0)
print(brenter(fn, x0)) #named the function brenter for no reasonSet: [50, 94, 44, 49, 98, 47, 55, 64, 8, 25]
Function: {50: 44, 94: 44, 44: 94, 49: 55, 98: 44, 47: 64, 55: 44, 64: 94, 8: 50, 25: 64}
Start-x0: 49
(2, 2) #These are the Lambda, Mu values of the detected cycle
Step through the above: the random start point was 49. Looking at the function, f(49) = 55, so 55 will be the next value in the sequence. We can easily identify the next sequence values by eyeballing the function map: 49, 55, 44, 94, 44, 94, 44,94…and there it is. We have fallen into a cycle, repeating the values 44 and 94 indefinitely! Note the first value of Brent’s algorithm output, 2. This is equal to Lambda, or the length of the cycle — checks out! The second value is Mu, which is the starting index of the detected cycle, starting from the random point x.0. Remember that index values start at 0, meaning 55 would be at index 1 and 44 lands at index 2 — which, as we know, is the value that kicks off the infinite cycle. Alas, Brent’s algorithm is working as intended.
What does it look like if we extend Brent’s algorithm to larger sequences? Can we identify larger-scale cycles? I wrote the following script to randomly generate a number of sets, functions, and starting indexes, then pull out the largest identified cycle length and sequence. Using the networkx library, we can generate some basic visualizations of these graphs as well.
import networkx as nx
import matplotlib.pyplot as plt
import random
from brent import brenter
from randGen import genSet, mapperposNums = 100
sampleSize = 10
numIters = 30lrg_lam = 0
lrg_mu = 0
lrg_fn = {}
lrg_x0 = 0
for i in range(numIters):
numSet = genSet(posNums, sampleSize)
fn = mapper(numSet)
x0 = numSet[random.randint(0,len(numSet)-1)]
lam, mu = brenter(fn, x0)
if lam > lrg_lam:
lrg_lam = lam
lrg_fn = fn
lrg_x0 = x0
lrg_mu = mu
print('Function Map f(x):',lrg_fn)
print('Random Start Value (x.0):',lrg_x0)
print('Cycle Length (Lambda):',lrg_lam)
print('Start Index of Cycle (Mu):',lrg_mu)cycle = [] #print largest cycle
for z in range((lrg_lam+lrg_mu)+1):
if z >= lrg_mu:
cycle.append(lrg_x0)
lrg_x0 = lrg_fn[lrg_x0]
print('Cycle:', cycle)#create graph
plt.figure(figsize=(20,20))
G = nx.Graph()
#add list of nodes to graph
G.add_nodes_from(list(lrg_fn.keys()))
G.add_edges_from(list(lrg_fn.items()))
nx.draw(G, with_labels=True, font_size=10)
plt.savefig('plot_path.png')
So, once again taking samples of 10 values from the range 0–99, 30 times, resulted in a largest cycle of length 7:
Function Map f(x): {43: 64, 73: 71, 13: 85, 90: 71, 64: 90, 71: 13, 29: 29, 37: 43, 40: 64, 85: 37}
Random Start Value (x.0): 64
Cycle Length (Lambda): 7
Start Index of Cycle (Mu): 0
Cycle: [64, 90, 71, 13, 85, 37, 43, 64]
In that example, we pulled a x.0 that happened to land at the start of the cycle itself, making Mu equal to 0. It is also easy to visualize how other start values, such as 73 or 40, would lead into the cycle with a Mu of 1 as opposed to 0.
What if we increase sampleSize by a factor of 10 (holding possible values and number of iterations constant at 0–99 and 30, respectively), so that we are generating a sequence from a set of 100 values?
Function Map f(x): {68: 18, 2: 91, 93: 89, 54: 8, 6: 48, 11: 44, 41: 23, 76: 70, 67: 40, 66: 75, 46: 79, 0: 72, 19: 31, 85: 38, 60: 82, 100: 71, 45: 61, 94: 50, 92: 5, 98: 52, 86: 64, 20: 84, 59: 77, 29: 38, 32: 25, 25: 16, 12: 34, 99: 72, 1: 85, 88: 87, 26: 34, 74: 45, 53: 32, 40: 55, 18: 0, 96: 9, 35: 8, 58: 7, 63: 85, 13: 14, 56: 11, 52: 50, 34: 46, 95: 85, 42: 7, 57: 20, 90: 63, 89: 50, 4: 37, 70: 7, 62: 93, 80: 21, 83: 81, 3: 87, 21: 92, 5: 20, 87: 47, 47: 85, 82: 45, 43: 64, 65: 89, 49: 6, 31: 4, 73: 6, 77: 94, 84: 50, 8: 31, 78: 68, 55: 21, 30: 23, 17: 11, 48: 86, 28: 72, 33: 68, 15: 76, 81: 94, 16: 14, 72: 21, 97: 31, 51: 23, 24: 54, 69: 89, 14: 2, 44: 40, 22: 35, 10: 11, 91: 19, 64: 47, 71: 14, 61: 60, 9: 71, 23: 39, 50: 12, 27: 32, 7: 11, 37: 58, 39: 15, 38: 1, 75: 0, 79: 51}
Random Start Value (x.0): 52
Cycle Length (Lambda): 21
Start Index of Cycle (Mu): 1
Cycle: [50, 12, 34, 46, 79, 51, 23, 39, 15, 76, 70, 7, 11, 44, 40, 55, 21, 92, 5, 20, 84, 50]
As you can see, the cycle length increased significantly to 21, and our ability to identify that cycle by eyeing the pattern or evaluating the function by hand is severely limited as the complexity of the problem grows. I added some identifiers to the above graph to show a rough idea of the cycle’s flow.
Finally, for the fun of it, let’s generate a set with a sample size of 1,000, taking from a possible number range of 0–1,000, and iterating 30 times to find the largest possible cycle. I’ll spare your eyes from having to look at the function mapping:
Random Start Value (x.0): 608
Cycle Length (Lambda): 55
Start Index of Cycle (Mu): 2
Cycle: [242, 688, 275, 13, 67, 959, 485, 928, 318, 860, 537, 703, 86, 183, 707, 295, 938, 660, 324, 122, 161, 547, 821, 767, 490, 140, 256, 395, 216, 730, 736, 870, 368, 468, 306, 704, 309, 763, 373, 456, 412, 326, 68, 23, 495, 906, 837, 55, 811, 239, 471, 351, 782, 623, 88, 242]
This time Brent’s algorithm was able to identify a cycle of 55 values. This is where the value of cycle detection really starts to show. Manual detection of a 55-long cycle within a sequence would be quite burdensome, even in this case where the cycle happened to start only 3 values in from the initial index value. It is not hard to imagine the difficulty that could arise as larger and larger sample sizes are introduced, as is the case in real-world applications. This is where the benefits of Brent’s and other cycle detection algorithms shine through! Instead of toiling for hours and going through detection by hand, Brent’s algorithm offers a seamless, efficient solution to identify cycles in a fraction of the time.
Applications of cycle detection come about in the fields of cryptography, celestial mechanics, and cellular automation simulations, among others. For further information, check out Floyd’s algorithm, as well as the work of R. W. Gosper, Nivasch, and Sedgewick, Szymanski, and Yao.
I hope this was informative in one way or another — if you would like to check out the code used for the project, head over to the Algorithm-Ish Github.
