I see. I know that standard Schoenhage-Strassen algorithm. has the
complexity of O(n. log(n). log(log(n)), this algorithm also has the same
complexity then?
I was confused as in the GMP and MPIR documents, it was mentioned that FFT
based multiplication will have O(n^{k/(k-2)}) complexity
Thanks and regards
Tanushree Banerjee,
Electrical and Computer Engineering, Graduate Student
University of Waterloo
On Wed, Apr 25, 2018 at 3:28 PM, 'Bill Hart' via mpir-devel <
mpir-devel@googlegroups.com> wrote:
>
>
> On 25 April 2018 at 19:35, Tanushree Banerjee <banerjee.tanushree10@gmail.
> com> wrote:
>
>> Thanks @Bill Hart . I was going through the second link. So what is the
>> complexity of this algorithm ?
>>
>
> It's the same complexity as the standard Schoenhage-Strassen algorithm.
>
>
>> (I have a jpeg file attached with FFT multiplication algorithm snapshot,
>> I think this is not used in the mpir implementation, isnt it? )
>>
>
> The algorithm used in MPIR is much more sophisticated. It would not be
> easy to write in pseudocode and I would not like to attempt it.
>
> --
> 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.
