Can someone please point me to a book or paper that describes the Tortoise and Hare algorithm by Floyd?
I know there are ample websites out there, but for reference purposes, I need a book or paper to point to.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Did you have a look at the references mentioned on Wikipedia? $\endgroup$– SEJPMJul 24, 2018 at 11:38
-
$\begingroup$ I don't want wikipedia. I want a book, or paper. Because you can put as reference the wikipedia. $\endgroup$– Mr. Zacarias SatrusteguiJul 24, 2018 at 11:45
-
2$\begingroup$ I'm not suggesting you reference Wikipedia. I'm suggesting you go through the references mentioned on Wikipedia and if they have what you want, you put these books and papers as your references. $\endgroup$– SEJPMJul 24, 2018 at 11:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Quoting Wikipedia:
The algorithm is named after Robert W. Floyd, who was credited with its invention by Donald Knuth.3[4] However, the algorithm does not appear in Floyd's published work, and this may be a misattribution: Floyd describes algorithms for listing all simple cycles in a directed graph in a 1967 paper,[5] but this paper does not describe the cycle-finding problem in functional graphs that is the subject of this article. In fact, Knuth's statement (in 1969), attributing it to Floyd, without citation, is the first known appearance in print, and it thus may be a folk theorem, not attributable to a single individual.[6]
Now looking up reference [4], yields the Handbook of Applied Cryptography, which indeed contains a description as Note 3.8 (PDF version). However the Handbook also attributes the algorithm to Knuth as Wikipedia does, so
Knuth, Donald E. (1969), The Art of Computer Programming, vol. II: Seminumerical Algorithms, Addison-Wesley, p. 7, exercise 6
is the reference you are looking for with the Handbook citing it as (PDF, reference 692)
D.E.Knuth , The Art of Computer Programming – Seminumerical Algorithms, volume 2, Addison-Wesley, Reading, Massachusetts, 2nd edition, 1981
