2 ms·
Prompted by a recent submission[0], this post talks about both the original Floyd algorithm[1] as well as the Brent optimisation[2]. It also mentions the appli
by ColinWright 13y ago
Prompted by a recent submission[0], this post talks about both the original Floyd algorithm[1] as well as the Brent optimisation[2]. It also mentions the applicability beyond the explicit linked list, in applications such as integer factoring (Pollard Rho[3]).
[0] https://news.ycombinator.com/item?id=6946779 https://news.ycombinator.com/item?id=6946779
[1] http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_ha...
[2] http://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algorithm http://en.wikipedia.org/wiki/Cycle_detection#Brent.27s_algor...
[3] http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm