Optimal generalization of Montgomery's trick


Hello, about the Montgomery's trick to compute 1/z1 && 1/z2 via
t= 1/(z1z2) and 1/z1= t* z2; 1/z2= t* z1, I was wondering what's the
generalization of this method and what's the minimun number of
multiplies requred ???

Say that input numbers are z[0], z[1], ..., z[n-1], each
non-null. I found that building a binary tree with v[N+ k]= z[k] for k=
0 to n-1, then computing v[k]= v[2k] * v[2k+ 1] for k= n-1 downto 1
leads to a very efficient implementation. This is step 1.
Step2: Compute inv= v[1] ^ -1; (one invert)
Step3: is for every non-root and non-leaf node k compute v[2k]=
v[2k]* v[k xor 1] {and} v[2k+1]= v[2k+1] * v[k xor 1]; that is for (k=
4; k< 2n; k++) v[k]*= v[(k/2) xor 1] {in a single loop}
Step4: for (k= 0; k< n; k++) result[k]= v[(N+ k) xor 1] * inv;

The total number of multiplies is (n-1) + (2n-4) + n = 4n -5 and
seems OPTIMAL.
The number of inversions is 1, but can we do better ?

Here is the C++ implementation say that "mul" and "inv" are
general multiply and invert routines for a specific number field or
matrix, N= number of elements and "type" is the basic to-invert data
type:

void invert(type z[], int N) //z has cardinality N (N
elements z[0.. N-1])
{
type v[N* 2];
for (int K= N; --K>= 0; v[N+ K]= z[K]);
for (int K= N; --K; v[K]= mul(v[K* 2] , v[K* 2+ 1]) ); //N-1
mul's
for (int K= 2; K< N; K++) {
v[K* 2+ 0]= mul(v[K* 2+ 0] , v[K ^ 1]);
v[K* 2+ 1]= mul(v[K* 2+ 1] , v[K ^ 1]);
} //2N-4 mul's
v[0] = inv(v[1]); //no need to store separately
for (int K= N; --K>= 0; z[K]= mul(v[(N+ K) ^ 1] , v[0]); //N
mul's, z is the result...
}
This works for any N> 0 (odd, even), and if we want to "mul" all
resulting z's with a constant w_hi/ w_lo, we set v[0]= mul(w_hi , inv(
mul(V[1] , w_lo) ) ) at the invert step, using 2 more mul's.



To all comp theory members, happy analysis, efficient coding, and I
expect comments....

Robert B.

.