Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[Minor] bug in integer true division algorithm #69790

Closed
mdickinson opened this issue Nov 12, 2015 · 5 comments
Closed

[Minor] bug in integer true division algorithm #69790

mdickinson opened this issue Nov 12, 2015 · 5 comments
Assignees
Labels
interpreter-core (Objects, Python, Grammar, and Parser dirs) type-bug An unexpected behavior, bug, or error

Comments

@mdickinson
Copy link
Member

BPO 25604
Nosy @mdickinson, @vstinner, @serhiy-storchaka

Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

Show more details

GitHub fields:

assignee = 'https://github.com/mdickinson'
closed_at = <Date 2016-08-21.10:01:24.275>
created_at = <Date 2015-11-12.08:44:45.098>
labels = ['interpreter-core', 'type-bug']
title = '[Minor] bug in integer true division algorithm'
updated_at = <Date 2016-08-21.10:01:24.273>
user = 'https://github.com/mdickinson'

bugs.python.org fields:

activity = <Date 2016-08-21.10:01:24.273>
actor = 'mark.dickinson'
assignee = 'mark.dickinson'
closed = True
closed_date = <Date 2016-08-21.10:01:24.275>
closer = 'mark.dickinson'
components = ['Interpreter Core']
creation = <Date 2015-11-12.08:44:45.098>
creator = 'mark.dickinson'
dependencies = []
files = []
hgrepos = []
issue_num = 25604
keywords = []
message_count = 5.0
messages = ['254523', '254531', '273283', '273287', '273288']
nosy_count = 4.0
nosy_names = ['mark.dickinson', 'vstinner', 'python-dev', 'serhiy.storchaka']
pr_nums = []
priority = 'low'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue25604'
versions = ['Python 2.7', 'Python 3.5', 'Python 3.6']

@mdickinson
Copy link
Member Author

There's a harmless but annoying (for code readers) bug in the code for true division of (long) integers. In long_true_divide in [Objects/longobject.c](https://github.com/python/cpython/blob/main/Objects/longobject.c), we have the following code for manipulating the bits of a 55- or 56-bit long to get something that will be exactly representable as a float:

/* The number of extra bits that have to be rounded away. */
extra_bits = MAX(x_bits, DBL_MIN_EXP - shift) - DBL_MANT_DIG;
assert(extra_bits == 2 || extra_bits == 3);

/* Round by directly modifying the low digit of x. */
mask = (digit)1 << (extra_bits - 1);
low = x->ob_digit[0] | inexact;
if (low & mask && low & (3*mask-1))
    low += mask;
x->ob_digit[0] = low & ~(mask-1U);

/* Convert x to a double dx; the conversion is exact. */
[...]

The last code line above is supposed to be masking out all the bits that we don't want to keep. Instead, it's masking out all but one of those bits. The line

x->ob_digit[0] = low & ~(mask-1U);

should be replaced with

x->ob_digit[0] = low & ~(2*mask-1U);

As it stands, the comment about the conversion to double being exact is false. (I've verified this by converting x both to a 64-bit unsigned integer and to a double and checking that the integer and double don't always match in value; with the fix above, they do.)

I don't *think* this bug actually affects the output on any platform whose arithmetic and ldexp functions do correct rounding with round-ties-to-even: the extra bit will always get rounded away (in the correct direction) by either the conversion to float (for the non-subnormal case) or by the ldexp operation (for the subnormal case). Still, the bug makes the code a bit more susceptible to platform arithmetic quirks.

@mdickinson mdickinson self-assigned this Nov 12, 2015
@mdickinson mdickinson added interpreter-core (Objects, Python, Grammar, and Parser dirs) type-bug An unexpected behavior, bug, or error labels Nov 12, 2015
@serhiy-storchaka
Copy link
Member

Correct.

@python-dev
Copy link
Mannequin

python-dev mannequin commented Aug 21, 2016

New changeset b9e12ca6fdb6 by Mark Dickinson in branch 'default':
Issue bpo-25604: Fix minor bug in integer true division, which could
https://hg.python.org/cpython/rev/b9e12ca6fdb6

@python-dev
Copy link
Mannequin

python-dev mannequin commented Aug 21, 2016

New changeset 370bbeba21b3 by Mark Dickinson in branch '2.7':
Issue bpo-25604: Fix bug in integer true division that could have resulted in off-by-one-ulp results in unusual cases.
https://hg.python.org/cpython/rev/370bbeba21b3

@mdickinson
Copy link
Member Author

Fixed for 2.7 and 3.6. I don't think it's worth backporting the fix to 3.5 without evidence of actual incorrect results arising from this bug.

@ezio-melotti ezio-melotti transferred this issue from another repository Apr 10, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
interpreter-core (Objects, Python, Grammar, and Parser dirs) type-bug An unexpected behavior, bug, or error
Projects
None yet
Development

No branches or pull requests

2 participants