Mersenne: Re: DWT help

[EWMAYER]

Naessens Yan <[EMAIL PROTECTED]> wrote:

>Is it possible to do a DWT with NTT or the Scho"nhage-Strassen algorithm ?

Yes. There are quite a few posts in the archives on this topic.
I suggest you find and read them - they will likely answer many of
your questions.

Aside:

Re. the digest archives, in M-digest Vol 1, #948 (Mon, 18 Mar 2002)
Richard Woods <[EMAIL PROTECTED]> posted a list of major discussion
topics that have appeared on this list over the years, indexed by
digest number. Richard, would it be possible to post this list online
(perhaps as one of the subpages of the official GIMPS website) and
replace the text digest numbers with hyperlinks to the relevant
digests? Of course, someone would need to volunteer time to do this
and to keep it up-to-date. Lacking that, the searchable version of
the archive at http://www.ndatech.com/mersenne/signup.htm is OK,
but as this list doesn't use a set of standard keywords or subject
classifications (as most scientific journals do), it's not the best
way to pull together the various postings that constitute the loose
discussion threads that have appeared over the years.


>If it is possible, what will be different from the floating-point version ?

This list is far from complete, but captures some of the key issues:

- Integer arithmetic. Note that while most general-purpose processors
  are fast at basic integer operations (+ - << >> & | ^ ~, in C syntax)
  very few CPUs can do do integer multiplies anywhere near as fast
  as floating, especially if the integer product exceeds 64 bits.
  (Alpha 21264 and IA64 are the exceptions here, but even these need
  2 cycles to get both halves of a 128-bit integer product).
  Extra SIMD hardware (like the x86 MMX or G4 AltiVec units) is not
  helpful for this, since the supported operand widths are too small.
  Also, if your integer modulus is close to the machine's wordsize
  (and several well-known moduli that are convenient for arithmetic
  happen to be like this, e.g. 31-32 or 61-64 bits), frequent mod
  operations will be needed. These mods will be even slower if your
  prime doesn't have a convenient form, in which case you'll need
  to do something like a Montgomery modular multiply.
  You may be using several small primes, in which case you'll need
  a CRT reconstruction during the carry step.

- For length-N NTT, you need a primitive Nth root of unity. It is
  preferable that this Nth root yield low-order power-of-two
  roots of unity that have a convenient form, i.e. that
  multiplication by them involve just shifts and adds.

- For length-N DWT, you need an Nth root of two. While it is less
  important that this root (and its powers) have a nice form, it is
  still preferable.

- Besides power-of-two runlengths, it is desirable that the NTT also
  support a decent variety of intermediate runlengths like N = 3*2^k.
  Note that some types of NTT (e.g. those over suitably chosen Gaussian
  integers, a.k.a. Fast Galois Transforms) have nice properties when
  the transform length is a power of 2 (FGT looks just like complex
  FFT in this case), but are not so nice for non-power-of-2 lengths.


>If someone has a C version of integer DWT, can he send me the source, please ?

Here are two that should be of interest:

1) Nick Craig-Woods' StrongArm code:

http://www.axis.demon.co.uk/armprime/

2) Jason Papadopoulos' Integer Convolution Library (ICL):

http://www.boo.net/~jasonp/icl11.tar.gz

Jason's implemtation is the fastest I've heard of for general-
purpose hardware and yet, even on an integer-crunching monster
like the Alpha 21264, it's at least 2X slower than the best
floating-point implementation. However, I'm hopeful that with
a suitably chosen modulus and lots of algorithmic tricks one
can approach the speed of a floating FFT, at least on this
kind of high-end hardware.


>Where can I find the Crandall/Fagin paper ?

Mathematics of Computation 62 (205), pp.305-324, January 1994.
Anyone seeking to understand the DWT should read this paper,
and work several of the short-transform-length numerical examples
therein. It's not the last word on the DWT, but it certainly is
the first.

Cheers,
-Ernst