4 ms·
Actually it seems you are right on both accounts. In the first case the hair would not actually jump over the turtle except for the very beginning. It is funny
by hristov 17y ago
Actually it seems you are right on both accounts. In the first case the hair would not actually jump over the turtle except for the very beginning. It is funny how that works, it is rather counter intuitive.
And in the second case, I think in the worst case scenario the optimization performs the same number of link followings as the original algorithm. That is because the original algorithm performs duplicative work as the turtle has to follow the same links the hare did.
But of course if following a link was that expensive, one would modify the original algorithm to save all the links that the hare traversed so that one does not have to pay for the turtle to follow them. This will result in the original algorithm being faster in certain circumstances than the optimisation (although it may use a bit more memory).
Well anyways I was wrong at the top, I am sorry if I offended anyone by stating that they had bugs in their pseudocode. I should not argue with stuff that has been obviously academically developed and argued and double checked to death before i have seen it.
- barrkel 17y agoIn terms of saving the links, I think it's not necessarily the wisest course for scenarios like PRNGs etc., where that may mean saving millions or billions of intermediate number results. The TH algorithm is Floyd's algorithm, while the TT algorithm is Brent's algorithm in the Wikipedia cycle detection link.