GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing github.com — bpo-45876: Correctly rounded stdev() and pstdev() for the Decimal case by rhettinger · Pull Request #29828 · python/cpython

Conversation

rhettinger commented Nov 29, 2021 •

edited by bedevere-bot

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

Contributor

https://bugs.python.org/issue45876

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

rhettinger and others added 25 commits

March 15, 2021 21:12


          Merge pull request #1 from python/master

bbd2da9

Update to 15 March


          Merge branch 'master' of github.com:python/cpython

74bdf1b


          Merge branch 'master' of github.com:python/cpython

6c53f1a

a487c4f

Merge branch 'master' of github.com:python/cpython

eb56423

Merge branch 'master' of github.com:python/cpython

cc7ba06

Merge branch 'master' of github.com:python/cpython

d024dd0

Merge branch 'master' of github.com:python/cpython


          merge

b10f912

Merge branch 'main' of github.com:python/cpython into main


          merge

fb6744d

Merge branch 'main' of github.com:python/cpython


          Merge branch 'main' of github.com:python/cpython

7f21a1c


          Merge branch 'main' of github.com:rhettinger/cpython

7da42d4


          Merge branch 'main' of github.com:python/cpython

e31757b


          Merge branch 'main' of github.com:python/cpython

f058a6f


          Merge branch 'main' of github.com:python/cpython

1fc29bd


          Merge branch 'main' of github.com:python/cpython

e5c0184


          Merge branch 'main' of github.com:python/cpython

3c86ec1


          Merge branch 'main' of github.com:rhettinger/cpython

96675e4


          Merge branch 'main' of github.com:python/cpython

de558c6


          Merge branch 'main' of github.com:python/cpython

418a07f


          Merge branch 'main' of github.com:python/cpython

ea23a8b


          Merge branch 'main' of github.com:python/cpython

ba248b7


          Correctly rounded stdev results for Decimal inputs

037b5fe


          Whitespace

f5c091c


          Rename the functions consistently

70cdade


          Improve comment

82dbec6

rhettinger added the skip news label

Nov 29, 2021

the-knights-who-say-ni added the CLA signed label

Nov 29, 2021

bedevere-bot added the awaiting core review label

Nov 29, 2021

rhettinger requested review from mdickinson and tim-one

November 29, 2021 03:25

bedevere-bot commented Nov 29, 2021

Copy link

Copy Markdown

🤖 New build scheduled with the buildbot fleet by @rhettinger for commit 1a6c58d 🤖

If you want to schedule another build, you need to add the ":hammer: test-with-buildbots" label again.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label

Nov 29, 2021

rhettinger added 5 commits

November 29, 2021 00:43


          Replace Fraction arithmetic with integer arithmetic

b2385b0


          Add spacing between terms

594ea27


          Fix type annotation


          Return a Decimal zero when the numerator is zero

a09e3c4


          Remove unused import

152ed3f

rhettinger added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label

Nov 29, 2021

bedevere-bot commented Nov 29, 2021

Copy link

Copy Markdown

🤖 New build scheduled with the buildbot fleet by @rhettinger for commit 152ed3f 🤖

If you want to schedule another build, you need to add the ":hammer: test-with-buildbots" label again.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label

Nov 29, 2021

rhettinger added 2 commits

November 29, 2021 09:12


          Factor lhs of inequality. Rename helper function for consistency.

80371c1


          Add comment for future work.

1c86e7c

mdickinson reviewed

Nov 29, 2021

View reviewed changes

Comment thread

Lib/statistics.py Outdated


		def _decimal_sqrt_of_frac(n: int, m: int) -> Decimal:
		"""Square root of n/m as a float, correctly rounded."""
		# Premise: For decimal, computing (n/m).sqrt() can be off by 1 ulp.

mdickinson Nov 29, 2021 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Unfortunately, while the corresponding result is true for binary floating-point, it's not true for decimal floating-point: for decimal, the error can be more than 1 ulp.

Example using 3-digit precision:

>>> from decimal import Decimal, getcontext
>>> n, m = 209, 20
>>> getcontext().prec = 3
>>> (Decimal(n) / Decimal(m)).sqrt()
Decimal('3.22')
>>> getcontext().prec = 10
>>> (Decimal(n) / Decimal(m)).sqrt()
Decimal('3.232645975')

The correctly-rounded value here is around 1.265 ulps away, at 3.232645975...

However, I believe that one can show that the worst case error is at most 1.3ulp (actually 0.5 + sqrt(10)/4 = 1.290569... ulps), in which case it remains true that the correctly-rounded result will always be one of root, root.next_plus() or root.next_minus().

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

