udiv_qr_3by2 vs divappr

Torbjörn Granlund tg at gmplib.org
Sun Apr 29 12:21:38 UTC 2018

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

  The first failure was for an input with n2 == d1, n1 == d1-1. 

  static void test_divappr_2(void)
    mp_limb_t q = divappr_2(0x8000000000000001ULL, 0xffffffffbfffffffULL,
  			  0x8000000000000001ULL, 0xffffffffc0000000ULL,
    ASSERT_ALWAYS (q != 0);

  Then quotient should be B-1, but divappr tried to return the one of
  quotient B, which then fails due to overflow. The below variant passes

A quick comment: I'd suggest that you test this with 32-bit limbs, as
the corner cases tend to be a fixed number irrespective of limb length,
meaning that the likelyhood of hitting a corner decreases with limb
size.  (You could even use asl.h, perhaps.)

As you mentioned, it's been a while since we last looked into these
things.  I cannot recall what exact operations we use today.  What
performance improvements do you envision?

Please encrypt, key id 0xC8601622

More information about the gmp-devel mailing list