Assume f has a period of length l, approximately equal to sqrt(p). Retain the value at step 2k, and compare it to each subsequent value, until the next power of 2 is reached. Once 2k exceeds l, step 2k+l will have the same value mod p as step 2k. This is determined by subtracting the two values and running gcd with n, thus extracting the prime p.
In my implementation, I multiply 256 differences together, then run the gcd algorithm, since the latter is a bit expensive, and most of the time it yields a negative result. This small change causes the program to run almost twice as fast. Of course I may need to back up through these 256 steps if I find that the values are equal mod n, i.e. all primes have fallen into the same loop.
If the gcd goes from 1 to 0 in a single step, you need to start again with a new seed, or a new function f. I begin with x2+29879, seeded with 5, and adjust the constant term of the quadratic thereafter. This algorithm easily factors most 35 digit numbers on a standard home computer.
The running time is proportional to the square root of p, for the smallest p dividing n. I thought about some enhancements that might lead to the square root of q, where q is the largest prime dividing p-1. This is inspired by the p-1 test in the previous section. However, such an algorithm would be much more complicated, and q is often close to p in practice, so little would be gained.
The name "pollard rho" comes from the Greek letter rho, which looks like a circle with a tail. ρ The first few (million) values march along the tail and around the circle, until a value repeats, and then you are in a loop.