[LLVMdev] Mul & div support for wider-than-legal types

[Joerg Sonnenberger]

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