BTW, a useful identity for computing inverse weights for modM(p) transform is as follows  for lengthN transform, start with the weights as per the original Crandall/Fagin paper (I dislike their p = 2^q  1 notation, since "p" in this sort of context generally implies prime, but their q is prime and primalityornot of p remains to be established ... I instead use M(p) = 2^p1 below):
w[j] = 2^[ceiling(j*p/N)  j*p/N], j = 0,...,N1 .[*]
This gives w[0] = 1, followed by a sequence of nonrepeating fractional powers of 2. E.g. for p = 263 and N = 16 we have w[j] = 2^[0,9,2,11,4,13,6,15,8,1,10,3,12,5,14,7]/16 = 2^[j*sw (mod N)] for j = 0,...,N1, where sw denotes the number of "smallwords" in our variablebase representation; if bw = p%N is the number of "bigwords", then sw = N  bw.
If we extend the formula[*] to j = N, we get w[N] = w[0] = 1. Instead define w[N] := 2, then observe that
w[j] * w[Nj] = 2 for j = 0,...,N .
Thus w[j] = 2/w[Nj], and the jth inverse weight can be computed as 1/w[j] = w[Nj]/2 . The 1/N multiplier needed for inversetransform outputs can be lumped into the denominator of the RHS, thus one can define "effective inverse weights" by winv[j] = w[Nj]/(2*N); this needs just a single reciprocal 1/2N to be computed.
Last fiddled with by ewmayer on 20210907 at 21:00
