middle products

[Niels Möller]

David Harvey <dmharvey at cims.nyu.edu> writes:

> I have written up some work I've been doing on middle products,  please see
>
> http://cims.nyu.edu/~harvey/mulmid/

After a first quick reading, it seems that the executive summary is
that middle-product is a more efficient primitive than low-product (at
least in Schoolbook and Karatsuba range, the ratio compared to a full
product is constant). While for mullo, the work saved is less
significant the larger n is.

The primitives needed (adderr, adderr2, and your variant of bdiv) are
somewhat unintuitive, but I think I understand what they're doing.
It's an interesting puzzle when you not only have to fit the pieces
together, but you must also determine what the right shapes are...

You say that for larger sizes, the middle product can be computed
using fft-multiplication with wraparound. Can you say something more
about how this is done? My understanding so far is that wraparound is
useful only when one part of the product is known, and you you want to
know the rest, which is the case for applications to newton-iteration
and the like. But for a general mulmid, no part of the product is
known a-priori.

In the FFT range, will it still hold that the time for MP_n will be
almost the same as for a full n × n multiply, or what's the expected
ratio?

Regards,
/Niels