Introduction

Consider the following geometric problem: mark all vertical lines x = c and horizontal lines y = c where c ∈ ℤ on a plane. Now consider a line y = (px + r)/q where p, r ∈ ℕ and q ∈ ℕ₊. Since the residue class of r modulo q determines the behavior, we can assume r < q without loss of generality.

Imagine a moving point traveling along this line from left to right within the interval (0, L] where L ∈ ℕ. Each time the point crosses a vertical line, it writes the character R; each time it crosses a horizontal line, it writes U. When the point hits an integer lattice point (where both lines intersect simultaneously), the convention is to write U first, then R. The resulting sequence of characters is called an RU string.

Now consider a monoid 𝔾 (which you may define yourself) containing two distinguished elements R, U ∈ 𝔾. The goal is to compute the value of the RU string efficiently by interpreting it as a product in this monoid. As it turns out, many summation problems of the form ∑ᵢ₌₁ᴸ f(i, ⌊(pi+r)/q⌋) can be reduced to this framwork.

The Recursive Algorithm

The algorithm follows the structure of the Euclidean algorithm for computing GCD. The key insight is to handle the cases where p ≥ q and p < q differently.

Case 1: p ≥ q

When p ≥ q, we can reduce p to p mod q. This case is relatively straightforward. Consider what happens when the x-coordinate increases by 1 unit: the y-coordinate increases by p/q units. Within each horizontal strip of height 1, there is exactly one R (the vertical line crossing), and there are either ⌊p/q⌋ or ⌊p/q⌋ + 1 occurrences of U before that R.

We can strip off at least ⌊p/q⌋ occurrences of U from consideration. This effectively gives us those U operations for free while reducing the vertical step size to the fractional part {p/q}. Mathematically, this corresponds to:

• Replacing R with L<sup>⌊p/q⌋</sup> R (where L represents left-multiplication by U)
• Setting p ← p mod q

Case 2: p < q

This case is more complex and requires swapping the roles of p and q, as well as R and U. Simply reflecting the coordinate system across y = x introduces three problems:

Problem 1: Intersection Requirements

Since r ≥ 0, the recursive subproblem's line must intersect the y-axis in the first quadrant. Direct reflection would make it intersect the x-axis instead, violating this invariant.

Solution: Find the first occurrence of U (which occurs where the line intersects y = 1), compute its contribution, remove the vertical strip (0, 1], then reflect the remaining region. The new line will have a positive y-intercept.

How many R operations occur before the b-th U? The answer is the largest integer x such that ⌊(px + r)/q⌋ < b. This simplifies to x ≤ ⌊(qb - r - 1)/p⌋, so the count is ⌊(qb - r - 1)/p⌋.

For b = 1, the contribution before the first U is R<sup>⌊(q-r-1)/p⌋</sup> U. Since p < q, we cannot encounter a lattice point here, so no additional R follows. After removing this strip and reflecting, the parameters become:

• p ↔ q (they swap roles)
• New r = q - r (derived from the x-intercept at y = 1)

Problem 2: Non-integer Length

After reflection, the horizontal length L is no longer an integer.

Solution: Find the last occurrence of U, recursively process the region below it, and handle the region above separately. The total number of U operations in the interval (0, L] is L₀ = ⌊(pL + r)/q⌋. If L₀ = 0, there are no U operations, and the answer is simply Rᴸ.

After removing the first U (as solved in Problem 1), the new length becomes L₀ - 1. The contribution from the region above the last U consists only of R operations. The count is L - ⌊(qL₀ - r - 1)/p⌋.

Problem 3: Lattice Point Ordering

After reflection, the ordering of operations at lattice points reverses: what was U then R becomes R then U.

Solution: Set r ← r - 1. This shifts the line downward by a tiny amount. Original lattice points satisfying px ≡ 0 (mod q) now appear with the desired ordering R then U. Points that were at px ≡ 1 (mod q) become the new lattice points, but these naturally follow the convention U then R.

With this adjustment, the new r equals the old q - r - 1, and we take it modulo p to maintain the invariant 0 ≤ r < p.

Complexity Analysis

The algorithm follows the same recurrence structure as the Euclidean algorithm for GCD. Each two iterations reduce p to p mod q. Analyzing the cases q ≤ p/2 and q > p/2 shows that p atleast halves every two iterations. Therefore, the number of recursive calls is O(log(p + q)).

The algorithm also uses exponentiation operations. The exponent in each R exponentiation is O(q/p), and its logarithm is O(log q - log p). In subsequent iterations, q becomes the previous p and p becomes a smaller value. Summing these gives O(log q), which is still logarithmic.

The total complexity is O(T(log(p + q) + log L)), where T is the time complexity of a single multiplication in the monoid 𝔾.

Reference Implementation

template<typename Op>
Op universal_euclid(int p, int q, int r, int L, const Op& U, const Op& R) {
    if (p >= q) {
        Op adjusted_R = pow_op(U, p / q) * R;
        return universal_euclid(p % q, q, r, L, U, adjusted_R);
    } else {
        int total_U = (p * L + r) / q;
        if (total_U == 0) {
            return pow_op(R, L);
        }

        // Contribution before first U
        int initial_R_count = (q - r - 1) / p;
        Op result = pow_op(R, initial_R_count) * U;

        // Recursive call with swapped parameters
        int new_r = (q - r - 1) % p;
        Op recursive_result = universal_euclid(q, p, new_r, total_U - 1, R, U);
        result = result * recursive_result;

        // Contribution after last U
        int final_R_count = L - (total_U * q - r - 1) / p;
        result = result * pow_op(R, final_R_count);

        return result;
    }
}

Example Applications

Computing Summation Values

When solving problems like ∑ᵢ₌₁ⁿ iᵏ or similar polynomial sums, we can define an operation structure that captures the transformation applied to the accumulated answer. The monoid elements track:

• Linear updates to the running answer
• Quadratic contributions for polynomial evaluation
• Cross-terms between index and value

The key is to define composition rules that maintain closure under the monoid operation while correctly propagating contributions through the RU string.

Matrix-Based Transformations

For problems involving matrix sequences or linear transformations, define the monoid to track:

• The accumulated answer matrix
• The cumulative effect of R operations (multiplication by matrix A)
• The cumulative effect of U operations (multiplication by matrix B)

When concatenating two RU strings, the new answer combines the left portion with a transformed version of the right portion, where the transformation accounts for the index shifts induced by the left string's R and U operations.

Polynomial Interpolations

For evaluating sums of polynomials at specific points, define an operation that captures:

• Updates to the polynomial value
• Updates to the evaluation point
• Additions to the accumulated answer

The cross-term contributions during composition require binomial expansion of the polynomial transformations, with complexity O(k⁴ log n) for polynomials of degree k.

When handling the initial offset where r might not satisfy r < q, apply U<sup>⌊r/q⌋</sup> first and reduce r modulo q. The final answer extraction depends on the specific problem but often involves reading constant terms from the accumulated transformation structure.