Thursday, March 7, 2013

[Algorithms] Brent's algorithm

This is also a cycle detection method.

Its key point is to move into the cycle as fast as possible.

Example: 0 1 2 3 4 5 6 7 3 4 5 6 7 3.....

P = 2^0 = 1, T = 0, H = 0, no match with x[T] within x[T + P]
P = 2^1 = 2, T = 1, H = 1, no match with x[T] within x[T + P]
P = 2^2 = 4, T = 3, H = 3, no match with x[T] within x[T + P]P = 2^3 = 8, T = 7, H = 5, no match with x[T] within x[T + P] -> v = 5;

Let T = 0, H = 5. -> u = 3 because x[3] = x[8].(x[0 + u] = x[v + u])

No comments:

Post a Comment