py/mpz: Simplify handling of borrow and quo adjustment in mpn_div.

The motivation behind this patch is to remove unreachable code in mpn_div.
This unreachable code was added some time ago in
9a21d2e070c9ee0ef2c003f3a668e635c6ae4401, when a loop in mpn_div was copied
and adjusted to work when mpz_dig_t was exactly half of the size of
mpz_dbl_dig_t (a common case).  The loop was copied correctly but it wasn't
noticed at the time that the final part of the calculation of num-quo*den
could be optimised, and hence unreachable code was left for a case that
never occurred.

The observation for the optimisation is that the initial value of quo in
mpn_div is either exact or too large (never too small), and therefore the
subtraction of quo*den from num may subtract exactly enough or too much
(but never too little).  Using this observation the part of the algorithm
that handles the borrow value can be simplified, and most importantly this
eliminates the unreachable code.

The new code has been tested with DIG_SIZE=3 and DIG_SIZE=4 by dividing all
possible combinations of non-negative integers with between 0 and 3
(inclusive) mpz digits.

1 files changed, 4 insertions, 0 deletions

diff --git a/py/mpz.h b/py/mpz.h
index e2d0c30aa..3c36cac66 100644
--- a/py/mpz.h
+++ b/py/mpz.h
@@ -55,18 +55,22 @@
 #endif
 
 #if MPZ_DIG_SIZE > 16
+#define MPZ_DBL_DIG_SIZE (64)
 typedef uint32_t mpz_dig_t;
 typedef uint64_t mpz_dbl_dig_t;
 typedef int64_t mpz_dbl_dig_signed_t;
 #elif MPZ_DIG_SIZE > 8
+#define MPZ_DBL_DIG_SIZE (32)
 typedef uint16_t mpz_dig_t;
 typedef uint32_t mpz_dbl_dig_t;
 typedef int32_t mpz_dbl_dig_signed_t;
 #elif MPZ_DIG_SIZE > 4
+#define MPZ_DBL_DIG_SIZE (16)
 typedef uint8_t mpz_dig_t;
 typedef uint16_t mpz_dbl_dig_t;
 typedef int16_t mpz_dbl_dig_signed_t;
 #else
+#define MPZ_DBL_DIG_SIZE (8)
 typedef uint8_t mpz_dig_t;
 typedef uint8_t mpz_dbl_dig_t;
 typedef int8_t mpz_dbl_dig_signed_t;