Recent Activity

&ldl Floyd's Algorithm has one pointer moving at 1-step per iter, and another at 2-steps per iter
This makes the initial step of "find node in loop" take 3-steps per iter
Brent's Algorithm reduces this to 1-step per iter by having one pointer at 0-steps per iter and another at 1-step per iter
By periodically updating the stationary pointer every power of 2, you'll find a node in the loop (and the loop length) faster
Now that you have the loop length, you can use the same method as before to find the start of the cycle

View original message on Discord

&ldl Added sliders, hit testing, and lots of polish

View original message on Discord

&ldl added some sliders, hit testing, and lots of polish

&ldl demonstrating a simple cycle detection algorithm

  • Find node in loop (one moves at 2x speed)
  • Compute length of loop
  • Compute start of loop
    2 ways to get to the start of the loop:
  • Take s steps
  • Take s + l steps -> equivalent to taking l + s steps
View original message on Discord