classification
Title: Expose round-to-nearest division algorithm in Objects/longobject.c
Type: enhancement Stage: resolved
Components: Interpreter Core Versions: Python 3.2
process
Status: closed Resolution: accepted
Dependencies: Superseder:
Assigned To: mark.dickinson Nosy List: belopolsky, mark.dickinson
Priority: normal Keywords: patch

Created on 2010-05-25 12:56 by mark.dickinson, last changed 2010-05-26 16:03 by mark.dickinson. This issue is now closed.

Files
File name Uploaded Description Edit
div_nearest.patch mark.dickinson, 2010-05-25 12:55
div_nearest2.patch mark.dickinson, 2010-05-25 18:30
Messages (6)
msg106431 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-05-25 12:55
The implementation of 'round' for Python integers uses a round-to-nearest form of divmod:  a, b -> q, r, where q is the nearest integer to a / b and r = a - b*q.

This form of divmod would be useful elsewhere.  In particular, it's currently needed for implementing multiplication and division of timedeltas by a float:  see issue 1289118  .

This patch exposes the operation to Python C code as _PyLong_Divmod_Near, and refactors long_round to use this operation.
msg106444 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2010-05-25 16:11
Just a few nitpicks on the patch (in increasing pickiness):

1. Any reason to prefer PyTuple_SetItem to PyTuple_SET_ITEM at the end of _PyLong_Divmod_Near?   You are filling a brand new tuple, so PyTuple_SET_ITEM seems to be more appropriate.

2. temp = (quo_is_neg ? long_add : long_sub)(..) is clever, but IMO is less readable than 

if (quo_is_neg)
   temp = long_add(..)
else
   temp = long_sub(..)

The later form may also be more optimization friendly, particularly if compiler wants to inline static long_add or long_sub.

3. Given that arguments are named 'a' and 'b' it is a bit confusing to have local variable c of a different type.  I think 'cmp' would be a better choice.

4. I see that you removed a comment that displays round() implemented in python.  I think it would be helpful to preserve it for documentation and testing purposes even though the actual algorithm is slightly different.  As long as the results are the same, it is helpful to have reference python code.

5. Similarly to #4, having python implementation of divmod_near() displayed somewhere will be helpful.
msg106462 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-05-25 18:30
Thanks for reviewing!

Updated patch, that addresses points 1-3.  For 4, there's no need for the old code, since "self - divmod_near(self, 10**-n)[1]" is enough.  And I didn't like the old algorithm anyway;  the new one is more straightforward.  For 5, I've added a Python version of divmod_near to the comments.
msg106491 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2010-05-25 23:11
Looking at

    Py_DECREF(one);
 
    result = PyTuple_New(2);
    if (result == NULL)
        goto error;
..
  error:
    Py_XDECREF(one);


If PyTuple_New fails, wouldn't it result in one being DECREF's twice?
msg106514 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-05-26 08:28
Ah, good point.  I knew there was a reason I didn't like Py_XDECREF.
I'll fix this and then apply this patch tonight.
msg106540 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2010-05-26 16:03
Committed (with the DECREF(one) fix) in r81541.
History
Date User Action Args
2010-05-26 16:03:46mark.dickinsonsetstatus: open -> closed
messages: + msg106540

components: + Interpreter Core
resolution: accepted
stage: resolved
2010-05-26 08:28:14mark.dickinsonsetmessages: + msg106514
2010-05-25 23:11:39belopolskysetmessages: + msg106491
2010-05-25 18:30:43mark.dickinsonsetfiles: + div_nearest2.patch

messages: + msg106462
2010-05-25 16:11:05belopolskysetnosy: + belopolsky
messages: + msg106444
2010-05-25 12:56:01mark.dickinsoncreate