Tim Peters added the comment:
Just curious about why the focus on the newer exp2 and log2? Logs are logs, and
the "natural" `exp()` and `log()` should work just as well. On Windows, exp2()
is particularly poor for now (I've seen dozens of cases of errors over 2 ulp,
with ex
Tim Peters added the comment:
Clever, Mark! Very nice.
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. I think it would be clearer at first sight to rely instead
Tim Peters added the comment:
I see no use of 128-bit ints in the CPython core. Advice: forget it.
int64_t and uint64_t are required by C99, and are used many places in the core.
Advice: use freely.
Note that if tables of "odd part mod 2**64" and "number of trailing zeroe
Tim Peters added the comment:
No problem, Mark! I just prefer the shallowest approaches that are "good
enough". If it's materially faster to use xors and a popcount instead, fine by
me, just provided a comment points to a clue about why that works.
BTW, the later xor version
Tim Peters added the comment:
Please don't use "long long". It usually introduces platform dependence where
none is intended, or helpful. PEP 7 requires that the compiler in use supply
the fixed-width integer types defined by C99's stdint.h[1]. These are:
int8_t
int
Tim Peters added the comment:
If people are keen to speed comb() for larger arguments, the approach in
Stefan's "comb_with_primes.py" is very much worth looking at. I've played with
that idea before, and it runs circles around any other approach I've seen.
The only
Tim Peters added the comment:
[Mark]
> def risqrt(n):
>return (isqrt(n<<2) + 1) >> 1
Sweet! New one on me - did you invent this? It's slick :-)
I'd be happy to see recipes added to the docs for rounded and ceiling flavors
of isqrt, but am dubious about the va
Tim Peters added the comment:
Raymond, using the count of trailing zeroes instead is exactly what I suggested
before, here:
https://bugs.python.org/issue37295#msg409000
So Mark & I already batted that around. For whatever reasons he had, though, he
stuck with the xor-popcount appr
Tim Peters added the comment:
A timing confounder: I see that CPython's _Py_popcount32() only tries to use
the relevant blazing fast hardware instruction if defined(__clang__) ||
defined(__GNUC__). On Windows, it's a long-winded bit-fiddling dance.
So which of xor-popcount and
Tim Peters added the comment:
>> can we use the decimal module's names for the supported
>> rounding modes?
> I'm not sure those make sense because we never get to
> exactly half. There is only floor, ceil, and round,
> not half_up, half_even, etc.
Tim Peters added the comment:
FYI, I had a simpler derivation in mind. Say
sqrt(n) = r + f
where r = isqrt(n) and 0 <= f < 1. Then
sqrt(4n) = 2 * sqrt(n) = 2*(r + f) = 2r + 2f, with 0 <= 2f < 2.
If f < 0.5, 2f < 1, so isqrt(4n) = 2r, and we shouldn't round r up eith
Tim Peters added the comment:
All cool. Since I doubt these new rounding modes will get much use anyway, it's
not worth arguing about. If I were to do this for myself, the rounding argument
would be one of the three values {-1, 0, +1}, which are already more than good
enough as mnem
Tim Peters added the comment:
About:
TableSize = 101
limits = bytearray(TableSize)
for n in range(0, TableSize):
for k in range(0, n+1):
if comb(n, k) != comb_small(n, k):
(and regardless of whether the last line is replaced with the later correction):
Did
Tim Peters added the comment:
{Serhiy]
> It can benefit larger arguments if move the code in
> perm_comb_small().
Seems pretty clear that the newer code really belongs there instead.
> And perhaps loops in perm_comb_small() could be optimized
> by using precalculated val
Tim Peters added the comment:
A practical caution about this in comb_with_side_limits.py:
Pmax = 25 # 25 41
Fmax = Pmax
It's true then that 25! == F[25] << S[25], but that's so in Python. The result
has 84 bits, so 64-bit C arithmetic isn&#
Tim Peters added the comment:
[Tim]
> That's [Mark's code] cheaper than almost every case handled by
> perm_comb_small()'s current ... "iscomb" loop.
Although I should clarify they're aimed at different things, and don't overlap
all that much. Mark&#
Tim Peters added the comment:
[Mark]
> 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)
Tim Peters added the comment:
> Aargh! That is of course what I meant, but not in fact
> what I timed. :-(
!!! Even more baffling then. Seems like the code posted got out of
math_comb_impl() early here:
if (overflow || ki > ni) {
result = PyLong_F
Tim Peters added the comment:
[Mark]
> The idea is no more than: "compute an extra bit, then use
> that extra bit to determine which way to round".
Thanks! Despite that this is what the derivation I sketched boiled down to, I
was still missing how general the underlying pr
Tim Peters added the comment:
Pretend this were the itertools module and you were responding to someone
suggesting a new optional argument to one of its functions. You have tons of
experience rejecting those, and much the same arguments apply, from "not every
one-line function needs
Tim Peters added the comment:
I'm not rejecting anything. Mark wrote the function, and I'll defer to him.
Yes, you added `initial` to `accumulate()`, and I spent hours in all explaining
to you why it was an utterly natural addition, conspicuous by absence,
including writing up se
Tim Peters added the comment:
Suppose we added isqrt_rem(n), returning the integer pair (i, rem) such that
n == i**2 + rem
0 <= rem <= 2*i
Then:
- Want the floor of sqrt(n)? i.
- The ceiling? i + (rem != 0).
- Rounded? i + (rem > i).
- Is n a perfect square? not rem.
That&
Tim Peters added the comment:
The name "isqrtrem" works fine for me too, and, indeed, is even more
reminiscent of mpz's workalike function.
> the number of times I've needed rounded integer square root
> is small compared with the number of times I've ne
New submission from Tim Peters :
As discussed on python-dev, it would be nice to break long_pow()'s reliance on
that the number of bits in a CPython long "digit" is a multiple of 5.
Moving to the sliding-window algorithm would do that (it has to be able to
cross digit boundar
Change by Tim Peters :
--
keywords: +patch
pull_requests: +28535
stage: needs patch -> patch review
pull_request: https://github.com/python/cpython/pull/30319
___
Python tracker
<https://bugs.python.org/issu
Tim Peters added the comment:
Nope, boosting the window size to 6 doesn't appear to really help at all, at
least not on my box. Regardless of the window size, we have to do a bigint
square for every bit position in the exponent. I don't know of any way to speed
that (short o
Tim Peters added the comment:
Since cutting the window size by 1 cut the size of the dynamic precomputed
table in half, the overhead of the sliding window method was correspondingly
reduced. It can pay off at exponents of half the bit length now, so that
threshold was also changed
Tim Peters added the comment:
New changeset 863729e9c6f599286f98ec37c8716e982c4ca9dd by Tim Peters in branch
'main':
bpo-46218: Change long_pow() to sliding window algorithm (GH-30319)
https://github.com/python/cpython/commit/863729e9c6f599286f98ec37c8716e
Change by Tim Peters :
--
resolution: -> fixed
stage: patch review -> resolved
status: open -> closed
___
Python tracker
<https://bugs.python.or
New submission from Tim Peters :
longobject.c's x_mul()'s special code for squaring gets kind of sloppy at the
end of a digit pass, doing a useless add of 0 and an "extra" test for carry.
Easily cleaned up.
I think the underlying cause is that the HAC algorithm descriptio
Change by Tim Peters :
--
keywords: +patch
pull_requests: +28557
stage: needs patch -> patch review
pull_request: https://github.com/python/cpython/pull/30345
___
Python tracker
<https://bugs.python.org/issu
Tim Peters added the comment:
I was suprised that
https://bugs.python.org/issue44376
managed to get i**2 to within a factor of 2 of i*i's speed. The overheads of
running long_pow() at all are high! Don't overlook that initialization of stack
variables at the start, like
Py
Tim Peters added the comment:
I've made several good-faith efforts to find any hint of demand for rounded
isqrt on the web; I've found no direct support for it in other
languages/environments(*); and the one use case you presented isn't compelling.
Building static tables to
Tim Peters added the comment:
New changeset 3aa5242b54b0627293d95cfb4a26b2f917f667be by Tim Peters in branch
'main':
bpo-46233: Minor speedup for bigint squaring (GH-30345)
https://github.com/python/cpython/commit/3aa5242b54b0627293d95cfb4a26b2
Change by Tim Peters :
--
resolution: -> fixed
stage: patch review -> resolved
status: open -> closed
___
Python tracker
<https://bugs.python.or
Tim Peters added the comment:
> Is
>
> i, rem = isqrt_rem(n)
> i + (rem != 0)
>
> better than
>
> (isqrt(n<<2) + 1) >> 1
>
> or
>
> n and isqrt(n-1) + 1
>
> ?
Define "better"? The first way is by far the most obvious of
Tim Peters added the comment:
New changeset ad1d5908ada171eff768291371a80022bfad4f04 by Dennis Sweeney in
branch 'main':
bpo-46235: Do all ref-counting at once during list/tuple multiplication
(GH-30346)
https://github.com/python/cpython/commit/ad1d5908ada171eff768291371a800
Change by Tim Peters :
--
assignee: -> Dennis Sweeney
resolution: -> fixed
stage: patch review -> resolved
status: open -> closed
___
Python tracker
<https://bugs.python
Change by Tim Peters :
--
keywords: +patch
pull_requests: +28756
stage: -> patch review
pull_request: https://github.com/python/cpython/pull/30555
___
Python tracker
<https://bugs.python.org/issu
Tim Peters added the comment:
GH_30555 helps a bit by leaving the giant-exponent table of small odd powers as
uninitialized stack trash unless it's actually used.
--
___
Python tracker
<https://bugs.python.org/is
Tim Peters added the comment:
Just noting that comb_pole.py requires a development version of Python to run
(under all released versions, a byteorder argument is required for int.{to,
from}_byte() calls).
--
___
Python tracker
<ht
Tim Peters added the comment:
A feature of the current code is that, while the recursion tree can be very
wide, it's not tall, with max depth proportional to the log of k. But it's
proportional to k in the proposal (the C(n-j, k-j) term's second argument goes
down by
Tim Peters added the comment:
I was thinking about
comb(100, 50)
The simple "* --n / ++k" loop does 499,999 each of multiplication and division,
and in all instances the second operand is a single Python digit. Cheap as can
be.
In contrast, despite that it short-ci
Tim Peters added the comment:
Another trick, building on the last one: computing factorial(k) isn't cheap, in
time or space, and neither is dividing by it. But we know it will entirely
cancel out. Indeed, for each outer loop iteration, prod(p) is divisible by the
current k. But, unli
Tim Peters added the comment:
For the purpose of topological sorting, yes, it's by far most natural to give,
for each node, the collection of that node's predecessors. And that's the way
topsort applications typically collect their data to begin with, like, "here,
for ea
Tim Peters added the comment:
I'm going to leave this to Pablo - adding the `graph` argument was his idea ;-)
It would, I think, have been better if this argument had been named, say,
"preds" instead of "graph".
The docs, to my eyes, are entirely clear about that `g
Tim Peters added the comment:
I think you should give up on this. But suit yourself ;-)
Exactly the same information is conveyed whether representing a graph by
successor or predecessor dicts. Some operations are more convenient in one
representation than the other, but each is easily
Tim Peters added the comment:
>> the meanings of "predecessor" and "successor" are
>> universally agreed upon
> I disagree.
I can post literally hundreds of citations that all agree: in u -> v, u is a
direct predecessor of v, and v is a dir
Tim Peters added the comment:
Now you may be getting somewhere ;-) Complaining about the docs wasn't getting
traction because they're using standard terminology with the standard meanings,
and tell the plain truth about what the class requires and delivers.
You wish it required
Tim Peters added the comment:
Perhaps you've overlooking something so obvious to the module authors that I
haven't thought to mention it?
The purpose here is to compute a linear order. Now not even you ;-) can pretend
to be confused about what "predecessor" and "su
Tim Peters added the comment:
> I know that there are many different ways to represent
> a graph, but your graph format *is just plain wrong.*
Yet when I offered to support an option to support the graph format you insist
is uniquely "right", you poo-poo'ed the idea.
Tim Peters added the comment:
Ya, I don't expect anyone will check in a change without doing comparative
timings in C first. Not worried about that.
I'd be happy to declare victory and move on at this point ;-) But that's me.
Near the start of this, I noted that we just won
Tim Peters added the comment:
I'm not inclined to change anything here. It's a trivial point, and by
"primitive" I had in mind a dedicated hardware instruction, blazing fast. Yes,
I was aware of long-winded ways of doing it for specific fixed integer widths.
But that
Tim Peters added the comment:
OK, here's the last version I had. Preconditions are that d > 0, n > 0, and n %
d == 0.
This version tries to use the narrowest possible integers on each step. The
lowermost `good_bits` of dinv at the start of the loop are correct already.
Taking
Tim Peters added the comment:
For any fixed width integer type, the worst case of the dead simple loop (all
bits are zero) is a fixed upper bound. So you don't mean "constant bounded"
either. You mean something more like "clever C code that usually runs faster
than the
New submission from Tim Peters :
x_divrem1() was recently (bpo-46406) changed to generate faster code for
division, essentially nudging optimizing compilers into recognizing that modern
processors compute the quotient and remainder with a single machine instruction.
The same can be done for
Change by Tim Peters :
--
versions: +Python 3.11
___
Python tracker
<https://bugs.python.org/issue46504>
___
___
Python-bugs-list mailing list
Unsubscribe:
Change by Tim Peters :
--
pull_requests: +29038
pull_request: https://github.com/python/cpython/pull/30856
___
Python tracker
<https://bugs.python.org/issue46
Change by Tim Peters :
--
keywords: +patch
pull_requests: +29037
stage: needs patch -> patch review
pull_request: https://github.com/python/cpython/pull/30856
___
Python tracker
<https://bugs.python.org/issu
Change by Tim Peters :
--
assignee: -> tim.peters
nosy: +gregory.p.smith, mark.dickinson
___
Python tracker
<https://bugs.python.org/issue46504>
___
___
Py
Tim Peters added the comment:
New changeset 7c26472d09548905d8c158b26b6a2b12de6cdc32 by Tim Peters in branch
'main':
bpo-46504: faster code for trial quotient in x_divrem() (GH-30856)
https://github.com/python/cpython/commit/7c26472d09548905d8c158b26b6a2b
Tim Peters added the comment:
New changeset 7c26472d09548905d8c158b26b6a2b12de6cdc32 by Tim Peters in branch
'main':
bpo-46504: faster code for trial quotient in x_divrem() (GH-30856)
https://github.com/python/cpython/commit/7c26472d09548905d8c158b26b6a2b
Change by Tim Peters :
--
resolution: -> fixed
stage: patch review -> resolved
status: open -> closed
___
Python tracker
<https://bugs.python.or
Change by Tim Peters :
--
nosy: +tim.peters
___
Python tracker
<https://bugs.python.org/issue46524>
___
___
Python-bugs-list mailing list
Unsubscribe:
Tim Peters added the comment:
As a general thing, I expect people on Windows always run the tests with
multiple processes. In which case it would be generally helpful to start the
longest-running tests first. As is, because of its late-in-the-alphabet name,
"test_peg_generator" ge
Tim Peters added the comment:
Charliz, please do! I have no idea why Raymond just stopped. He even deleted
his initial message here, saying "I relied on this for many years. So, yet it
would be nice to guarantee it :-)".
Best I can tell, nothing has changed: lots of people have
Tim Peters added the comment:
New changeset f10dafc430279b4e6cf5b981ae3d1d76e8f431ad by Crowthebird in branch
'main':
bpo-46407: Optimizing some modulo operations (GH-30653)
https://github.com/python/cpython/commit/f10dafc430279b4e6cf5b981ae3d1d
Tim Peters added the comment:
I only merged the split-off PR that added new remainder-only functions. Still
thinking about the `1 << n` and `2**n` one.
--
assignee: -> tim.peters
resolution: -> fixed
stage: patch review -> resolved
status:
New submission from Tim Peters :
Our internal base conversion algorithms between power-of-2 and non-power-of-2
bases are quadratic time, and that's been annoying forever ;-) This applies to
int<->str and int<->decimal.Decimal conversions. Sometimes the conversion is
im
Tim Peters added the comment:
Dennis, partly, although that was more aimed at speeding division, while the
approach here doesn't use division at all.
However, thinking about it, the implementation I attached doesn't actually for
many cases (it doesn't build as much of th
Tim Peters added the comment:
Changed the code so that inner() only references one of the O(log log n) powers
of 2 we actually precomputed (it could get lost before if `lo` was non-zero but
within `n` had at least one leading zero bit - now we _pass_ the conceptual
width instead of
Tim Peters added the comment:
The test case here is a = (1 << 1) - 1, a solid string of 100 million 1
bits. The goal is to convert to a decimal string.
Methods:
native: str(a)
numeral: the Python numeral() function from bpo-3451's div.py after adapting to
use
Tim Peters added the comment:
Ha! This will never die. More discussion in bpo-46558.
Ya, I already closed it, but don't want to. I opened it to begin with to record
an int->str method that doesn't use division, so it didn't really belong on
this report.
What if we _did
Tim Peters added the comment:
Addendum: the "native" time (for built in str(a)) in the msg above turned out
to be over 3 hours and 50 minutes.
--
___
Python tracker
<https://bugs.python.o
Tim Peters added the comment:
The factorial of a million is much smaller than the case I was looking at. Here
are rough timings on my box, for computing the decimal string from the bigint
(and, yes, they all return the same string):
native: 475seconds (about 8 minutes)
numeral: 22.3
Tim Peters added the comment:
> todecstr treats it as an "input" conversion instead, ...
Worth pointing this out since it doesn't seem widely known: "input" base
conversions are _generally_ faster than "output" ones. Working in the
destination base (
Tim Peters added the comment:
Exponentiation has higher precedence (binds more tightly) than unary minus, so
the expression groups as -(2**2).
Virtually all computer languages (those that _have_ an exponentiation operator)
do the same. For example, here from wxMaxima:
(%i1) -2**2;
(%o1) -4
Tim Peters added the comment:
Raised the priority back to normal.
I agree with Dennis's observation that PyDict_Next is safe, provided it's used
as intended: it returns borrowed references, but to things that absolutely are
legitimate at the time. In the presence of mutations,
Tim Peters added the comment:
Introducing some kind of optional timeout is too involved to just drop in
without significant discussion and design effort first. If you want to pursue
this, please bring it up on the python-ideas mailing list.
My first take: it wouldn't really help, be
Tim Peters added the comment:
GMP's mpz has 18 functions of this form. These are the 6 "ceiling" flavors:
c_divmod
c_div
c_mod
c_divmod_2exp
c_div_2exp
c_mod_2exp
The suggestion here is for c_div.
There are 6 more for floor rounding (with prefix "f_" instead of
Tim Peters added the comment:
I've been keeping my eyes open. The only mariginally relevant thing I've
noticed is Hart's "one line factoring" method:
http://wrap.warwick.ac.uk/54707/1/WRAP_Hart_S1446788712000146a.pdf
That wants the _ceiling_ of the square root. And
Tim Peters added the comment:
I expect "obviousness" is mostly driven by background here. You know, e.g.,
that ceil(x) = -floor(-x) for any real x, and the application to integer
division is just a special case of that. I expect programmers mostly don't know
that, though. An
Tim Peters added the comment:
SequenceMatcher looks for the longest _contiguous_ match. "UNIQUESTRING" isn't
the longest by far when autojunk is False, but is the longest when autojunk is
True. All those bpopular characters then effectively prevent finding a longer
mat
Tim Peters added the comment:
We can't change defaults without superb reason - Python has millions of users,
and changing the output of code "that works" is almost always a non-starter.
Improvements to the docs are welcome.
In your example, try running this code after usin
Tim Peters added the comment:
The `decimal` module intends to be a faithful implementation of external
standards. The identity
x == (x // y) * y + x % y
isn't a minor detail, it's the dog on which all else is but a tail ;-)
It's why Guido picked -7 // 4 = -2 in Python[1]. Th
Tim Peters added the comment:
Eryk, I don't think that workaround is solid on Windows in all cases. For
example, if .join() is called with a timeout, the same timeout is passed to
lock.acquire(block, timeout). If the acquire() in fact times out, but the store
to the `acquired` variab
Tim Peters added the comment:
Na, we've been doing excruciatingly clever stuff to deal with thread shutdown
for decades, and it always proves to be wrong in some way. Even if code like
except:
if lock.locked():
lock.release()
self._stop()
raise
did work as hope
Tim Peters added the comment:
> Maybe add an `acquire_and_release()` method
Bingo - that should do the trick, in an "obviously correct" way. Of course it's
of limited applicability, but fine by me.
Will you open a
Tim Peters added the comment:
While bundling the lock.release() into C makes that bulletproof, is there a
bulletproof way to guarantee that `self._stop()` gets called if the
acquire_and_release() succeeds? Offhand, I don't see a reason for why that
isn't just as vulnerable
Tim Peters added the comment:
>> is there a bulletproof way to guarantee that `self._stop()` gets
>> called if the acquire_and_release() succeeds?
> I don't think it's critical.
Agreed! Anything at the Python level that cares whether the thread
Tim Peters added the comment:
> It's nice that _maintain_shutdown_locks() gets
> called in _stop(), but the more important call site is in
> _set_tstate_lock().
I didn't have that in mind at all. What at the Python level cares whether the
thread is alive? Well. is_alive()
Tim Peters added the comment:
Unassigning myself - I have no insight into this.
I suspect the eternally contentious issue 7946 is related.
--
___
Python tracker
<https://bugs.python.org/issue46
Tim Peters added the comment:
New changeset e466faa9df9a1bd377d9725de5484471bc4af8d0 by Charlie Zhao in
branch 'main':
bpo-45735: Promise the long-time truth that `args=list` works (GH-30982)
https://github.com/python/cpython/commit/e466faa9df9a1bd377d9725de54844
Tim Peters added the comment:
I don't know that there's a good use case for this. For floating addition,
tree-based summation can greatly reduce total roundoff error, but that's not
true of floating multiplication.
The advantage for prod(range(2, 50001)) doesn't really
Tim Peters added the comment:
Hi. "It's pretty good for a lot of things" is precisely what I'm questioning.
Name some, and please be specific ;-)
Tree reduction is very popular in the parallel processing world, for obvious
reasons. But we're talking about a sing
Tim Peters added the comment:
Too abstract for me to find compelling. I suspect the title of this report
referenced "math.prod with bignums" because it's the only actual concrete use
case you had ;-)
Here's another: math.lcm. That can benefit for the same reason as ma
Tim Peters added the comment:
About runtime, you're right. I did a ballpark "OK, if there are N incoming
values, the inner loop has to go around, for each one, looking for a NULL,
across a vector of at most log2(N) entries. So N * log2(N)". But, in fact, it's
highly s
Tim Peters added the comment:
> the total number of trailing 1 bits in the integers from 1
> through N inclusive is N - N.bit_count()
Sorry, that's the total number of trailing 0 bits. The total number of trailing
1 bits is (N+1) - (N+1
Tim Peters added the comment:
FWIW, I doubt there's a real issue here. Objects in Python consume a lot more
than a byte or two of memory, so the index range of a Python list is generally
a lot less than ssize_t allows for. In other words, quantify "large" in "large
arr
1 - 100 of 1332 matches
Mail list logo
