udiv_qr_3by2 vs divappr

Torbjörn Granlund tg at gmplib.org
Mon Apr 30 09:00:50 UTC 2018

nisse at lysator.liu.se (Niels Möller) writes:

  Good idea. Is there an easy way to use asl.h?

I cannot recall what it takes, I never finished simple integration of
it.  (The idea is to have some --enable-asl=4 configure switch.)

I think using ABI=32 for now is yoor best option.

  Main use is schoolbook division, where the quadratic term is unchanged.
  So we can't expect any huge improvements.

Except when the linear term dominates, e.g., when the divisor is small...

  Using divappr_2 instead of udiv_qr_3by2 might give a small improvement
  of the linear term, this is still unclear. Quotient approximation gets
  slightly easier, and the update of the high limbs of the partial remainder
  will be done by submul_1 instead of explicit subtractions and carry
  logic in the C code.

So the submul_1 size agument will increase slightly?

  I think main benefit is that it will make unnormalized schoolbook
  division, without upfront normalization, easier to implement.
  Eliminating the bignum normalization shifts should give a good speedup
  for divisions u/d, where u and d are large, but the quotient is just one
  or a few limbs. And reduce need for temporary allocation as well.

That'd be very good!

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list