Re: DFT with gp

[Karim Belabas <Karim.Belabas@math.u-bordeaux.fr>]

* 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]
`