CODEWITHSUNDEEP
c++
deha
deha

Reputation: 815

Find period in very large sequence of numbers

Is there any possibility to find a cycle length in very large portion of numbers (more than maximum value of bigest integer type in C/C++, let's say 2^20), without involving disk to perform it? The best situation would be to analyze them sequentially, as they arrive from standard input, but I'm pretty sure that is impossible and I need to store them in memory. But I hope I'm wrong. Numbers values are integers, they are coming from standard input.

Example: Input: ( 1 2 3 ... (2^20 triples of 1 2 3) ... 1 2 3) Desired result: 3

EDIT

let's think of cycle as a period (f(x) = f(x+t) for some t) - looking for value of t

let's assume that operating memory is too few to store all numbers (numbers can be more than 2^20) and might be gmp types.

Upvotes: 0

Views: 3263

Answers (2)

Soverman
Soverman

Reputation: 1135

This is a well-studied problem, with quite a number of algorithms depending on what exactly your resources and contraints are:

http://en.wikipedia.org/wiki/Cycle_detection

You do not need to store everything in memory (just two pointers/indices in the basic algorithms), but you need to be able to access the sequence multiple times.

See also:

Floyd's cycle-finding algorithm

Upvotes: 2

Ivan Vergiliev
Ivan Vergiliev

Reputation: 3841

The standard way to find the period length is to imagine your sequence is a string S over an alphabet of integers, and then find the leftmost position (greater than 0) where S can be found in the string SS (the concatenation of the string S with itself). That is, if S = 'abcabc', you have to find the first position i greater than zero, such that S is found at position i in the string SS = 'abcabcabcabc'. In this case, this is 3, and that's the length of the period.

This can be done any of the string searching algorithms with linear performance, and should work perfectly fine for 2^20 numbers on a modern computer. I doubt that you can avoid saving the numbers in memory though.

Upvotes: 1

Related Questions