Brendan Younger <[EMAIL PROTECTED]> wrote:
>I know there has been some discussion on this list about the
>theoretical possibility of staying in frequency space and doing a bunch
>of point-wise squarings in there instead of computing the inverse DWT
>after every iteration. Now, I'm not suggesting this as a feasible
>avenue for GIMPS as I've read some of the arguments against it in the
>archives. I'm just curious as to how it might proceed if you could
>assume infinite precision, etc. For instance, would it be as simple as:
>
>DWT(x) -> X^n -> IDWT(X^n) == x^n (mod 2^q - 1) (where "n" is now only 2?)
Yes. Of course since you have just one element in your input vector,
the DWT multiplier is just unity, FFT(x) = x, and you're really just
doing a scalar multiply and subsequent modular reduction (that's the
carry step).
>Of course I'm simplifying by not including the subtraction by 2
For any length-n vector with just a single nonzero term in the first
slot, i.e. x = (c, 0, 0, ... , 0), the FFT is trivial:
FFT(x) = (c, c, c, ... , c),
so to do the subtract-2 in the frequency space, just subtract 2
from *every* term after doing the dyadic squaring (there might
be a factor 1/n in there, depending on where the divide-by-n occurs
in your FFT implementation).
>Also, if it *is* this simple, could there be any
>modular reduction of the X^n before doing the IDWT?
AFAIK, no, at least not in a floating-point-FFT-based scheme.
If you were doing a number-theoretic transform modulo 2^q-1
you'd have your mod, but then things again reduce to the one-term
scheme described above. Another question one might ask is, can
one do any part of the normalize-outputs-and-carry step in frequency
space? The problem here is that the forward-FFTed and dyadically-
squared terms contain a mixture (linear superposition, to be
precise) of the actual inverse FFT outputs one wants. Each
term contains a different mix of the n outputs, and in the
Crandall-Fagin DWT scheme, these outputs are w.r.to a mixture
of bases, so even if one had a clever way to effect the normalization
by a constant base in frequency space, it wouldn't work with DWT.
Cheers,
-Ernst
