Is there a finite-field equivalent to the DWT?

[fivemack]

If I read Percival's paper http://www.daemonology.net/papers/fft.pdf correctly, what you need for arithmetic mod k^n \pm 1 with a Fourier transform of size N is an Nth root of k, which I suppose is quite hard to find in companion with an Nth root of unity.

But let's have a look for finite fields with convenient root properties:

for(p=1,256*256*256,q=p*2^40+1;\
 if(isprime(q),r=2;v=2;\
  u=polrootsmod(x^2-v,q);\
  while(length(u)==2,v=lift(u[1]);u=polrootsmod(x^2-v,q);r=r*2);\
  if(r>100000,print([p,q,r]))))

GF(81*2^48+1) has a 16384th root of 2 and a 65536th root of 3!

GF(10548595*2^40+1) has a 2^23rd root of 2, which is happily in the GIMPS range (FFT size 2^23, digit size 2^{19 or 20} is 159Mbits)

Or is the DWT reliant on properties of the complex numbers in ways not replicated by even the best-equipped number fields?

[akruppa]

Is this really a 2^23-rd root? I get only 2^22:

p=10548595*2^40+1
? (p-1)/znorder(Mod(2,p))
%5 = 4194304
? Mod(2,p)^(1/4194304)
%6 = Mod(122531489542579258, 11598302859199774721)
? Mod(2,p)^(1/8388608)
  *** _^_: gpow: nth-root does not exist.

Afaik all the DWT needs is that you have the required roots of unity and of the desired multiplier you want to appear in the wrapped-around part of the convolution.

Alex

[ewmayer]

A pair of relevant older threads for you, Tom:

http://mersenneforum.org/showthread.php?t=118

http://mersenneforum.org/showthread.php?t=1081

[fivemack]

Originally Posted by akruppa

Is this really a 2^23-rd root? I get only 2^22

You're right, I should have initialized r=1, I forgot how while loops work.

45960129*2^37+1 does have 2^23-rd roots of two; the smallest is 376222520911 which is still (as you'd expect for the smallest of 2^23 random numbers less than 2^63) greater than 2^32. Nothing k*2^36+1 with k<2^28 has (>=2^24)th roots of two.

Though I see this field has already been thoroughly dealt with, and p=2^64-2^32+1 with its attractive form and 2^26th roots of two consequent on 2^192=1 is surely the right answer, except that it forces FFT size a power of two. So the next search is for primes with [3,5,7]*2^lots-th roots of both 1 and 2, and that too has already been done. Time to abandon the random arithmetic and start thinking about implementation :(

[ewmayer]

By way of an addendum, the reasons I still have not gotten back to serious work on the hybrid FFT/FGT as described in the above-linked thread are as follows [all within the context of rather-limited-free-time-for-this-hobby-work]:

0) Fast 64-bit integer MUL still not very widespread - e.g. Cire2 only supports in 64-bit-OS mode;

1) I only prototyped a hybrid FFT/FGT with the mod-M61 DWT for power-of-2 transform lengths - for non-power-of-2, I still need to discern the pattern of FGT outputs to see how it compares to well-known one for FFT-applied-to-real-data. I do know that the output pattern for FGT [specifically the locations of the generalized "complex conjugates"] are different for non-power-of-2 runlengths than the [j, N-j] pairings of the FFT outputs. That complicates things, especially in terms of having the FFT and FGT execute side-by-side, for which same-index-patterns-for-both is a desirable property.

2) Floating-point SIMD [e.g. SSE2] is much simpler to implement - 6 months of evening-and-weekend work and I have a nearly-complete version of this, and an already-realized 2x speedup. 2x is the absolute most one could ever expect using hybrid FFT/FGT, and realizing it in practice is far from guaranteed. The old "choosing one's battles" theme.