At 12:46 PM 6/28/02 +0200, you wrote:
>Is it possible to do a DWT with NTT or the Schonhage-Strassen algorithm ?
>If it is possible, what will be different from the floating-point version ?
To perform a DWT, you need to find a prime that
1) allows a number theoretic FFT of large size, say 2^n, and
2) allows a number r such that r^(2^n) = 2, i.e. a large root of 2
I think a DWT using Schonhage-Strassen is possible; property 1 above
is certainly possible, but I don't know how you'd find numbers that
satisfy property 2. Likewise, Schonhage-Strassen multiplies compute
a product mod 2^(big number)+1, so that you would have to zero-pad
to actually perform cyclic convolution (the DWT saves you from having
to double the runlength again)
In practice, primes that satisfy property 1 seem very common but those
which satisfy both properties simultaneously are much more rare (there
are no 32-bit primes I know of which can work).
>If someone has a C version of integer DWT, can he send me the source, please ?
>Where can I find the Crandall/Fagin paper ?
Have a look at www.boo.net/~jasonp/icl11.tar.gz; this is an integer convolution
library I wrote for the Alpha ev6 which can do normal and DWT multiplication.
It's a bit old by now, and I'm working on it.
Hope this helps,
jasonp
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
