> Linus noted that it's possible to fuck up the algorithm for
> for detecting loops by changing the world under it.
No, I noted it. To attribute correctly, vermont@gate.net pointed out the
problem to me, before I had thought about it.
> A more efficient, and somewhat simpler to implement, IMHO,
> technique was developed by Richard Brent. It consists of:
[...]
> This does a signle traversal of the list, but "halts" a comparison
> point at each power-of-two step. If you ever come back to the
> comparison pointer, you have a loop.
This obviously doesn't work.
(a->b->c->d->c... for example)
--Scott
@ @
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-oOO-(_)-OOo-=-=-=-=-=
C. Scott Ananian: cananian@lcs.mit.edu / Declare the Truth boldly and
Laboratory for Computer Science/Crypto / without hindrance.
Massachusetts Institute of Technology /META-PARRESIAS AKOLUTOS:Acts 28:31
-.-. .-.. .. ..-. ..-. --- .-. -.. ... -.-. --- - - .- -. .- -. .. .- -.
PGP key available via finger and from http://www.pdos.lcs.mit.edu/~cananian
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu