Khác biệt giữa bản sửa đổi của “Phát hiện chu trình”

[[Richard Brent (nhà khoa học)|Richard P. Brent]] mô tả một thuật toán tìm chu trình khác, giống thuật toán rùa và con thỏ, chỉ cần hai con trỏ để duyệt dãy số.<ref name="brent">{{citation|first=R. P.|last=Brent|authorlink=Richard Brent (scientist)|title=An improved Monte Carlo factorization algorithm|journal=[[BIT Numerical Mathematics ]]|volume=20|year=1980|pages=176–184|url=http://wwwmaths.anu.edu.au/~brent/pd/rpb051i.pdf|doi=10.1007/BF01933190|issue=2|s2cid=17181286}}.</ref> Tuy nhiên, nó dựa theo nguyên tắc khác: tìm giá trị [[lũy thừa bậc hai]] nhỏ nhátnhất {{math|2^''i''}} mà lớn hơn cả {{mvar|λ}} và {{mvar|μ}}. Với {{math|1=''i'' = 0, 1, 2, ...}}, thuật toán so sánh {{math|''x''_{2^''i''&minus;1}}} với mỗi giá trị phần tử tiếp theo cho đến khi gặp lũy thừa bậc hai tiếp theo, dừng khi nó gặp một cặp bằng nhau. Thuật toán có hai ưu thế so với thuật toán rùa và con thỏ: nó tìm đúng và trực tiếp giá trị {{mvar|λ}} của chu trình, thay vì phải tìm nó trong đoạn mã sau, và các bước của nó chỉ cần một phép tính {{mvar|f}} hơn là 3.<ref>{{harvtxt|Joux|2009}}, Section 7.1 .2, Brent's cycle-finding algorithm, pp. 226–227.</ref>

Giống thuật toán rùa và thỏ, Đâyđây là thuật toán con trỏ dùng {{math|''O''(''λ'' + ''μ'')}} lần kiểm tra và tính hàm cùng với {{math|''O''(1)}} bộ nhớ. Đồng thời cũng không quá khó để chứng minh rằng số lần tính hàm không bao giờ cao hơn số lần tính trong thuật toán của Floyd. Brent cho rằng, trên trung bình, thuật toán tìm chu trình của ông chạy khoảng 36% nhanh hơn so với cái của Floyd và nó đẩy tốc độ cho [[thuật toán Pollard rho]] bởi tầm 24%. Ông cũng xét [[phân tích trung bình]] cho phiên bản ngẫu nhiên của thuật toán trong đó dãy chỉ số xét bởi con trỏ chậm hơn không phải lũy thừa bậc hai như thường, mà là bội ngẫu nghiên của lũy thừa bậc hai. Mặc dù ông định áp dụng chủ yếu cho các thuật toán phân tích số nguyên, Brent cũng có xét tới các ứng dụng cho việc kiểm nghiệm các bộ sinh số giả ngẫu nhiên.<ref name="brent"/>