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