fft enhancement?

[Décio Luiz Gazzoni Filho]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Saturday 31 July 2004 10:18, Jason F wrote:
> I'm wondering if the FFT implemented in GMP would be suited for repeated
> squarings while remaining in the transform domain.
>
> <snip>
>
> I frankly don't know enough about FFTs in general to speak very
> intelligently about them or the specific properties of each type of
> transform.  But, from my understanding, a lot of the overhead comes from
> the transform and inverse transform.  If the repeated squaring can all take
> place in the transform domain without needing to do an inverse transform
> and then another forward transform in between, then surely a lot of
> processing can be saved.
>
> Is this just a fantasy, or could it really be implemented?

My FFTs are a little rusty, so I might be wrong here, but I don't think your 
idea is going to work.

Take two arrays, a[] and b[], then compute their FFTs, now you have A[] and 
B[]. Do a pointwise multiplication to obtain C[] = A[] .* B[] (in Matlab-like 
notation). Now the problem is that you started out with numbers of limited 
precision in a[] or b[], probably something like 16 bits. Now if you were to 
compute c[], the IFFT of C[], you might possibly get results as large as 16 + 
16 = 32 bits. If you were to multiply two 32-bit numbers, the result might be 
as large as 64 bits. Now since the mantissa of a double datatype is only 53 
bits (and even a long double on x86 is 64 bits) you're already going to 
overflow it, or get very close to. Not to mention you need some headroom for 
the addition pyramid, and the trig errors.

However, there might be an improvement to specific exponentiation algorithms 
where the exponent is not a power of 2. In that case you need multiplications 
in addition to squarings. Algorithms like the left-right binary ladder 
require multiplication by a fixed number, thus you can compute the transform 
of that number and store it -- you save a forward FFT for each 
multiplication. Consider, though, that the left-right binary ladder isn't the 
fastest exponentiation algorithm on the block, so unless the faster ladders 
also require multiplication by a fixed number, this improvement won't be 
useful in practice.

Décio
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFBC6YHMvCZlCdExvkRAoUlAJwOGcEPmM9cX0EmkUgSQUFRuuzv9gCeP6kl
OOLR9xAJkhOzfn3/0NK5I4U=
=UXaj
-----END PGP SIGNATURE-----