🚀 What Problem Are We Solving? (The Loop)

Imagine you are traveling through a sequence of steps (like nodes in a linked list, or numbers from a math formula). Eventually, you might enter a loop, where the steps just repeat forever.

The sequence looks like the Greek letter “Rho” : it has a straight Tail leading into a repeating Cycle (Loop).

Our goal is simple: Find the length of the repeating Cycle (lambda) and the length of the Tail (k) as quickly as possible.

Concept	What it is	Example
Tail (k)	The steps before the cycle starts.	1, 2, 3 (3 steps)
Cycle (lambda)	The sequence that repeats infinitely.	4, 5, 6 (3 steps)
Full Sequence	1, 2, 3, 4, 5, 6, 4, 5, 6, 4, 5, 6, ...

Why Brent’s Algorithm?

Brent’s Algorithm is a clever way to find this loop. Unlike other methods that crawl slowly, Brent’s method is like having a Teleporting Runner that jumps ahead, cutting down on the total number of steps it takes to find the cycle. It’s often faster in practice!

---

🧠 How Brent’s Algorithm Works

Brent’s algorithm uses two main pointers that move along the sequence:

1. start: The ‘anchor’ pointer.
2. current: The ‘runner’ pointer.

It works in two simple phases:

Phase 1: Find the Cycle Length ($\lambda$)

This is where the ‘teleporting’ happens.

• The current runner moves one step at a time.

• We use a counter, steps_limit, that doubles every time it’s reached (e.g., 1, 2, 4, 8, 16).

• When the runner reaches a steps_limit, we “teleport” the start pointer to the current position of the runner.

• This keeps the start pointer close to the beginning of the cycle, guaranteeing the runner will complete the cycle and meet it quickly.

• When the runner finally catches up to the ‘teleported’ anchor, the distance the runner traveled since the last teleport is the Cycle Length (lambda).

Phase 2: Find the Tail Length (k)

1. Reset the start pointer to the very beginning of the sequence (x_0).
2. Move the current runner ahead by exactly lambda steps (the cycle length we just found).
3. Now, move both start and current one step at a time until they meet.
4. The distance they travel to meet is the Tail Length (k).

---

💻 Code Implementation

The most critical part of this algorithm is a function that gives us the next value in the sequence. For simplicity, we’ll use a sequence generated by the formula: f(x) = (x \cdot x + 1) \bmod 11.

Sequence starting at x_0 = 0:

0 \to 1 \to 2 \to 5 \to 3 \to 10 \to \mathbf{2} \to 5 \to 3 \to 10 \to \mathbf{2} \dots

• Tail (k): 0, 1 (Length k=2)
• Cycle (lambda): 2, 5, 3, 10 (Length lambda=4)

🐍 Python Code

def sequence_generator(x):
# Our simple formula: (x^2 + 1) mod 11
return (x * x + 1) % 11

def brents_algorithm_py(x0):
current = x0
start = x0

steps_limit = 1
cycle_length = 0

# PHASE 1: Find the cycle length (lambda)
current = sequence_generator(current)
cycle_length += 1

while current != start:
if cycle_length == steps_limit:
# Teleport the 'start' pointer and increase the jump limit
start = current
steps_limit *= 2
cycle_length = 0

current = sequence_generator(current)
cycle_length += 1

lambda_val = cycle_length

# PHASE 2: Find the tail length (k)
start = x0
current = x0

# Move 'current' ahead by lambda_val steps
for _ in range(lambda_val):
current = sequence_generator(current)

# Move both until they meet
tail_length = 0
while start != current:
start = sequence_generator(start)
current = sequence_generator(current)
tail_length += 1

return lambda_val, tail_length

# Test with starting point x0 = 0
cycle, tail = brents_algorithm_py(0)

print(f"Python Output: Cycle Length (λ) = {cycle}, Tail Length (k) = {tail}")
# Expected Output: Cycle Length (λ) = 4, Tail Length (k) = 2

💻 JavaScript Code

function sequence_generator(x) {
// Our simple formula: (x^2 + 1) mod 11
return (x * x + 1) % 11;
}

function brentsAlgorithmJS(x0) {
let current = x0;
let start = x0;

let steps_limit = 1;
let cycle_length = 0;

// PHASE 1: Find the cycle length (lambda)
current = sequence_generator(current);
cycle_length++;

while (current !== start) {
if (cycle_length === steps_limit) {
// Teleport 'start' and increase the jump limit
start = current;
steps_limit *= 2;
cycle_length = 0;
}

current = sequence_generator(current);
cycle_length++;
}

const lambda_val = cycle_length;

// PHASE 2: Find the tail length (k)
start = x0;
current = x0;

// Move 'current' ahead by lambda_val steps
for (let i = 0; i < lambda_val; i++) {
current = sequence_generator(current);
}

// Move both until they meet
let tail_length = 0;
while (start !== current) {
start = sequence_generator(start);
current = sequence_generator(current);
tail_length++;
}

return { cycle: lambda_val, tail: tail_length };
}

// Test with starting point x0 = 0
const result = brentsAlgorithmJS(0);

console.log(`JavaScript Output: Cycle Length (λ) = ${result.cycle}, Tail Length (k) = ${result.tail}`);
// Expected Output: Cycle Length (λ) = 4, Tail Length (k) = 2

🚀 C++ Code

#include <iostream>

// Function that defines our sequence
int sequence_generator(int x) {
// Our simple formula: (x^2 + 1) mod 11
return (x * x + 1) % 11;
}

std::pair<int, int> brents_algorithm_cpp(int x0) {
int current = x0;
int start = x0;

int steps_limit = 1;
int cycle_length = 0;

// PHASE 1: Find the cycle length (lambda)
current = sequence_generator(current);
cycle_length++;

while (current != start) {
if (cycle_length == steps_limit) {
// Teleport 'start' and increase the jump limit
start = current;
steps_limit *= 2;
cycle_length = 0;
}

current = sequence_generator(current);
cycle_length++;
}

int lambda_val = cycle_length;

// PHASE 2: Find the tail length (k)
start = x0;
current = x0;

// Move 'current' ahead by lambda_val steps
for (int i = 0; i < lambda_val; i++) {
current = sequence_generator(current);
}

// Move both until they meet
int tail_length = 0;
while (start != current) {
start = sequence_generator(start);
current = sequence_generator(current);
tail_length++;
}

return {lambda_val, tail_length};
}

int main() {
// Test with starting point x0 = 0
std::pair<int, int> result = brents_algorithm_cpp(0);

std::cout << "C++ Output: Cycle Length (λ) = " << result.first
<< ", Tail Length (k) = " << result.second << std::endl;
// Expected Output: Cycle Length (λ) = 4, Tail Length (k) = 2
return 0;
}

✅ Conclusion

Brent’s algorithm is a smart, efficient way to find the characteristics of a repeating sequence. By using the power-of-two jump, it quickly finds the Cycle Length (lambda) and then uses that to pinpoint the Tail Length (k). This is a powerful technique to have in your coding toolkit!