middle products

[Niels Möller]

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

> It computes an approximation to B^(2n) / d, where d is the n-limb input.
>
> I profiled it against mpn_tdiv_qr in GMP 4.3.1. I don't know my way
> around all the new division code in GMP, I expect something in there
> can beat mpn_tdiv_qr.

Relevant functions in the new division code are

  mpn_dc_div_qr: computes both quotient and remainder

  mpn_dc_divappr_q: computes approximate quotient

  mpn_dc_div_q: computes approximate quotient and somehow corercts it
               if needed

I think at least mpn_dc_div_qr should run at about the same time as
the old mpn_tdiv_qr, since both use the same Burnikel-Ziegler
divide-and-conquer algorithm.

Anyway, it looks promising with almost a factor 2 speedup!

/Niels