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? 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 http://www.axis.demon.co.uk/armprime/ For other archictures (like alpha) having the top bit set in the 64 bit modulus was a pain. > My personal opinion is that NTTs will not be faster than FFTs until modular > multiplication has the same throughput as floating point multiplication. > Right now we're at least a factor of 3-5 away from that. I agree with you and this was my experience with StrongARM. The integer DWT was about 3 times slower than the equivalent pentium implementation. -- Nick Craig-Wood [EMAIL PROTECTED] _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
