[issue23522] Misleading note in Statistics module documentation
Change by Mark Dickinson : -- nosy: +mark.dickinson ___ Python tracker <https://bugs.python.org/issue23522> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue23522] Misleading note in Statistics module documentation
Mark Dickinson added the comment: > "The mean is strongly affected by outliers and is not necessarily a typical > example of the data points. For a more robust, although less efficient, > measure of central tendency, see median()" That wording sounds fine to me. I don't think we can reasonably expect to hear from Jake again, but from my understanding of his post, this addresses his concerns. FWIW, I share those concerns. My brain can't parse "robust estimator for central location", because the term "estimator" has a precise and well-defined meaning in (frequentist) statistics, and what I expect to see after "estimator for" is a description of a parameter of a statistical model - as in for example "estimator for the population mean", or "estimator for the Weibull shape parameter". "central location" doesn't really fit in that slot. > How do we feel about linking to Wikipedia? I can't think of any good reason not to. We have plenty of other external links in the docs, and the Wikipedia links are probably at lower risk of becoming stale than most of the others. -- ___ Python tracker <https://bugs.python.org/issue23522> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue23522] Misleading note in Statistics module documentation
Change by Mark Dickinson : -- pull_requests: +28390 stage: -> patch review pull_request: https://github.com/python/cpython/pull/30174 ___ Python tracker <https://bugs.python.org/issue23522> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue23522] Misleading note in Statistics module documentation
Mark Dickinson added the comment: Steven: I've made a PR at https://github.com/python/cpython/pull/30174. Does this match what you had in mind? -- ___ Python tracker <https://bugs.python.org/issue23522> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue45995] string formatting: normalize negative zero
Change by Mark Dickinson : -- assignee: -> mark.dickinson ___ Python tracker <https://bugs.python.org/issue45995> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue45995] string formatting: normalize negative zero
Mark Dickinson added the comment: Thanks, John. I should have time to review within the next week or so. -- ___ Python tracker <https://bugs.python.org/issue45995> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Mark Dickinson added the comment: > we can get faster code by using a small (3Kb) table of factorial logarithms The problem here is that C gives no guarantees about accuracy of either log2 or exp2, so we'd be playing a guessing game about how far we can go before the calculation becomes unsafe (in the sense of the `round` operation potentially giving the wrong answer). I think it would be better to stick to integer-only arithmetic. -- ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Mark Dickinson added the comment:
One approach that avoids the use of floating-point arithmetic is to precompute
the odd part of the factorial of n modulo 2**64, for all small n. If we also
precompute the inverses, then three lookups and two 64x64->64 unsigned integer
multiplications gets us the odd part of the combinations modulo 2**64, hence
for small enough n and k gets us the actual odd part of the combinations.
Then a shift by a suitable amount gives comb(n, k).
Here's what that looks like in Python. The "% 2**64" operation obviously
wouldn't be needed in C: we'd just do the computation with uint64_t and rely on
the normal wrapping semantics. We could also precompute the bit_count values if
that's faster.
import math
# Max n to compute comb(n, k) for.
Nmax = 67
# Precomputation
def factorial_odd_part(n):
f = math.factorial(n)
return f // (f & -f)
F = [factorial_odd_part(n) % 2**64 for n in range(Nmax+1)]
Finv = [pow(f, -1, 2**64) for f in F]
PC = [n.bit_count() for n in range(Nmax+1)]
# Fast comb for small values.
def comb_small(n, k):
if not 0 <= k <= n <= Nmax:
raise ValueError("k or n out of range")
return (F[n] * Finv[k] * Finv[n-k] % 2**64) << k.bit_count() +
(n-k).bit_count() - n.bit_count()
# Exhaustive test
for n in range(Nmax+1):
for k in range(0, n+1):
assert comb_small(n, k) == math.comb(n, k)
--
___
Python tracker
<https://bugs.python.org/issue37295>
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46144] math.log() returns improper output
Mark Dickinson added the comment: Yes, confirmed that this is not a bug, but just one of the many consequences of approximating real numbers by floating-point numbers. You may be interested in math.log2 and/or int.bit_length. math.log2(x) *may* give you more accurate results than math.log(x, 2) when x is a power of two, but there are no guarantees - we're at the mercy of the C math library here. -- nosy: +mark.dickinson resolution: -> not a bug ___ Python tracker <https://bugs.python.org/issue46144> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Mark Dickinson added the comment: That computation of the shift can be simplified to require only one popcount operation. With F and Finv as before: def comb_small(n, k): assert 0 <= k <= n <= Nmax return (F[n] * Finv[k] * Finv[n-k] % 2**64) << (k ^ n ^ (n-k)).bit_count() -- ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue23522] Misleading note in Statistics module documentation
Change by Mark Dickinson : -- stage: patch review -> resolved status: open -> closed ___ Python tracker <https://bugs.python.org/issue23522> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Mark Dickinson added the comment: [Tim] > The justification for the shift count isn't self-evident, and > appears to me to be an instance of the generalization of Kummer's > theorem to multinomial coefficients. Not sure there's any generalisation here: I think it *is* just Kummer's theorem. Though I confess I wasn't aware that this was a named theorem - I was working directly from what I now discover is called [Legendre's formula](https://en.wikipedia.org/wiki/Legendre%27s_formula), which I originally learned from "Concrete Mathematics" by Knuth et. al., where they also didn't mention any particular names. It's equation 4.24 in my edition; it may have a different number in the 2nd edition. Kummer's theorem says that the 2-valuation of n-choose-k is the number of carries when k is added to n-k in binary. Notation: write `bit(x, i)` for the bit at position `i` of `x` - i.e., `(x >> i) & 1` In the absence of carries when adding `k` to `n-k`, `bit(n, i) = bit(k, i) ^ bit(n-k, i)`. We have an incoming carry whenever `bit(n, i) != bit(k, i) ^ bit(n-k, i)`; i.e., whenever `bit(n ^ k ^ (n-k), i)` is `1`. So the number of carries is the population count of `n ^ k ^ (n-k)`. > I think it would be clearer at first sight to rely instead on that 2**i/(2**j > * 2**k) = 2**(i-j-k), which is shallow. Sounds fine to me, especially if it makes little performance difference. -- ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue35037] PYLONG_BITS_IN_DIGIT differs between MinGW and MSVC
Mark Dickinson added the comment: > This should probably be a separate issue, Specifically, issue 45569. -- ___ Python tracker <https://bugs.python.org/issue35037> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue20369] concurrent.futures.wait() blocks forever when given duplicate Futures
Change by Mark Dickinson : -- nosy: -mark.dickinson ___ Python tracker <https://bugs.python.org/issue20369> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46055] Speed up binary shifting operators
Change by Mark Dickinson : -- nosy: +mark.dickinson ___ Python tracker <https://bugs.python.org/issue46055> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46055] Speed up binary shifting operators
Change by Mark Dickinson : -- keywords: +patch pull_requests: +28464 stage: -> patch review pull_request: https://github.com/python/cpython/pull/30243 ___ Python tracker <https://bugs.python.org/issue46055> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Mark Dickinson added the comment: Raymond: how do you want to proceed on this? Should I code up my suggestion in a PR, or are you already working on it? -- ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46173] float(x) with large x not raise OverflowError
Mark Dickinson added the comment: Yes, exactly: Python's intentionally following the normal IEEE 754 rules for rounding a value to the binary64 format using the round-ties-to-even rounding rule, as formalised in section 7.4 of IEEE 754-2019 (and quoted by @cykerway). These are the exact same rules that are followed for conversion from str to float (where we return `inf` rather than raise `OverflowError` for large values, but the overflow boundary is the same), or conversion from Fraction to float, or conversion from Decimal to float, etc. > the python float doc might better say "If the *rounded* argument is > outside..." Docs are hard. I think there's a danger that that word "rounded" would cause more confusion than it alleviates - to me, it suggests that there's some kind of rounding going on *before* conversion to float, rather than *as part of* the conversion to float. This isn't a language specification document, so it's not reasonable to give a perfectly accurate description of what happens - the actual meaning would be lost in the mass of details. (In this case, it would also be rather hard to be precise, given that we have to allow for platforms that aren't using IEEE 754.) I'm not seeing an obvious way to improve the docs here. -- ___ Python tracker <https://bugs.python.org/issue46173> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46173] float(x) with large x not raise OverflowError
Mark Dickinson added the comment: If we wanted to make a change, I think the part of the docs that I'd target would be this sentence: > a floating point number with the same value (within Python’s floating point > precision) is returned It's that "same value (within Python's floating point precision)" bit that I'd consider changing. We could consider replacing it with something along the lines that "an integer argument is rounded to the nearest float", possibly with an additional note that under the assumption of IEEE 754 binary64 format, we follow the usual IEEE 754 rules. -- ___ Python tracker <https://bugs.python.org/issue46173> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46173] float(x) with large x not raise OverflowError
Change by Mark Dickinson : -- resolution: -> not a bug ___ Python tracker <https://bugs.python.org/issue46173> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46173] Clarify conditions under which float(x) with large x raises OverflowError
Mark Dickinson added the comment: Changing to a documentation issue. -- assignee: -> docs@python components: +Documentation -Interpreter Core nosy: +docs@python resolution: not a bug -> title: float(x) with large x not raise OverflowError -> Clarify conditions under which float(x) with large x raises OverflowError versions: +Python 3.11 ___ Python tracker <https://bugs.python.org/issue46173> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Change by Mark Dickinson : -- pull_requests: +28490 pull_request: https://github.com/python/cpython/pull/30275 ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46055] Speed up binary shifting operators
Mark Dickinson added the comment: New changeset 360fedc2d2ce6ccb0dab554ef45fe83f7aea1862 by Mark Dickinson in branch 'main': bpo-46055: Streamline inner loop for right shifts (#30243) https://github.com/python/cpython/commit/360fedc2d2ce6ccb0dab554ef45fe83f7aea1862 -- ___ Python tracker <https://bugs.python.org/issue46055> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46055] Speed up binary shifting operators
Mark Dickinson added the comment: New changeset 3581c7abbe15bad6ae08fc38887e5948f8f39e08 by Xinhang Xu in branch 'main': bpo-46055: Speed up binary shifting operators (GH-30044) https://github.com/python/cpython/commit/3581c7abbe15bad6ae08fc38887e5948f8f39e08 -- ___ Python tracker <https://bugs.python.org/issue46055> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46055] Speed up binary shifting operators
Mark Dickinson added the comment: Two separate significant improvements have been pushed: thanks, Xinhang Xu! The original PR also contained a reworking of the general case for right-shifting a negative integer. The current code (in main) for that case does involve some extra allocations, and it ought to be possible to write something that doesn't need to allocate temporary PyLongs. -- ___ Python tracker <https://bugs.python.org/issue46055> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46187] Optionally support rounding for math.isqrt()
Mark Dickinson added the comment: FWIW, when this need has turned up for me (which it has, a couple of times), I've used this: def risqrt(n): return (isqrt(n<<2) + 1) >> 1 But I'll admit that that's a bit non-obvious. -- ___ Python tracker <https://bugs.python.org/issue46187> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46055] Speed up binary shifting operators
Change by Mark Dickinson : -- pull_requests: +28493 pull_request: https://github.com/python/cpython/pull/30277 ___ Python tracker <https://bugs.python.org/issue46055> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Mark Dickinson added the comment: New changeset 02b5417f1107415abaf81acab7522f9aa84269ea by Mark Dickinson in branch 'main': bpo-37295: Speed up math.comb(n, k) for 0 <= k <= n <= 67 (GH-30275) https://github.com/python/cpython/commit/02b5417f1107415abaf81acab7522f9aa84269ea -- ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46203] Add timeout for Windows build steps
New submission from Mark Dickinson : Recently there was an upstream issue with GitHub Actions that caused the Windows build steps in build.yml to hang. No output for the step was displayed in the build logs until the entire job was eventually cancelled, after the default step timeout of 6 hours. I don't know how to fix the "no output" problem, but we can mitigate the 6 hour wait by adding a timeout for the build step. Some external discussion suggested that a conservative timeout of 30 minutes would be appropriate; looking at recent PRs, the build usually completes in around 5 minutes. The (soon-to-be-)attached PR adds that timeout. Here's the log from one of the failed jobs: https://github.com/python/cpython/runs/4641823914?check_suite_focus=true (note that this link will probably eventually become invalid). Here's the relevant GitHub incident: https://www.githubstatus.com/incidents/gh0vvxtlj5v7 -- messages: 409359 nosy: christian.heimes, mark.dickinson, steve.dower priority: normal severity: normal status: open title: Add timeout for Windows build steps versions: Python 3.11 ___ Python tracker <https://bugs.python.org/issue46203> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46203] Add timeout for Windows build steps
Change by Mark Dickinson : -- keywords: +patch pull_requests: +28513 stage: -> patch review pull_request: https://github.com/python/cpython/pull/30301 ___ Python tracker <https://bugs.python.org/issue46203> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Mark Dickinson added the comment: > So which of xor-popcount and add-up-up-trailing-zero-counts is faster may > well depend on platform. I ran some timings for comb(k, 67) on my macOS / Intel MacBook Pro, using timeit to time calls to a function that looked like this: def f(comb): for k in range(68): for _ in range(256): comb(k, 67) comb(k, 67) ... # 64 repetitions of comb(k, 67) in all Based on 200 timings of this script with each of the popcount approach and the uint8_t-table-of-trailing-zero-counts approach (interleaved), the popcount approach won, but just barely, at around 1.3% faster. The result was statistically significant (SciPy gave me a result of Ttest_indResult(statistic=19.929941828072433, pvalue=8.570975609117687e-62)). Interestingly, the default build on macOS/Intel is _not_ using the dedicated POPCNT instruction that arrived with the Nehalem architecture, presumably because it wants to produce builds that will still be useable on pre-Nehalem machines. It uses Clang's __builtin_popcount, but that gets translated to the same SIMD-within-a-register approach that we have already in pycore_bitutils.h. If I recompile with -msse4.2, then the POPCNT instruction *is* used, and I get an even more marginal improvement: a 1.7% speedup over the lookup-table-based version. -- ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46187] Optionally support rounding for math.isqrt()
Mark Dickinson added the comment: > did you invent this? The idea is no more than: "compute an extra bit, then use that extra bit to determine which way to round". More generally, for any real number x, the nearest integer to x (rounding ties towards +infinity) is `⌊(⌊2x⌋ + 1) / 2⌋`. Now put x = √n, then ⌊2x⌋ is ⌊√(4n)⌋, and the rest follows. -- ___ Python tracker <https://bugs.python.org/issue46187> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46187] Optionally support rounding for math.isqrt()
Mark Dickinson added the comment: > I'd be happy to see recipes added to the docs for rounded and ceiling flavors > of isqrt, but am dubious about the value of building them in. I'd similarly prefer to see recipes in the docs. We already have such a recipe for ceil(√n). -- ___ Python tracker <https://bugs.python.org/issue46187> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue45569] Drop support for 15-bit PyLong digits?
Mark Dickinson added the comment: I posted a request for information on usage of 15-bit digits to python-dev: https://mail.python.org/archives/list/python-...@python.org/thread/ZICIMX5VFCX4IOFH5NUPVHCUJCQ4Q7QM/ -- ___ Python tracker <https://bugs.python.org/issue45569> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Mark Dickinson added the comment: > I'm assuming you meant to write comb(67, k) instead Aargh! That is of course what I meant, but not in fact what I timed. :-( I'll redo the timings. Please disregard the previous message. -- ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Mark Dickinson added the comment: Thanks Tim for spotting the stupid mistake. The reworked timings are a bit more ... plausible. tl;dr: On my machine, Raymond's suggestion gives a 2.2% speedup in the case where POPCNT is not available, and a 0.45% slowdown in the case that it _is_ available. Given that, and the fact that a single-instruction population count is not as readily available as I thought it was, I'd be happy to change the implementation to use the trailing zero counts as suggested. I'll attach the scripts I used for timing and analysis. There are two of them: "timecomb.py" produces a single timing. "driver.py" repeatedly switches branches, re-runs make, runs "timecomb.py", then assembles the results. I ran the driver.py script twice: once with a regular `./configure` step, and once with `./configure CFLAGS="-march=haswell"`. Below, "base" refers to the code currently in master; "alt" is the branch with Raymond's suggested change on it. Output from the script for the normal ./configure Mean time for base: 40.130ns Mean for alt: 39.268ns Speedup: 2.19% Ttest_indResult(statistic=7.9929245698581415, pvalue=1.4418376402220854e-14) Output for CFLAGS="-march=haswell": Mean time for base: 39.612ns Mean for alt: 39.791ns Speedup: -0.45% Ttest_indResult(statistic=-6.75385578636895, pvalue=5.119724894191512e-11) -- Added file: https://bugs.python.org/file50530/timecomb.py ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Change by Mark Dickinson : Added file: https://bugs.python.org/file50531/driver.py ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue45569] Drop support for 15-bit PyLong digits?
Change by Mark Dickinson : -- keywords: +patch pull_requests: +28519 stage: -> patch review pull_request: https://github.com/python/cpython/pull/30306 ___ Python tracker <https://bugs.python.org/issue45569> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue45569] Drop support for 15-bit PyLong digits?
Mark Dickinson added the comment: Terry: > create a fake test file test/test_xintperf [...] Sounds reasonable, though I'm not sure I know what exact timings I'd want to try. Maybe some of the stock integer-heavy Python benchmarks (pidigits, etc.). I realised that I have no idea whether any of the buildbots actually use 15-bit digits. I've created PR GH-30306 to find out. -- stage: patch review -> ___ Python tracker <https://bugs.python.org/issue45569> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue45569] Drop support for 15-bit PyLong digits?
Mark Dickinson added the comment: > I've created PR GH-30306 to find out. Results: we have two Gentoo/x86 buildbots, and a 32-bit Windows build in GitHub Actions: those machines use 15-bit digits, as a result of the logic in pyport.h that chooses 15-bit digits if SIZEOF_VOID_P < 8. Everything else seems to be using 30-bit digits. GPS pointed out in the python-dev discussion that the other platform we should be thinking about is 32-bit ARM. -- ___ Python tracker <https://bugs.python.org/issue45569> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Change by Mark Dickinson : -- pull_requests: +28529 pull_request: https://github.com/python/cpython/pull/30313 ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Mark Dickinson added the comment: > I'd be happy to change the implementation to use the trailing zero counts as > suggested. Done in GH-30313 (though this will conflict with Serhiy's PR). -- ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46187] Optionally support rounding for math.isqrt()
Mark Dickinson added the comment: A new function isqrt_rem seems like a reasonably natural addition. (Though I'd call it "isqrtrem", partly by analogy with "divmod", and partly because the math module isn't very good at doing underscores.) -- ___ Python tracker <https://bugs.python.org/issue46187> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46187] Optionally support rounding for math.isqrt()
Mark Dickinson added the comment: > Mark didn't mention his use case for rounded isqrt Mainly for emulation of floating-point sqrt. But the number of times I've needed rounded integer square root is small compared with the number of times I've needed rounded integer division. -- ___ Python tracker <https://bugs.python.org/issue46187> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue37295] Possible optimizations for math.comb()
Mark Dickinson added the comment: New changeset 0b58bac3e7877d722bdbd3c38913dba2cb212f13 by Mark Dickinson in branch 'main': bpo-37295: More direct computation of power-of-two factor in math.comb (GH-30313) https://github.com/python/cpython/commit/0b58bac3e7877d722bdbd3c38913dba2cb212f13 -- ___ Python tracker <https://bugs.python.org/issue37295> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46199] Calculation influenced by print
Mark Dickinson added the comment: When you do: FINUB = np.empty(len(close)) FINLB = np.empty(len(close)) you're creating two *uninitialised* arrays of values. (See the NumPy documentation at https://numpy.org/doc/stable/reference/generated/numpy.empty.html.) When you then do FINUB[i] = UB[i] if UB[i] < FINUB[i-1] \ and close[i-1] > FINUB[i] else FINUB[i-1] on the first iteration of the loop (i = 1), you make use of the (undefined) value in FINUB[0] to compute FINUB[1]. In other words, this is a bug in your code, rather than in Python or NumPy. -- nosy: +mark.dickinson resolution: -> not a bug stage: -> resolved status: open -> closed ___ Python tracker <https://bugs.python.org/issue46199> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46020] Optimize long_pow for the common case
Change by Mark Dickinson : -- nosy: +tim.peters ___ Python tracker <https://bugs.python.org/issue46020> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46258] Minor algorithmic improvements for math.isqrt
New submission from Mark Dickinson : There are a couple of minor algorithmic improvements possible for the math.isqrt fast path (which is used for nonnegative integers smaller than 2**64). On my machine those improvements produce a little over a 10% speedup. The current algorithm for values under 2**64 involves exactly four division instructions, corresponding to four Newton steps. The proposal is to: - 1. Replace the first division with a table lookup. The necessary table is extremely small: 12 entries at one byte per entry. - 2. Arrange for the return type of the _approximate_sqrt helper function to be uint32_t rather than uint64_t. That means that the correction step only involves a 32-bit-by-32-bit multiplication, not a 64-bit-by-64-bit multiplication. The second part is a bit subtle: the input to _approximate_sqrt is a 64-bit integer `n` in the range [2**62, 2**64). Barring any overflow, the output `u` is guaranteed to satisfy `(u-1)**2 < n < (u+1)**2`. That implies that `(u-1)**2 < 2**64`, from which it follows that `u <= 2**32`. So the only possible case where `u` might overflow a `uint32_t` is when `u == 2**32`. But from the earlier inequality, that can only happen if `n > (2**32 - 1)**2`, and in that case the top 31 bits of `n` are completely determined and since the first steps of the algorithm only depend on the topmost bits of `n`, it's easy to follow through the algorithm and see that it's not possible for `u` to be `2**32` in that case. (We always get `u = 128` from the lookup, followed by `u = 255` after the first division, then `u = 65536` after the second.) -- components: Extension Modules messages: 409693 nosy: mark.dickinson priority: normal severity: normal stage: commit review status: open title: Minor algorithmic improvements for math.isqrt type: performance versions: Python 3.11 ___ Python tracker <https://bugs.python.org/issue46258> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46258] Minor algorithmic improvements for math.isqrt
Change by Mark Dickinson : -- keywords: +patch pull_requests: +28612 stage: commit review -> patch review pull_request: https://github.com/python/cpython/pull/30333 ___ Python tracker <https://bugs.python.org/issue46258> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46277] '''...''' error
Mark Dickinson added the comment: https://github.com/ipython/ipython/issues/12843 looks very closely related, and may be the exact same bug. -- nosy: +mark.dickinson ___ Python tracker <https://bugs.python.org/issue46277> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46272] Fix bitwise and logical terminology in python.gram
Mark Dickinson added the comment:
> In the section "Comparison operators", all mentions of "bitwise" should be
> "binary".
Should they? The corresponding line from
https://docs.python.org/3/reference/expressions.html#comparisons is
comparison::= or_expr (comp_operator or_expr)*
which seems to match:
comparison[expr_ty]:
| a=bitwise_or b=compare_op_bitwise_or_pair+ { ... snipped ... }
| bitwise_or
from the "Comparisons operators" section of the grammar. The
next-higher-precedence operation after comparison operators is bitwise or, and
the occurrences of "bitwise_or" look correct to me in this section.
We could retitle "Comparisons operators" to "Comparison operators", though.
> The section "Logical operators" should be retitled "Bitwise operators".
Agreed.
--
nosy: +mark.dickinson
___
Python tracker
<https://bugs.python.org/issue46272>
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46294] Integer overflow & Int values loaded into Bool detected via Libfuzzer & UndefinedBehaviorSanitizer
Mark Dickinson added the comment: @swirsz: Thanks for the report. Most of these look like false positives: we're intentionally making use of C's unsigned arithmetic behaviour. Note that these are technically *not* overflows. As the C standard itself says, in C99 §6.2.5, paragraph 9: > A computation involving unsigned operands can never overflow, > because a result that cannot be represented by the resulting > unsigned integer type is reduced modulo the number that is one > greater than the largest value that can be represented by the > resulting type. .. and we're deliberately depending on exactly that well-defined reduction behaviour. Would you be able to do a first pass over the results and identify those that might be genuine issues, worthy of further investigation? -- nosy: +mark.dickinson ___ Python tracker <https://bugs.python.org/issue46294> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46203] Add timeout for Windows build steps
Change by Mark Dickinson : -- stage: patch review -> resolved status: open -> closed ___ Python tracker <https://bugs.python.org/issue46203> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue45569] Drop support for 15-bit PyLong digits?
Change by Mark Dickinson : -- pull_requests: +28703 stage: -> patch review pull_request: https://github.com/python/cpython/pull/30497 ___ Python tracker <https://bugs.python.org/issue45569> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue45569] Drop support for 15-bit PyLong digits?
Mark Dickinson added the comment: First step in GH-30497, which changes the default to 30-bit digits unconditionally, instead of having the default be platform dependent. -- ___ Python tracker <https://bugs.python.org/issue45569> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46294] Integer overflow & Int values loaded into Bool detected via Libfuzzer & UndefinedBehaviorSanitizer
Mark Dickinson added the comment: Thanks for checking, Steven. Your report also helped me to notice a minor portability bug (at Objects/longobject.c:288, where the wrong type is used in a cast); a fix is in GH-30496. -- ___ Python tracker <https://bugs.python.org/issue46294> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46311] Clean up PyLong_FromLong and PyLong_FromLongLong
New submission from Mark Dickinson : PR GH-27832 inadvertently (I believe) introduced a couple of changes to PyLong_FromLong that didn't make a lot of sense: an (unsigned long) cast was replaced with (twodigits), and a digit count variable (counting number of PyLong digits in a C long) had its type needlessly changed from int to Py_ssize_t. The first change is a potential portability bug, but only on platforms where the width of C's `long` exceeds 64 bits. The (unsigned long) cast is obviously correct, while figuring out whether (twodigits) loses information takes some work. The second change is merely a potential pessimization: there's no need to use what's typically a 64-bit integer to count the number of PyLong digits in a long. While fixing these, I've also reworked the PyLong_FromLong code a bit to move the medium int check earlier, and I've applied analogous changes to PyLong_FromLongLong. -- messages: 410141 nosy: Mark.Shannon, mark.dickinson priority: normal severity: normal status: open title: Clean up PyLong_FromLong and PyLong_FromLongLong versions: Python 3.11 ___ Python tracker <https://bugs.python.org/issue46311> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46311] Clean up PyLong_FromLong and PyLong_FromLongLong
Change by Mark Dickinson : -- keywords: +patch pull_requests: +28705 stage: -> patch review pull_request: https://github.com/python/cpython/pull/30496 ___ Python tracker <https://bugs.python.org/issue46311> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46272] Fix bitwise and logical terminology in python.gram
Change by Mark Dickinson : -- keywords: +patch pull_requests: +28706 stage: -> patch review pull_request: https://github.com/python/cpython/pull/30499 ___ Python tracker <https://bugs.python.org/issue46272> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46272] Fix bitwise and logical terminology in python.gram
Mark Dickinson added the comment: > So, the meaning of these names like this is, "lt followed by an optional > bitwise_or expression"? That's certainly how I was reading it. -- ___ Python tracker <https://bugs.python.org/issue46272> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue45569] Drop support for 15-bit PyLong digits?
Mark Dickinson added the comment: Adding Stefan Behnel to the nosy, since Cython is one of the few projects that might be directly affected by this change. Stefan: can you see any potential problems with changing the default to 30 here? -- nosy: +scoder ___ Python tracker <https://bugs.python.org/issue45569> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46361] Small ints aren't always cached properly
Mark Dickinson added the comment: I don't *think* we currently rely on small integers being cached anywhere in the implementation (and neither do we guarantee anywhere in the docs that small integers will be cached), so as far as I can tell these omissions shouldn't lead to user-visible bugs. I agree that these cases should be fixed, though. -- nosy: +mark.dickinson ___ Python tracker <https://bugs.python.org/issue46361> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46361] Small ints aren't always cached properly
Mark Dickinson added the comment:
Hmm. This sort of thing is a little dodgy, though (despite the comment that
it's "okay"):
https://github.com/python/cpython/blob/1de60155d5d01be2924e72fb68dd13d4fd00acd7/Modules/mathmodule.c#L939
PyObject *zero = _PyLong_GetZero(); // borrowed ref
for (i = 1; i < nargs; i++) {
/* --- 8< --- snipped code */
if (res == zero) {
/* Fast path: just check arguments.
It is okay to use identity comparison here. */
Py_DECREF(x);
continue;
}
/* --- 8< --- snipped code*/
}
--
___
Python tracker
<https://bugs.python.org/issue46361>
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46361] Small ints aren't always cached properly
Mark Dickinson added the comment:
And there are some similar things going on in rangeobject.c.
https://github.com/python/cpython/blob/1de60155d5d01be2924e72fb68dd13d4fd00acd7/Objects/rangeobject.c#L598
if (r->step == _PyLong_GetOne()) {
return idx;
}
Again, technically "okay", since it's only a fast path and the slow path that
follows will still do the right thing with a 1 that's not "the" 1, but it feels
fragile.
--
___
Python tracker
<https://bugs.python.org/issue46361>
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue45569] Drop support for 15-bit PyLong digits?
Mark Dickinson added the comment: Thanks, Stefan. I think I'm going to go ahead with the first step of making 30-bit digits the default, then, but leaving the 15-bit digit option present. > That said, if we decide to keep 15-bit digits in the end, I wonder if > "SIZEOF_VOID_P" is the right decision point. It seems more of a "has > reasonably fast 64-bit multiply or not" kind of decision Agreed. And most platforms we care about _do_ seem to have such an instruction, so "30-bit digits unless the builder explicitly indicates otherwise - e.g., via configure options or pyconfig.h edits" seems reasonable. My other worry is division. It's less important than multiplication in the sense that I'd expect division operations to be rarer than multiplications in typical code, but the potential impact for code that _does_ make heavy use of division is greater. With 30-bit digits, all the longobject.c source actually *needs* is a 64-bit-by-32-bit unsigned division for cases where the result is guaranteed to fit in a uint32_t. If we're on x86, there's an instruction for that (DIVL), so you'd think that we'd be fine. But without using inline assembly, it seems impossible to persuade current versions of either of GCC or Clang[*] to generate that DIVL instruction - instead, they both want to do a 64-bit-by-64-bit division, and on x86 that involves making a call to a dedicated __udivti3 intrinsic, which is potentially multiple times slower than a simple DIVL. The division problem affects x64 as well: GCC and Clang currently generate a DIVQ instruction when all we need is a DIVL. > If we find a platform that would be fine with 30-bits but lacks a fast 64-bit > multiply, then we could still try to add a platform specific value size check > for smaller numbers. Since those are common case, branch prediction might > help us more often than not. Yes, I think that could work, both for multiplication and division. [*] Visual Studio 2019 _does_ apparently provide a _udiv64 intrinsic, which we should possibly be attempting to use: https://docs.microsoft.com/en-us/cpp/intrinsics/udiv64?view=msvc-170 -- ___ Python tracker <https://bugs.python.org/issue45569> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue45569] Drop support for 15-bit PyLong digits?
Mark Dickinson added the comment: New changeset 025cbe7a9b5d3058ce2eb8015d3650e396004545 by Mark Dickinson in branch 'main': bpo-45569: Change PYLONG_BITS_IN_DIGIT default to 30 (GH-30497) https://github.com/python/cpython/commit/025cbe7a9b5d3058ce2eb8015d3650e396004545 -- ___ Python tracker <https://bugs.python.org/issue45569> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46258] Minor algorithmic improvements for math.isqrt
Mark Dickinson added the comment: New changeset d02c5e9b55a8651b7d396ac3f2bdedf1fc1780b5 by Mark Dickinson in branch 'main': bpo-46258: Streamline isqrt fast path (#30333) https://github.com/python/cpython/commit/d02c5e9b55a8651b7d396ac3f2bdedf1fc1780b5 -- ___ Python tracker <https://bugs.python.org/issue46258> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46258] Minor algorithmic improvements for math.isqrt
Change by Mark Dickinson : -- stage: patch review -> resolved status: open -> closed ___ Python tracker <https://bugs.python.org/issue46258> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46393] Generate frozenset constants when explicitly appropriate
Mark Dickinson added the comment:
[Terry]
> To avoid the intermediate set, [...]
It's not quite as bad as that: there _is_ no intermediate set (or if you
prefer, the intermediate set is the same object as the final set), since the
frozenset call returns its argument unchanged if it's already of exact type
frozenset:
>>> x = frozenset({1, 2, 3})
>>> y = frozenset(x)
>>> y is x
True
Relevant source:
https://github.com/python/cpython/blob/09087b8519316608b85131ee7455b664c00c38d2/Objects/setobject.c#L999-L1003
--
nosy: +mark.dickinson
___
Python tracker
<https://bugs.python.org/issue46393>
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46393] Generate frozenset constants when explicitly appropriate
Mark Dickinson added the comment: > That's not always the case though. Sorry, yes - I see. We're not creating a frozenset from a frozenset - we're creating a frozenset from a regular set from a frozenset. :-( Sorry for the noise. -- ___ Python tracker <https://bugs.python.org/issue46393> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46372] int/float specializations should mutate the LHS in-place when possible
Change by Mark Dickinson : -- nosy: +mark.dickinson ___ Python tracker <https://bugs.python.org/issue46372> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46361] Small ints aren't always cached properly
Mark Dickinson added the comment: New changeset 5cd9a162cd02a3d0f1b0a182d80feeb17439e84f by Brandt Bucher in branch 'main': bpo-46361: Fix "small" `int` caching (GH-30583) https://github.com/python/cpython/commit/5cd9a162cd02a3d0f1b0a182d80feeb17439e84f -- ___ Python tracker <https://bugs.python.org/issue46361> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46361] Small ints aren't always cached properly
Change by Mark Dickinson : -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker <https://bugs.python.org/issue46361> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46393] Generate frozenset constants when explicitly appropriate
Change by Mark Dickinson : -- nosy: -mark.dickinson ___ Python tracker <https://bugs.python.org/issue46393> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46423] CLI: Addition assignment for tuples
Mark Dickinson added the comment: Thanks for the report. This is a long-standing and known behaviour. It's been discussed a good few times before, and (quite apart from potential problems with backwards compatibility) no-one has yet come up with convincing alternative behaviours. See https://docs.python.org/3/faq/programming.html#why-does-a-tuple-i-item-raise-an-exception-when-the-addition-works Marking as a duplicate of https://bugs.python.org/issue40911 -- nosy: +mark.dickinson resolution: -> duplicate stage: -> resolved status: open -> closed superseder: -> Unexpected behaviour for += assignment to list inside tuple ___ Python tracker <https://bugs.python.org/issue46423> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46444] Wrong value of pi for larger values using math.cos() function
Mark Dickinson added the comment: Hi Darshan. This isn't a bug in Python. You're running into the limitations of floating-point arithmetic. There's a lot of good material on those limitations available on the web, starting with Python's own tutorial: https://docs.python.org/3/tutorial/floatingpoint.html If you want to understand what's going on in this particular case, take a closer look at the values of 90 - 180/k when k=2**62 and k=2**63, say. Are they the same? Should they be? Why / why not? -- nosy: +mark.dickinson resolution: -> not a bug status: open -> closed ___ Python tracker <https://bugs.python.org/issue46444> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue45995] string formatting: normalize negative zero
Mark Dickinson added the comment: [John] > Mark, would you give it a review this month? Apologies; my holiday-break free time was nobbled from unexpected quarters. I can't promise to find time this month, but I can promise to try. I did at least skim through the PR, and while there are still likely some iterations needed I'm satisfied that this is technically feasible. But I'm afraid that's the easy part. If this is to go in, the other problem we still have to solve is achieving some consensus among the core developers that this is worth doing. Right now, judging by comments on this issue, I think I'm the only core dev who thinks this is a good idea; others are lukewarm at best, and I'm not willing to unilaterally approve and merge these changes without something closer to a consensus. There are a couple of ways forward here: - Post the proposal on python-ideas to get wider visibility and feedback. If everyone agrees this is a great idea (from experience, this seems an unlikely outcome), then we can go ahead and merge. Otherwise we'd likely need a PEP to move forward. - Bypass the python-ideas step, write the PEP, discuss in the appropriate forums, and then submit to the SC for approval / rejection. - Convince Eric Smith. :-) With apologies to Eric for singling him out: Eric could reasonably be described as the steward/maintainer of the formatting machinery, so if he's persuaded, that's good enough for me. The fact that you've already created a working implementation so that people can experiment is a bonus when it comes to trying to sell this to others. I don't have the bandwidth to write a PEP, but I would be happy to act as PEP sponsor. -- ___ Python tracker <https://bugs.python.org/issue45995> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue29882] Add an efficient popcount method for integers
Change by Mark Dickinson : -- pull_requests: +28979 pull_request: https://github.com/python/cpython/pull/30794 ___ Python tracker <https://bugs.python.org/issue29882> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue29882] Add an efficient popcount method for integers
Mark Dickinson added the comment: New changeset 83a0ef2162aa379071e243f1b696aa6814edcd2a by Mark Dickinson in branch 'main': bpo-29882: Fix portability bug introduced in GH-30774 (#30794) https://github.com/python/cpython/commit/83a0ef2162aa379071e243f1b696aa6814edcd2a -- ___ Python tracker <https://bugs.python.org/issue29882> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46406] optimize int division
Mark Dickinson added the comment: New changeset c7f20f1cc8c20654e5d539552604362feb9b0512 by Gregory P. Smith in branch 'main': bpo-46406: Faster single digit int division. (#30626) https://github.com/python/cpython/commit/c7f20f1cc8c20654e5d539552604362feb9b0512 -- ___ Python tracker <https://bugs.python.org/issue46406> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46406] optimize int division
Change by Mark Dickinson : -- stage: patch review -> resolved status: open -> closed ___ Python tracker <https://bugs.python.org/issue46406> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.
Change by Mark Dickinson : -- nosy: +tim.peters ___ Python tracker <https://bugs.python.org/issue46488> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue44734] turtle: tests for Vec2D.__abs__ are too strict
Mark Dickinson added the comment: Low priority, but it may also be worth updating the implementation of `Vec2D.__abs__`. It currently looks like this: def __abs__(self): return (self[0]**2 + self[1]**2)**0.5 But would be more robust if it used hypot: def __abs__(self): return math.hypot(self[0], self[1]) -- ___ Python tracker <https://bugs.python.org/issue44734> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue44734] turtle: tests for Vec2D.__abs__ are too strict
Mark Dickinson added the comment: Apologies; looks like I'm out of date on this. It's already using hypot, which makes it more than a little worrying that it doesn't get the right answer for `Vec2D(6, 8)`. -- ___ Python tracker <https://bugs.python.org/issue44734> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue44734] turtle: tests for Vec2D.__abs__ are too strict
Mark Dickinson added the comment: Sorry again, all; I failed to read everything that was going on here. The test *wasn't* failing with the hypot-based version of Vec2D.__abs__ that's in the main branch; only with the "**0.5"-based version that was still in the older branches. Please ignore this and the previous two messages ... -- ___ Python tracker <https://bugs.python.org/issue44734> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46640] Python can now use the C99 NAN constant
Mark Dickinson added the comment: The big blocker here is that a platform that fully supports C99 might not define the "NAN" macro. I don't think we can require that NAN be defined in order for Python to build (which is what the PR currently does, if I'm understanding it correctly). Python deliberately doesn't assume IEEE 754 floating-point. By requiring that the C "NAN" macro is present to be able to build Python, we'd be effectively requiring IEEE 754 by stealth. (No other common floating-point format has NaNs.) I'd be fully on board with a decision to require IEEE 754 floating-point for Python in future, but that decision would at least need a python-dev discussion - we shouldn't sneak it in by the back door. -- nosy: +rhettinger, tim.peters ___ Python tracker <https://bugs.python.org/issue46640> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46639] Ceil division with math.ceildiv
Mark Dickinson added the comment: I'm not convinced that this deserves to be a math module function. I agree that `-(-x // y)`, while simple to write, isn't necessarily obvious. But it does have some advantages, like not needing an import, and being naturally duck-typed, so that it automatically does the right thing for floats, or `fractions.Fraction` objects, or `numpy.int64` objects, or SymPy integers. (Not for `Decimal` instances, but that's another story.) Unless we were to add a whole __ceildiv__ mechanism, a math module implementation would necessarily be limited to integers. (Or perhaps integers and floats.) There's also the "thin end of the wedge" argument: if ceildiv, why not also ceilrem, ceildivrem, rounddiv, roundmod, etc. The main issue with the `-(-x // y)` spelling seems to be discoverability: if everyone knew that this was the right way to spell ceiling division, then there wouldn't be a problem. And I'm not convinced that a math.ceildiv function would necessarily solve the discoverability problem, either. So maybe the solution is to advertise the `-(-x // y)` pattern better in documentation, for example at the point where floor division is introduced in the library reference? -- ___ Python tracker <https://bugs.python.org/issue46639> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46640] Python can now use the C99 NAN constant
Mark Dickinson added the comment: > If a platform doesn't implement NaN, it should define the Py_NO_NAN macro Ah. In that case your PR description (and the PR news entry) is misleading: > Building Python now requires a C99 header file providing the > NAN constant. Please could you update them? -- ___ Python tracker <https://bugs.python.org/issue46640> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46639] Ceil division with math.ceildiv
Mark Dickinson added the comment: [Tim] > Because it's a bit obscure, and in real life y is always known to be > positive, so the nearly obvious (x + y - 1) // y works fine. Whereas I find (x + y - 1) // y less obvious at first sight than -(-x // y). :-) I don't care about negative y - that's not my reason for preferring -(-x // y). The preference comes from the fact that -(-x // y) still does the right thing for non-integral cases. [Vladimir] > Say we're making a controller for a game engine GUI and need to figure out how to paint sprites. [...] For this example, I'd probably just use `ceil(x / y)`. For "real world" things with x and y representing counts of something tangible (pixels, work items, row or column count of a matrix, lines of text, bytes of memory used, ...), you have to go quite a long way before `ceil(x / y)` gives you the wrong answer due to floating-point errors. E.g. if you know the quotient is no larger than 10**6, you're safe for all y <= 10**10. (Or vice versa: if you know the quotient is at most 10**10, then you're safe for y <= 10**6.) > not __ceildiv__ [...] It would be a little odd (but only a little) to have __floor__, __ceil__, and __floordiv__ overloads, but not __ceildiv__. It probably wouldn't be long before someone requested it. I'll quieten down now and wait to see what other people think. -- ___ Python tracker <https://bugs.python.org/issue46639> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46656] Compile fails if Py_NO_NAN is defined
New submission from Mark Dickinson : The macro Py_NAN may or may not be defined: in particular, a platform that doesn't have NaNs is supposed to be able to define Py_NO_NAN in pyport.h to indicate that. But not all of our uses of `Py_NAN` are guarded by suitable #ifdef conditionals. As a result, compilation fails if Py_NAN is not defined. -- messages: 412620 nosy: mark.dickinson priority: normal severity: normal status: open title: Compile fails if Py_NO_NAN is defined type: behavior versions: Python 3.10, Python 3.11, Python 3.9 ___ Python tracker <https://bugs.python.org/issue46656> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46656] Compile fails if Py_NO_NAN is defined
Mark Dickinson added the comment: Here's the first point of failure on my machine. Fixing this shows up more failures. gcc -c -Wsign-compare -Wunreachable-code -DNDEBUG -g -fwrapv -O3 -Wall -std=c99 -Wextra -Wno-unused-parameter -Wno-missing-field-initializers -Wstrict-prototypes -Werror=implicit-function-declaration -fvisibility=hidden -I./Include/internal -I. -I./Include-DPy_BUILD_CORE -o Objects/complexobject.o Objects/complexobject.c Objects/complexobject.c:120:27: error: use of undeclared identifier 'Py_NAN' r.real = r.imag = Py_NAN; ^ Objects/complexobject.c:206:16: error: use of undeclared identifier 'Py_NAN' return Py_NAN; ^ 2 errors generated. make: *** [Objects/complexobject.o] Error 1 -- ___ Python tracker <https://bugs.python.org/issue46656> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46187] Optionally support rounding for math.isqrt()
Mark Dickinson added the comment:
Thanks, Tim; very interesting. I hadn't seen this factoring algorithm before.
> That wants the _ceiling_ of the square root.
Looks like what it actually wants is the ceiling analog of isqrtrem: that is,
it needs both the ceiling of the square root *and* the difference between the
square of that ceiling and the original number.
The description of the algorithm in section 2 is a bit odd: they define m :=
s*s % n, using an expensive modulo operation, when all they need is a
subtraction: m := s*s - n*i. This is noted in section 3 ("to reduce modulo Mn
at step 3, one may simply subtract Mni from s2"), but they fail to note that
the two things aren't equivalent for large enough i, possibly because that
large an i won't be used in practice. And in the case that the two quantities
differ, it's the subtraction that's needed to make the algorithm work, not the
mod result.
Here's a Python version of Hart's algorithm:
from itertools import count
from math import gcd, isqrt
def isqrtrem(n):
""" For n >= 0, return s, r satisfying s*s + r == n, 0 <= r <= 2*s. """
s = isqrt(n)
return s, n - s*s
def csqrtrem(n):
""" For n > 0, return s, r satisfying n + s*s == r, 0 <= r <= 2*(s-1). """
s = 1 + isqrt(n-1)
return s, s*s - n
def factor(n):
""" Attempt to use Hart's algorithm to find a factor of n. """
for i in count(start=1):
s, m = csqrtrem(n*i)
t, r = isqrtrem(m)
if not r:
return gcd(n, s-t)
--
___
Python tracker
<https://bugs.python.org/issue46187>
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46187] Optionally support rounding for math.isqrt()
Mark Dickinson added the comment: Ah, https://math.mit.edu/research/highschool/primes/materials/2019/Gopalakrishna.pdf is interesting - they conjecture a bound on the number of iterations required, and note that under that conjecture the mod can be replaced by a subtraction. -- ___ Python tracker <https://bugs.python.org/issue46187> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46656] Compile fails if Py_NO_NAN is defined
Mark Dickinson added the comment: Okay, the comments I made on #46640 still apply (even though they didn't properly apply on that issue). I think this needs a python-dev discussion before it can be moved forward - requiring the existence of NaNs is very close to requiring IEEE 754 floating-point, and that's something we've been historically reluctant to do. -- ___ Python tracker <https://bugs.python.org/issue46656> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46656] Compile fails if Py_NO_NAN is defined
Mark Dickinson added the comment: > Is the macro PY_NO_SHORT_FLOAT_REPR also related to platforms which don't > support IEEE 754? Yes, though it's a bit more than that: we also need the platform either not to have issues with double rounding for normal numbers, or we need to be able to control the x87 rounding mode in the case that double rounding might be an issue. See the explanations in the source. https://github.com/python/cpython/blob/025cbe7a9b5d3058ce2eb8015d3650e396004545/Include/pyport.h#L345-L355 > In 2022, which platforms don't support IEEE 754? None that CPython might plausibly run on that I'm aware of. -- ___ Python tracker <https://bugs.python.org/issue46656> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46656] Compile fails if Py_NO_NAN is defined
Mark Dickinson added the comment: > See the explanations in the source. Hmm. Those explanations made more sense before PR GH-28882. :-( -- ___ Python tracker <https://bugs.python.org/issue46656> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46663] test_math test_cmath test_complex fails on Fedora Rawhide buildbots
Mark Dickinson added the comment: @vstinner What was the change that caused the buildbots to start failing? Did the GCC version get updated on those machines between the last runs and this one, or was the change due to recent PRs in Python? -- nosy: +mark.dickinson ___ Python tracker <https://bugs.python.org/issue46663> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46639] Ceil division with math.ceildiv
Mark Dickinson added the comment: > Couldn't math.ceildiv(x, y) be implemented as -(-x//y) in a type-agnostic > fashion? Ah, good point. Yes, that could work. We'd have to decide what to do about Decimal if we took this approach, since the -(-x//y) trick doesn't work there. (Document the issue? Try to make things work for Decimal?) -- ___ Python tracker <https://bugs.python.org/issue46639> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46694] isdigit/isnumeric vs int()
Mark Dickinson added the comment: This is by design: int looks for characters with the Unicode Decimal (De) numeric type, corresponding to str.isdecimal(), rather than for the Digit (Di) or Numeric (Nu) numeric types. >>> "²".isdecimal() False -- nosy: +mark.dickinson ___ Python tracker <https://bugs.python.org/issue46694> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue46694] isdigit/isnumeric vs int()
Change by Mark Dickinson : -- resolution: -> not a bug stage: -> resolved status: open -> closed ___ Python tracker <https://bugs.python.org/issue46694> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