mdickinson Nov 29, 2021

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Self-correction: I guess "off by <= 1ulp" is accurate, so long as it's clear that we're talking about the maximum difference between the computed value and the correctly-rounded value. I was thinking in terms of the max difference between the computed value and the true mathematical value.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

rhettinger Nov 29, 2021

Copy link

Copy Markdown

Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Updating the comment.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

mdickinson reviewed

Nov 29, 2021

View reviewed changes

Comment thread

Lib/statistics.py

		"""Square root of n/m as a float, correctly rounded."""
		# Premise: For decimal, computing (n/m).sqrt() can be off by 1 ulp.
		# Method: Check the result, moving up or down a step if needed.
		if n <= 0:

mdickinson Nov 29, 2021

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should we be checking m here rather than n? It looks as though we multiply through by m below, so we need m to be positive for the inequalities to work.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

rhettinger Nov 29, 2021

Copy link

Copy Markdown

Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The case where m is zero is handled before the inequality test. The Decimal(n) / Decimal(m) step raises DivisionByZero which is a subclass of ZeroDivisionError. There is a test for this case.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

mdickinson Nov 30, 2021 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes, I was really more worried about the case m negative, not m zero. It seems more natural to have the normalization step n, m = -n, -m ensure that the denominator is positive than that the numerator is positive: right now, we're effectively converting -2 / 5 to 2 / (-5), and what we care about below for the maths to work is that m is positive, not that n is positive: you're implicitly converting the inequality n / m > ((root + plus) / 2) ** 2 to the inequality n > ((root + plus) / 2)**2 * m, and that conversion is only valid if m is positive.

It doesn't matter, because if just one of n and m is negative then the (Decimal(n) / Decimal(m)).sqrt() step will fail (except in the case of really extreme m where the division rounds from something tiny and negative to negative zero); it just seems like a surprising choice and for me at least it made the code harder to read and reason about.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

mdickinson reviewed

Nov 29, 2021

View reviewed changes

Comment thread

Lib/statistics.py Outdated



		def _decimal_sqrt_of_frac(n: int, m: int) -> Decimal:
		"""Square root of n/m as a float, correctly rounded."""

mdickinson Nov 29, 2021

Copy link

Copy Markdown

Member

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

copypasta: "as a float"

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

rhettinger Nov 29, 2021

Copy link

Copy Markdown

Contributor Author

There was a problem hiding this comment.

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fixed.

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions

rhettinger added 4 commits

November 29, 2021 17:40


          Fix typo in docstring. Refine wording in comment.

0684fac


          Add more detail to the comment about numerator and denominator sizes

8b5e377


          Improve variable name

d11d567


          Avoid double rounding in test code

309cb0a

rhettinger added the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label

Nov 30, 2021

bedevere-bot commented Nov 30, 2021

Copy link

Copy Markdown

🤖 New build scheduled with the buildbot fleet by @rhettinger for commit 309cb0a 🤖

If you want to schedule another build, you need to add the ":hammer: test-with-buildbots" label again.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

bedevere-bot removed the 🔨 test-with-buildbots Test PR w/ buildbots; report in status section label

Nov 30, 2021

rhettinger merged commit a39f46a into python:main

Dec 1, 2021

bedevere-bot removed the awaiting core review label

Dec 1, 2021

rhettinger deleted the stdev_deci_sqrt branch

December 1, 2021 00:20

shihai1991 added a commit to shihai1991/cpython that referenced this pull request

Dec 1, 2021


          Merge branch 'main' into bpo_44133

6edb6f5

