View Single Post
Old 2021-09-07, 20:50   #8
ewmayer's Avatar
Sep 2002
Rep├║blica de California

2·3·29·67 Posts

BTW, a useful identity for computing inverse weights for mod-M(p) transform is as follows - for length-N 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 primality-or-not of p remains to be established ... I instead use M(p) = 2^p-1 below):

w[j] = 2^[ceiling(j*p/N) - j*p/N], j = 0,...,N-1 .[*]

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,...,N-1, where sw denotes the number of "smallwords" in our variable-base 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[N-j] = 2 for j = 0,...,N .

Thus w[j] = 2/w[N-j], and the jth inverse weight can be computed as 1/w[j] = w[N-j]/2 . The 1/N multiplier needed for inverse-transform outputs can be lumped into the denominator of the RHS, thus one can define "effective inverse weights" by winv[j] = w[N-j]/(2*N); this needs just a single reciprocal 1/2N to be computed.

Last fiddled with by ewmayer on 2021-09-07 at 21:00
ewmayer is offline   Reply With Quote