4 ms·

To say, "now on every clock tick we only take one step, not three," seems to imply that the optimized version takes 1/3 as many steps. The mammal still doesn't

To say, "now on every clock tick we only take one step, not three," seems to imply that the optimized version takes 1/3 as many steps. The mammal still doesn't catch the reptile without doing two full laps while the reptile does one. For an n-entry loop: The original version has the tortoise take n steps and the hare take 2n steps. The optimized version has the rabbit take 2n steps and the turtle take lg(n) steps. For an n-entry line: The original version has the tortoise take n/2 steps and the hare take n steps. The optimized version has the rabbit take n steps and the turtle take lg(n) steps. Or did I misread the algorithm?

barrkel 17y ago
Your misreading: the turtle doesn't move at all. It teleports to the rabbit's location. (Counting following a link as a move, which seems to be the costly operation being optimized for.) For every full iteration of the loop, TH (tortoise and hare) follows 3 links, while TT (teleporting turtle) follows 1 link. In the loop case, where the loop of length n is linked in at k steps, the there must be at least k iterations of both loops (the turtle or tortoise must reach the loop). In the no-loop case, there must be at least n iterations of the TT case but TH can get away with n/2 iterations. Unfortunately, each iteration of TH has more than twice the cost of an iteration of TT, when optimizing for following loops.
- argv_empty 17y ago
  * For every full iteration of the loop, TH (tortoise and hare) follows 3 links, while TT (teleporting turtle) follows 1 link.* Except the TT loop iterations accomplish half as much in terms of covering ground, so TH and TT don't take the same number of iterations.
  - JoachimSchipper 17y ago
    If both Tortoise and Hare have just entered a cycle of length n, the original algorithm takes n iterations before the Tortoise is caught (2n steps for the Hare, n steps for the Tortoise). Likewise, TT takes n steps (although it may take some additional steps before the turtle is teleported into the loop; once this has happened, it's n steps.)
    - argv_empty 17y ago
      * once this has happened, it's n steps* Unless the turtle teleports some time during those n steps. The only way the turtle won't teleport during that time is if the rabbit has already taken at least n steps to get to the loop, in which case, it only eliminates up to 1/4 of the mammal moves.

barrkel 17y ago

Your misreading: the turtle doesn't move at all. It teleports to the rabbit's location. (Counting following a link as a move, which seems to be the costly operation being optimized for.) For every full iteration of the loop, TH (tortoise and hare) follows 3 links, while TT (teleporting turtle) follows 1 link. In the loop case, where the loop of length n is linked in at k steps, the there must be at least k iterations of both loops (the turtle or tortoise must reach the loop). In the no-loop case, there must be at least n iterations of the TT case but TH can get away with n/2 iterations. Unfortunately, each iteration of TH has more than twice the cost of an iteration of TT, when optimizing for following loops.

argv_empty 17y ago
* For every full iteration of the loop, TH (tortoise and hare) follows 3 links, while TT (teleporting turtle) follows 1 link.* Except the TT loop iterations accomplish half as much in terms of covering ground, so TH and TT don't take the same number of iterations.
- JoachimSchipper 17y ago
  If both Tortoise and Hare have just entered a cycle of length n, the original algorithm takes n iterations before the Tortoise is caught (2n steps for the Hare, n steps for the Tortoise). Likewise, TT takes n steps (although it may take some additional steps before the turtle is teleported into the loop; once this has happened, it's n steps.)
  - argv_empty 17y ago
    * once this has happened, it's n steps* Unless the turtle teleports some time during those n steps. The only way the turtle won't teleport during that time is if the rabbit has already taken at least n steps to get to the loop, in which case, it only eliminates up to 1/4 of the mammal moves.