bdiv vs redc

Torbjorn Granlund tg at
Thu Jun 28 22:05:13 CEST 2012

Torbjorn Granlund <tg at> 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: <>
-------------- next part --------------


More information about the gmp-devel mailing list