AirlineDog/cycle-detection

cycle-detection

If we have a sequence of numbers produced by a function, how can we know that the generated values are not repeated? Or, if reoccurring, when does this start happening?

This repo implements the algorithms described in the article below:

Sedgewick, Robert, Thomas G. Szymanski, and Andrew C. Yao. 1982. “The Complexity of Finding Cycles in Periodic Functions.” SIAM Journal on Computing 11 (2): 376– 90. https://doi.org/10.1137/0211030.

cycle-detection/cycle_detection.py

Lines 31 to 48 in 0d117aa

    
           def detect_cycle(x, f, b, g, max_size): 
        
               y = x 
        
               i = 0 
        
               m = 0 
        
               while True: 
        
                   if i % b == 0 and m == max_size: 
        
                       b *= 2 
        
                       purge(table, b) 
        
                       m = math.floor(m / 2) 
        
                   if i % b == 0: 
        
                       table.append((y, i)) 
        
                       m += 1 
        
                   y = f(y) 
        
                   i += 1 
        
                   if (i % (b*g)) < b: 
        
                       j = search_table_y(table, y) 
        
                       if j != -1: 
        
                           return y, i, j, b

The basic idea behind this algorithm is that instead of examining all values of the sequence, we only examine b values, which are within gb of each other, where b, g are parameters that we have to choose. Those values are stored in a table containing pairs (y, j), where y is a value of the sequence and j the order we found it. For every y the table can have more than one corresponding j.

The algorithm stores values in the table in order not to recalculate them. If a sequence is too long this can result in a very big table. To avoid that we put a max_size limit to the table. When the table is full we purge all pairs that j mod 2b != 0 and we double the parameter b

The next step is to find where this cycle is starting, that is the leader, and how long the cycle is.

cycle-detection/cycle_detection.py

Lines 51 to 71 in 0d117aa

    
           def recover_cycle(f, y, i, j): 
        
               c = 1 
        
               found_c = False 
        
               y_c = y 
        
               while c <= (g + 1) * b and not found_c: 
        
                   y_c = f(y_c) 
        
                   if y == y_c: 
        
                       found_c = True 
        
                   else: 
        
                       c += 1 
        
               if not found_c: 
        
                   c = i - j 
        
               block_length = g * b 
        
               final_block = block_length * math.floor(i / block_length) 
        
               previous_block = final_block - block_length 
        
               ii = max(c, previous_block) 
        
               jj = ii - c 
        
               leader = jj + 1 
        
               while find_f_to_the_nth(leader) != find_f_to_the_nth(leader + c): 
        
                   leader += 1 
        
               return leader, c

In order to calculate the kth element of the sequence without recalculating all the sequence again and again we use the above table. Specifically, the value b * ⌊k / b⌋ is the closest value that have been stored in the table. So, we only need to find the pair with j = b * ⌊k / b⌋. If kb is the first element of this pair, we then apply k mod b times the function f to kb

	def detect_cycle(x, f, b, g, max_size):
	y = x
	i = 0
	m = 0
	while True:
	if i % b == 0 and m == max_size:
	b *= 2
	purge(table, b)
	m = math.floor(m / 2)
	if i % b == 0:
	table.append((y, i))
	m += 1
	y = f(y)
	i += 1
	if (i % (b*g)) < b:
	j = search_table_y(table, y)
	if j != -1:
	return y, i, j, b

	def recover_cycle(f, y, i, j):
	c = 1
	found_c = False
	y_c = y
	while c <= (g + 1) * b and not found_c:
	y_c = f(y_c)
	if y == y_c:
	found_c = True
	else:
	c += 1
	if not found_c:
	c = i - j
	block_length = g * b
	final_block = block_length * math.floor(i / block_length)
	previous_block = final_block - block_length
	ii = max(c, previous_block)
	jj = ii - c
	leader = jj + 1
	while find_f_to_the_nth(leader) != find_f_to_the_nth(leader + c):
	leader += 1
	return leader, c