At 10:17 AM 3/18/02 +0000, you wrote:
>On Sun, Mar 17, 2002 at 08:08:06PM -0500, Jason Papadopoulos wrote: >> If you want to explore your idea further, here are some primes that may >> be useful. All are of the form i*2^e+1, and have the advantage that roots >> of unity out to some small order are "simple": >> >> i exponent FFT radix DWT size root >> 007d43548abc4361 320 8 2^17 67 >> 04235deab8321000 512 8 2^22 19 >> 0051656f7fe405c1 2048 8 2^19 29 >> 07ab47a650572a01 2112 8 2^16 29 >> >> 06954fe21e3e8100 384 32 N/A 37 >> 290d741 1792 32 N/A 5 > >These are big moduli? Surely this would make it quite inefficient? Probably. But the first four allow a trick, in that 4th and 8th roots of unity have the form j*2^k, where j is small (<64 bits). I think the 512-bit one is especially nice. >I spent a long time looking at all the options when I made the >StrongARM mersenne prime checker. For that architecture a modulus of >2^64-2^32+1 was the easy winner given that StrongARM doesn't have >floating point or a divide instruction but does have a quick >32x32->64bit multiply. More info here Yes, that prime is really nice. The only downside is that you can't pack more bits into a single element than with floating point data. And even that prime is very awkward to implement in x86 asm. jasonp _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
