udiv_qr_3by2 vs divappr

[Torbjörn Granlund]

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,
  			  0xfffffffffffffff8ULL);
    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
  tests:

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?


-- 
Torbjörn
Please encrypt, key id 0xC8601622