Re: DFT with gp

[Alessandro Languasco <languasc@math.unipd.it>]

Dear Karim,
That’s great, thanks. But it works only when N is a power of two and unfortunately in my case N=q-1, q odd prime.
Is there in pari a more general version of  FFT which works for a general natural number N \ge 2 ?

Thanks again, 
Alessandro 

Sent from my iPad

> On 29 Aug 2018, at 16:33, Karim Belabas <Karim.Belabas@math.u-bordeaux.fr> wrote:
> 
> * Alessandro Languasco [2018-08-29 14:41]:
>> Dear all,
>> 
>> I should compute the DFT and the inverse DFT of a large vector of real numbers computed
>> using gp; I wrote a trivial implementation of it which is fine when the  
>> main parameter q (an odd prime) is tiny but it becomes very slow as soon as q is a bit larger.
>> 
>> I read here
>> https://pari.math.u-bordeaux.fr/faq.html <https://pari.math.u-bordeaux.fr/faq.html>
>> about the existence of some FFT-related functions in libpari
>> but they are not publicly available. 
>> 
>> So I am wondering if  these functions can be installed in gp ?
>> (I mean using some install() directive).
>> 
>> If so, some of you can send me an example of using them?
> 
>  install(FFTinit,Lp);
>  install(FFT,GG);
> 
>  k = 8; N = 2^k;
>  w = FFTinit(k);
>  v = vector(N, i, random(1.));
>  vhat = FFT(v, w);
> 
>  \\ checks
>  P = Polrev(v);
>  ? exponent([ subst(P, 'x, z) | z <- w ] - vhat)
>  %10 = -112   \\ instead of default accuracy -128
> 
>  \\ complexity
>  ? for(i=1,10^3, [ subst(P, 'x, z) | z <- w ])
>  time = 12,363 ms.
>  ? for(i=1,10^3, FFT(v,w))
>  time = 457 ms.
> 
> Cheers,
> 
>    K.B.
> --
> Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
> Universite de Bordeaux         Fax: (+33) (0)5 40 00 21 23
> 351, cours de la Liberation    http://www.math.u-bordeaux.fr/~kbelabas/
> F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]
> `