3 ms·
There is a lesser known variation of "find a cycle in a linked list". Given a function int f(int arg); that returns a value computed solely from arg, find t
by huhtenberg 16y ago
There is a lesser known variation of "find a cycle in a linked list". Given a function
int f(int arg);
that returns a value computed solely from arg, find the length of the repeating sequence in
f(x), f(f(x)), f(f(f(x))), ...
The primary use is determining the period of a state-less PRNG such as a linear congruential one.
- psykotic 16y ago> There is a lesser known variation of "find a cycle in a linked list" There's also a lesser known alternative to Floyd's tortoise-and-hare algorithm called Brent's algorithm. It's a little faster in practice, but more importantly it represents an algorithm design technique that everyone should know.
- RiderOfGiraffes 16y agoSee http://news.ycombinator.com/item?id=1068715 http://news.ycombinator.com/item?id=1068715 for a lot of discussion on this.