Skip to content
Snippets Groups Projects
  • Damien George's avatar
    9766fddc
    py/mpz: Simplify handling of borrow and quo adjustment in mpn_div. · 9766fddc
    Damien George authored
    The motivation behind this patch is to remove unreachable code in mpn_div.
    This unreachable code was added some time ago in
    9a21d2e0, 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.
    9766fddc
    History
    py/mpz: Simplify handling of borrow and quo adjustment in mpn_div.
    Damien George authored
    The motivation behind this patch is to remove unreachable code in mpn_div.
    This unreachable code was added some time ago in
    9a21d2e0, 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.