[LLVMdev] Mul & div support for wider-than-legal types
joerg at britannica.bec.de
Sun Mar 22 09:33:21 PDT 2015
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>
> > 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.
More information about the llvm-dev