fft enhancement?
Décio Luiz Gazzoni Filho
decio at decpp.net
Sat Jul 31 16:00:28 CEST 2004
-----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-----
More information about the gmp-discuss
mailing list