<div dir="ltr">Can it be a first step?<div><a href="http://reviews.llvm.org/D8770">http://reviews.llvm.org/D8770</a></div><div><br></div><div>- Paweł<br><br><div class="gmail_quote">On Sun, Mar 22, 2015 at 5:35 PM Joerg Sonnenberger <<a href="mailto:joerg@britannica.bec.de">joerg@britannica.bec.de</a>> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Sun, Mar 22, 2015 at 03:18:14PM +0000, Paweł Bylica wrote:<br>
> On Sun, Mar 22, 2015 at 5:57 AM Joerg Sonnenberger <<a href="mailto:joerg@britannica.bec.de" target="_blank">joerg@britannica.bec.de</a>><br>
> wrote:<br>
><br>
> > On Fri, Mar 20, 2015 at 08:06:11PM -0700, Tim Northover wrote:<br>
> > > > mul can be inlined easily if necessary for arbitrary sizes, but div is<br>
> > very expensive.<br>
> > ><br>
> > > Shall I file a bug for "implement FFT in LLVM"?<br>
> ><br>
> > I didn't say it is the most efficient algorithm :) That's why I asked<br>
> > about the purpose.<br>
> ><br>
> > Joerg<br>
> ><br>
><br>
>  Can you suggest an algorithm and implementation then?<br>
<br>
For short multi-word multiplications, school book approach works fine.<br>
For medium sizes problems, Karatsuba or Toom-Cook is better. For truely<br>
larger problems, it boils down to FFT. Of course, all this needs careful<br>
benchmarking if you want to select a specific one.<br>
<br>
Joerg<br>
<br>
______________________________<u></u>_________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu" target="_blank">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/<u></u>mailman/listinfo/llvmdev</a><br>
</blockquote></div></div></div>