如何在PARI/gp中高效反转向量？求正规快速实现方式

Great catch on the performance issues with your initial approach—let's walk through proper, efficient ways to reverse vectors in PARI/gp, no polynomial tricks required.

First, why your first method was so slow #

Your initial code:

vector(10^4,i,vector(10^4,i,i)[10^4-i+1])

was painfully inefficient because it regenerated the entire original vector every single time inside the loop. That’s an O(n²) operation (10⁴ iterations each creating a 10⁴-length vector), which explains the 4-second runtime—total wasted computation!

The "proper" efficient linear-time methods #

Here are two straightforward, performant approaches that stick to native vector operations:

1. Generate reversed vector via index lookup

First store your original vector, then build the reversed version by accessing elements from the end to the start:

// Create your original vector
original_vec = vector(10^6, i, i);
// Reverse it by indexing from the end
reversed_vec = vector(#original_vec, k, original_vec[#original_vec - k + 1]);

This runs in O(n) time—only two linear passes (one to create the original vector, one to build the reversed one). For a 10⁶-length vector, this will be just as fast as your polynomial trick, without relying on type conversion hacks.

2. In-place reversal (save memory)

If you don’t need to keep the original vector, you can reverse it in place by swapping elements from the start and end moving inward:

original_vec = vector(10^6, i, i);
n = #original_vec;
// Swap first with last, second with second-last, etc.
for(k=1, floor(n/2), swap(original_vec[k], original_vec[n - k + 1]));

This uses no extra memory for a new vector and still runs in O(n) time—perfect for very large datasets where memory is a concern.

Why your polynomial trick worked so well #

Your Vec(polrecip(Pol(vector(10^6,i,i)))) method was fast because polrecip (polynomial reciprocal) is a highly optimized low-level operation that essentially reverses the coefficients of the polynomial. It’s a clever hack, but it’s not the most idiomatic way to handle vector reversal since it involves converting between vector and polynomial types.

内容的提问来源于stack exchange，提问作者Joe