[music-dsp] fixed point fft?

[Joshua Scholar]

----- Original Message -----
From: "joshua reich" <josh at i2pi.com>
To: <music-dsp at aulos.calarts.edu>
Sent: Monday, April 21, 2003 5:59 AM
Subject: Re: [music-dsp] fixed point fft?


>
> Thanks for that. Ive just started studying number theory, and its nice to
> have some practical applications outside of crypto.
>
> On Sun, 20 Apr 2003, Joshua Scholar wrote:
>
> >Anyone know how to calculate x*y mod (2^n-1) quickly?  I know there's an
> >answer.
>
> assuming 2^n-1 is prime ?
>


Yeah, assuming that.

2^n-1 is prime for n in{ 2,3,5,7,13,17,19,31,61,89,107,127,607}.  Hmm n is
all prime!   31,  61 and 127 are convenient (no I don't know of any
processors that have 128 bit math, yet).

Too bad there isn't one around the size of the mantissa of a double,
assuming there's a way to calculate (x*y mod (2^n-1)) in a double, though on
intel you could do 80 bit doubles in assembly language.

2^n+1 is prime for n in {0,1,2,4,8,16} Hmm n is all powers of 2 (except 0).
And mupad can't find any more.

mupad refuses to solve for primitive roots though.

I have a reference for the FGT that says that one of it's strengths is that
you can use 2^n-1 primes, so I assume you CAN'T use them for NTT and that
they don't have the roots.