bdiv vs redc

[Torbjorn Granlund]

Torbjorn Granlund <tg at gmplib.org> writes:

    iterate nn-dn times
      q = np[0] * dinv
      hi = mpn_addmul_1 (np, dp, dn, q)
      hi += cy
      cy = hi < cy		// can this be true?
      hi += np[dn]
      cy2 += hi < np[dn]
      np[dn] = hi
      np += 1;

I wrote a possible start for mpn_sbpi1_bdiv_r using the above idea.
It is attached.

As currently writtem this is a pure generalisation of redc_1; the
dividend and divisor have separate sizes.  The remainder is of redc_1
type, with carry returned, not borrow.

I suspect this will beat both previous styles of schoolbook Hensel
division, in particular when written in assembly.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: sbpi1_bdiv_r.c
Type: application/octet-stream
Size: 1747 bytes
Desc: not available
URL: <http://gmplib.org/list-archives/gmp-devel/attachments/20120628/9844ff95/attachment.obj>
-------------- next part --------------

-- 
Torbj?rn