Thanks @Bill Hart . I was going through the second link. So what is the complexity of this algorithm ? (I have a jpeg file attached with FFT multiplication algorithm snapshot, I think this is not used in the mpir implementation, isnt it? )
Thanks and regards Tanushree Banerjee, Electrical and Computer Engineering, Graduate Student University of Waterloo On Wed, Apr 25, 2018 at 10:43 AM, 'Bill Hart' via mpir-devel < mpir-devel@googlegroups.com> wrote: > There is, by the way, a brief introduction to the FFT used in MPIR (the > same FFT is used in Flint), here [1]. > > [1] https://github.com/wbhart/flint2/blob/trunk/fft/README > > On 25 April 2018 at 10:18, Bill Hart <goodwillh...@googlemail.com> wrote: > >> Hi, >> >> We don't use quite this FFT in MPIR. The best reference on the FFT that I >> know of is by Joerg Arndt. >> >> https://www.jjj.de/fxt/fxtbook.pdf >> >> It doesn't cover the FFT we use, but it gives you the basic ideas that >> are necessary to understand it. >> >> Bill. >> >> On 25 April 2018 at 03:51, Tanushree Banerjee < >> banerjee.tanushre...@gmail.com> wrote: >> >>> I was going through the documentation of MPIR ( >>> http://mpir.org/mpir-3.0.0.pdf), specially section 16.1.5 where they >>> refer to the use of Fermat's style FFT. I tried to follow the reference but >>> couldn't quite understand this technique, can anyone explain to me how this >>> Fermat's FFT work? I don't understand how and why the modulus changes from >>> (2^N+1) to (2M+k+3) using FFT-k splitting? If there is some documentation >>> on this with better explanation it would be very helpful! Thanks a lot for >>> your patience >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "mpir-devel" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to mpir-devel+unsubscr...@googlegroups.com. >>> To post to this group, send email to mpir-devel@googlegroups.com. >>> Visit this group at https://groups.google.com/group/mpir-devel. >>> For more options, visit https://groups.google.com/d/optout. >>> >> >> > -- > You received this message because you are subscribed to the Google Groups > "mpir-devel" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to mpir-devel+unsubscr...@googlegroups.com. > To post to this group, send email to mpir-devel@googlegroups.com. > Visit this group at https://groups.google.com/group/mpir-devel. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "mpir-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to mpir-devel+unsubscr...@googlegroups.com. To post to this group, send email to mpir-devel@googlegroups.com. Visit this group at https://groups.google.com/group/mpir-devel. For more options, visit https://groups.google.com/d/optout.
