2
$\begingroup$

I would like to find cycles in a finite length list of numbers where there is no function:

xn = f(xn-1).

For example, in the list:

3, 12, 11, 46, 1034, 23, 12, 11, 46, 1034, 5

x0 = 3, x1 = 12, etc. and the cycle starts at x1 with a length of 4.

There is a Java implementation of Brent's Cycle Algorithm here which includes some sample data with the expected output.

Brent Cycle Algorithm Test

Enter size of list
9

Enter f(x)
6 6 0 1 4 3 3 4 2

Enter x0
8

First 9 elements in sequence :
8 2 0 6 3 1 6 3 1 6

Length of cycle : 3
Position : 4

Here you can see that x0 = 8 and that the 8th entry in the entered list is 2 (using a zero based index), which when used as an index gives 0, which when used as an index gives 6 and so on producing the first 9 elements in the sequence 8, 2, 0, 6, etc.

My problem (likely due to my lack of understanding about the purpose or use of Brent's Algorithm) is that the numbers in the list I provided (3, 12, 11, 46, etc.) cannot be used as indexes (indicies?) to access the next number in the list. In other words, there is no f(x) such that xn = f(xn-1).

Does this put Brent's Algorithm out of reach for my application? Maybe there's a simple modification to Brent's Algorithm that hasn't occurred to me.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ In that case you don't necessarily have a cycle, right? So an adaptation of the algorithm may not terminate. $\endgroup$
    – md5
    Jun 23, 2017 at 19:45
  • $\begingroup$ @md5 "In that case you don't necessarily have a cycle, right?" That depends on the definition of a cycle, and there, I am uninformed. The data in my example has a cycle: it is 12, 11, 46, 1034 (which repeats once). Does this constitute a cycle in the Brent's Cycle Algorithm sense? Or must my data be representable by a function f(x) such that x sub n = f(x sub n-1) in order to constitute a cycle in the Brent's Cycle Algorithm sense? $\endgroup$
    – mbmast
    Jun 23, 2017 at 20:26
  • 1
    $\begingroup$ A cycle is a sequence that keeps repeating forever and can only exist in an infinite sequence. For example, 1/x contains a cycle in its decimal expansion for every x. $\endgroup$
    – Albert Hendriks
    Jul 24, 2017 at 4:34

1 Answer 1

Reset to default
2
$\begingroup$

If the numbers in the list are stored in memory as a list, you can just use a hashtable to look for duplicates, or you can sort them and then look for duplicates.

Brent's algorithm is primarily useful in situations where you don't want to store all of the numbers in memory, because the memory cost would be too high -- but that doesn't apply if you have a list with the numbers, because then you're already committed to storing all the numbers in memory.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.