* main: (21 commits)
  bpo-45876:  Have stdev() also use decimal specific square root. (pythonGH-29869)
  bpo-45876:  Correctly rounded stdev() and pstdev() for the Decimal case (pythonGH-29828)
  bpo-45711: Change exc_info related APIs to derive type and traceback from the exception instance (pythonGH-29780)
  bpo-30533:Add function inspect.getmembers_static that does not call properties or dynamic properties. (python#20911)
  bpo-45476: Disallow using asdl_seq_GET() as l-value (pythonGH-29866)
  bpo-45476: Add _Py_RVALUE() macro (pythonGH-29860)
  bpo-33381: [doc] strftime's %f option may pad zeros on the left or the right (pythonGH-29801)
  Fix EncodingWarning in Tools/freeze/test/freeze.py (pythonGH-29742)
  no-issue: remove unused import from test_graphlib.py (pythonGH-29853)
  bpo-45931: Prevent Directory.Build.props/targets from leaking from directories above the repo when building on Windows (pythonGH-29854)
  bpo-45653: fix test_embed on windows (pythonGH-29814)
  bpo-45917: Add math.exp2() method - return 2 raised to the power of x (pythonGH-29829)
  bpo-43905: Expand dataclasses.astuple() and asdict() docs (pythonGH-26154)
  bpo-44391: Remove unused argument from a varargs call. (pythonGH-29843)
  bpo-45881: configure --with-freeze-module --with-build-python (pythonGH-29835)
  bpo-45847: PY_STDLIB_MOD_SIMPLE now checks py_stdlib_not_available (pythonGH-29844)
  bpo-45828: Use unraisable exceptions within sqlite3 callbacks (FH-29591)
  bpo-40280: Emscripten systems use .wasm suffix by default (pythonGH-29842)
  bpo-45723: Sort the grand AC_CHECK_HEADERS check (pythonGH-29846)
  bpo-45847: Make socket module conditional (pythonGH-29769)
  ...

shihai1991 added a commit to shihai1991/cpython that referenced this pull request

Dec 1, 2021


          Merge branch 'main' into bpo_44133

b71b124

* main: (21 commits)
  bpo-45876:  Have stdev() also use decimal specific square root. (pythonGH-29869)
  bpo-45876:  Correctly rounded stdev() and pstdev() for the Decimal case (pythonGH-29828)
  bpo-45711: Change exc_info related APIs to derive type and traceback from the exception instance (pythonGH-29780)
  bpo-30533:Add function inspect.getmembers_static that does not call properties or dynamic properties. (python#20911)
  bpo-45476: Disallow using asdl_seq_GET() as l-value (pythonGH-29866)
  bpo-45476: Add _Py_RVALUE() macro (pythonGH-29860)
  bpo-33381: [doc] strftime's %f option may pad zeros on the left or the right (pythonGH-29801)
  Fix EncodingWarning in Tools/freeze/test/freeze.py (pythonGH-29742)
  no-issue: remove unused import from test_graphlib.py (pythonGH-29853)
  bpo-45931: Prevent Directory.Build.props/targets from leaking from directories above the repo when building on Windows (pythonGH-29854)
  bpo-45653: fix test_embed on windows (pythonGH-29814)
  bpo-45917: Add math.exp2() method - return 2 raised to the power of x (pythonGH-29829)
  bpo-43905: Expand dataclasses.astuple() and asdict() docs (pythonGH-26154)
  bpo-44391: Remove unused argument from a varargs call. (pythonGH-29843)
  bpo-45881: configure --with-freeze-module --with-build-python (pythonGH-29835)
  bpo-45847: PY_STDLIB_MOD_SIMPLE now checks py_stdlib_not_available (pythonGH-29844)
  bpo-45828: Use unraisable exceptions within sqlite3 callbacks (FH-29591)
  bpo-40280: Emscripten systems use .wasm suffix by default (pythonGH-29842)
  bpo-45723: Sort the grand AC_CHECK_HEADERS check (pythonGH-29846)
  bpo-45847: Make socket module conditional (pythonGH-29769)
  ...

Reviewers

tim-one

Awaiting requested review from tim-one

stevendaprano

Awaiting requested review from stevendaprano

1 more reviewer

mdickinson

mdickinson left review comments

Reviewers whose approvals may not affect merge requirements

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

skip news

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Uh oh!

There was an error while loading. Please reload this page.

4 participants

Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

GeezerVison

Conversation

rhettinger commented Nov 29, 2021 • edited by bedevere-bot Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

bedevere-bot commented Nov 29, 2021

Uh oh!

bedevere-bot commented Nov 29, 2021

Uh oh!

mdickinson Nov 29, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mdickinson Nov 29, 2021

Choose a reason for hiding this comment

Uh oh!

rhettinger Nov 29, 2021

Choose a reason for hiding this comment

Uh oh!

mdickinson Nov 29, 2021

Choose a reason for hiding this comment

Uh oh!

rhettinger Nov 29, 2021

Choose a reason for hiding this comment

Uh oh!

mdickinson Nov 30, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

mdickinson Nov 29, 2021

Choose a reason for hiding this comment

Uh oh!

rhettinger Nov 29, 2021

Choose a reason for hiding this comment

Uh oh!

bedevere-bot commented Nov 30, 2021

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

rhettinger commented Nov 29, 2021 •

edited by bedevere-bot

Loading

Uh oh!

There was an error while loading. Please reload this page.

mdickinson Nov 29, 2021 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.

mdickinson Nov 30, 2021 •

edited

Loading

Uh oh!

There was an error while loading. Please reload this page.