On Sun, Mar 22, 2015 at 5:57 AM Joerg Sonnenberger <joerg at britannica.bec.de> wrote:> On Fri, Mar 20, 2015 at 08:06:11PM -0700, Tim Northover wrote: > > > mul can be inlined easily if necessary for arbitrary sizes, but div is > very expensive. > > > > Shall I file a bug for "implement FFT in LLVM"? > > I didn't say it is the most efficient algorithm :) That's why I asked > about the purpose. > > Joerg >Can you suggest an algorithm and implementation then? -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150322/e2acadd4/attachment.html>
Joerg Sonnenberger
2015-Mar-22 16:33 UTC
[LLVMdev] Mul & div support for wider-than-legal types
On Sun, Mar 22, 2015 at 03:18:14PM +0000, Paweł Bylica wrote:> On Sun, Mar 22, 2015 at 5:57 AM Joerg Sonnenberger <joerg at britannica.bec.de> > wrote: > > > On Fri, Mar 20, 2015 at 08:06:11PM -0700, Tim Northover wrote: > > > > mul can be inlined easily if necessary for arbitrary sizes, but div is > > very expensive. > > > > > > Shall I file a bug for "implement FFT in LLVM"? > > > > I didn't say it is the most efficient algorithm :) That's why I asked > > about the purpose. > > > > Joerg > > > > Can you suggest an algorithm and implementation then?For short multi-word multiplications, school book approach works fine. For medium sizes problems, Karatsuba or Toom-Cook is better. For truely larger problems, it boils down to FFT. Of course, all this needs careful benchmarking if you want to select a specific one. Joerg
Can it be a first step? http://reviews.llvm.org/D8770 - Paweł On Sun, Mar 22, 2015 at 5:35 PM Joerg Sonnenberger <joerg at britannica.bec.de> wrote:> On Sun, Mar 22, 2015 at 03:18:14PM +0000, Paweł Bylica wrote: > > On Sun, Mar 22, 2015 at 5:57 AM Joerg Sonnenberger < > joerg at britannica.bec.de> > > wrote: > > > > > On Fri, Mar 20, 2015 at 08:06:11PM -0700, Tim Northover wrote: > > > > > mul can be inlined easily if necessary for arbitrary sizes, but > div is > > > very expensive. > > > > > > > > Shall I file a bug for "implement FFT in LLVM"? > > > > > > I didn't say it is the most efficient algorithm :) That's why I asked > > > about the purpose. > > > > > > Joerg > > > > > > > Can you suggest an algorithm and implementation then? > > For short multi-word multiplications, school book approach works fine. > For medium sizes problems, Karatsuba or Toom-Cook is better. For truely > larger problems, it boils down to FFT. Of course, all this needs careful > benchmarking if you want to select a specific one. > > Joerg > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150401/95e32e22/attachment.html>