[issue15391] Add bitlength function to the math module
New submission from anon unluckykit...@mailinator.com: Many numeric algorithms require knowing the number of bits an integer has (for instance integer squareroots). For example this simple algorithm using shifts is O(n^2): def bitl(x): x = abs(x) n = 0 while x 0: n = n+1 x = x1 return n A simple O(n) algorithm exists: def bitl(x): if x==0: return 0 return len(bin(abs(x)))-2 It should be possible find the bit-length of an integer in O(1) however. O(n) algorithms with high constants simply don't cut it for many applications. That's why I would propose adding an inbuilt function bitlength(n) to the math module. bitlength(n) would be the integer satisfying bitlength(n) = ceil(log2(abs(n)+1)) Python more than ever with PyPy progressing is becoming a great platform for mathematical computation. This is an important building block for a huge number of algorithms but currently has no elegant or efficient solution in plain Python. -- components: Library (Lib) messages: 165818 nosy: anon priority: normal severity: normal status: open title: Add bitlength function to the math module type: enhancement ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue15391 ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
New submission from anon: For many numeric algorithms it's useful to be able to read individual bits at a location in an integer. Currently there is no efficient way to do this. The following function is the closest to this: def bit_at(i, n): return (in)1 However in computing the intermediate result in we must spend O(b-n) time at least (where b is n.bit_length()). It should be possible to read bits in O(1) time. Adding int.bit_at(n) would complement int.bit_length(). I would suggest making the semantics of i.bit_at(n) the same as (in)1. Although the exact meaning when i is negative should be considered. Real world uses of bit_at include binary exponentiation and bit counting algorithms. -- messages: 205421 nosy: anon priority: normal severity: normal status: open title: int.bit_at(n) - Accessing a single bit in O(1) type: enhancement versions: Python 3.5 ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: I like the i.bits_at(pos, width=1) suggestion. Unless slicing is chosen instead this seems the most future-proof idea. I think slicing semantically seems wrong but it might be more elegant. It might also make catching errors harder (in the case where an int is sent to a function that does slicing and now won't fail with a TypeError). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: I didn't really consider floats. bit_length() is only provided to ints for example. I think a better solution to pick apart floats would be a function similar to math.frexp, if it isn't already sufficient. float.bits_at(pos, width) seems a worse solution because the position of each bit would be arbitrary. But I have no major objection against it being extended to floats. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: Then I think we're in agreement with regards to bits_at. :) What should happen next? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: Antoine, I don't suggest that since you commonly want a fixed number of bits. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment:
Here is my very rough attempt at bits_at. It doesn't handle negative numbers
and I am not sure it's safe. This was my first time using Python internals.
Objects/longobject.c:
static PyObject *
long_bits_at(PyLongObject *v, PyObject *args)
{
PyLongObject *z = NULL;
if(Py_SIZE(v) 0)
{
PyLongObject *a1, *a2;
Py_RETURN_NOTIMPLEMENTED;
a1 = (PyLongObject *)long_invert(v);
//Handle the case where a1 == NULL
a2 = (PyLongObject *)long_bits_at(a1, args);
//Handle the case where a2 == NULL
Py_DECREF(a1);
Py_DECREF(a2);
//return a2 ^ ((1 width) - 1)
}
else
{
PyObject *at_ = NULL;
PyObject *width_ = NULL;
ssize_t at, width, i, j, bitsleft, step;
ssize_t wordshift, size, newsize, loshift, hishift;
digit mask;
if (!PyArg_UnpackTuple(args, bits_at, 1, 2, at_, width_))
return NULL;
at = PyLong_AsSsize_t((PyObject *)at_);
if (at == -1L PyErr_Occurred())
return NULL;
if (at 0) {
PyErr_SetString(PyExc_ValueError, negative index);
return NULL;
}
if (width_ == NULL)
width = 1;
else {
width = PyLong_AsSsize_t((PyObject *)width_);
if (width == -1L PyErr_Occurred())
return NULL;
if (width 0) {
PyErr_SetString(PyExc_ValueError, negative bit count);
return NULL;
}
}
wordshift = at / PyLong_SHIFT;
size = ABS(Py_SIZE(v));
newsize = (width-1) / PyLong_SHIFT + 1;
if (newsize size-wordshift)
newsize = size-wordshift;
if (newsize = 0)
return PyLong_FromLong(0L);
loshift = at % PyLong_SHIFT;
hishift = PyLong_SHIFT - loshift;
bitsleft = width;
z = _PyLong_New(newsize);
if (z == NULL)
return NULL;
for (i = 0, j = wordshift; i newsize; i++, j++) {
step = bitslefthishift ? bitsleft : hishift;
mask = ((digit)1 step) - 1;
z-ob_digit[i] = (v-ob_digit[j] loshift) mask;
bitsleft -= step;
if (j+1 size) {
step = bitsleftloshift ? bitsleft : loshift;
mask = ((digit)1 step) - 1;
z-ob_digit[i] |= ((v-ob_digit[j+1] mask) hishift);
bitsleft -= step;
}
}
z = long_normalize(z);
}
return (PyObject *)z;
}
PyDoc_STRVAR(long_bits_at_doc,
int.bits_at(pos, width=1) - int\n\
\n\
Equivalent to (int pos) ((1 width) - 1).);
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue19915
___
___
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: Here are some inadequate tests to add to Lib/test/test_long.py def test_bits_at(self): def bits_at(n, pos, width=1): return (npos) ((1 width) - 1) for n in [123, 777, (135)|(130)|(125)]: for i in range(50): for j in range(20): self.assertEqual(n.bits_at(i, j), bits_at(n, i, j)) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: Both segments of code are public domain. It would be great if someone could review them, improve them and produce a proper patch. I didn't handle the negative case, which I hope someone else can add. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: Some of the code may be under Python's license though. So I should clarify that only MY parts of the two samples of code are public domain. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: Tim, I'm sorry to hear you can't accept my patch. I am afraid I want to stay anonymous. You have my word that I wrote the two code segments above (based on code already in CPython) and that I put them in the public domain. But I appreciate that the word of `anon` may be worth nothing to you. For what it is worth I could have used a fake name anyway. If you can't accept them, may I request someone else implement the proposal? This may be for the best anyway since I am unfamiliar with CPython internals. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: Thank you! I will try to help in ways that I can such as testing. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: From what I can tell it's fairly easy to just add bits_at to int. Indeed something like a mutable int type might be nice but that's really outside the scope of this. And adding bits_at to int would still be desirable anyway. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: I think the case where i is negative can be handled by bits_at(i, pos, width) = bits_at(~i, pos, width) ^ ((1 width) - 1) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: I noticed feature freeze for 3.5 is in May 2015 which is actually only 7-8 months. It'd be really awesome if this feature could make it. Is there anyone who can get this into 3.5? -- status: open - pending ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: Above I included a first attempt however I don't think my code is good and I couldn't figure out the case for negative integers. There's some discussion above about its inclusion. I like your x.bits suggestion actually, assuming x.bits returns an IntBitsView object without copying x in any way. That would suggest that we could do len(x.bits) and probably depreciate x.bit_length(). Any consensus on this? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: Pros for x.bits being a view: - seems slightly cleaner (in my opinion) - can potentially abstract slicing bits without copying the underlying int (e.g. x.bits[2:][4:]) Pros for x.bits being a function: - Victor's point - no need to depreciate x.bit_length - no need to create a View object and probably faster? - easier to implement -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: Giving it more thought: to get the int we'd need something like int(x.bits[2:][4:]) which seems quite annoying for the general case of int(x.bits[0:52]). So actually I'm not sure that views would add any more abstraction for their extra complexity without becoming a bit unwieldy. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: @Georg: I don't think it would be as common but do agree it'd be useful. I think it can be implemented efficiently in pure Python currently. def with_bits(i, value, pos, width=1): width = min(width, value.bit_length()) mask = ((1 width) - 1) v = value mask i = i ~(mask pos) return i | (v pos) -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: All I had meant by depreciating was changing the x.bit_length documentation to point towards len(x.bits). -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: That's something that a Python comitter would have to do isn't it? -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: Since I'm not familiar with the process I'd request someone creates the PEP. But if really necessary I can try. I just really want to see this in Python 3.5 - it's really essential to a number of scientific methods. I know several open source projects that would benefit from it. -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: I'm struggling to get time for this. I hope someone else can take responsibility. Sorry :-( -- ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue19915 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue24203] Depreciate threading.Thread.isDaemon etc
New submission from anon: In threading.Thread isDaemon, setDaemon, getName, setName are not needed since 2.6 (preferring directly changing daemon or name instead). They should probably be depreciated in 3.5 and removed later. isAlive has already been removed. -- messages: 243277 nosy: anon priority: normal severity: normal status: open title: Depreciate threading.Thread.isDaemon etc ___ Python tracker rep...@bugs.python.org http://bugs.python.org/issue24203 ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue19915] int.bit_at(n) - Accessing a single bit in O(1)
anon added the comment: Any update on this? -- ___ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue19915> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue24203] Depreciate threading.Thread.isDaemon etc
anon added the comment: Any consensus? -- ___ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue24203> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
[issue38023] Deal better with StackOverflow exception when debugging
New submission from almenon anon : Code that runs fine in the command line can crash in the debugger Note that because https://bugs.python.org/issue10933 is not fixed yet I'm assuming this applies to all python 3 versions but it was confirmed in python 3.6 See https://github.com/microsoft/ptvsd/issues/1379: @fabioz says it better than I could: > This is really a CPython bug, not ptvsd (CPython is crashing because of a > stack overflow when the stack overflow is thrown inside a tracing function -- > because the user code already recursed too much). > As a note, the debugger is even disabled on the face of a stack overflow > (see: https://bugs.python.org/issue10933), so, even if it didn't crash, > things wouldn't work very well from that point onwards... > Maybe we could try to detect that a stack overflow is about to happen and > notify about it right before it happens in the debugger so that users could > know that the debugger would stop (note that this is actually pretty hard to > do from the debugger without killing performance because we don't have a > stack in the debugger as we try to run with frames untraced whenever possible > and I don't think there's a python API that provides the size of the stack in > a fast way -- but maybe I'm wrong, I haven't investigated much). > As a note, the ideal place for that would probably be in CPython itself (when > it got to that condition it could raise the recursion limit a bit and call a > handler or at least give some warning if configured to do so as it can be > really puzzling to know that the tracing got disabled because of a swallowed > StackOverflow). > So, I'm going to rename this issue to Deal better with StackOverflow in > CPython so that it reflects better the issue at hand, but it's not currently > high-priority -- that's really a bug in CPython itself and is probably better > fixed there (the workaround in user code -- in this case foxdot -- is not > throwing a StackOverflow). -- components: Interpreter Core messages: 351107 nosy: almenon anon priority: normal severity: normal status: open title: Deal better with StackOverflow exception when debugging type: crash versions: Python 3.5, Python 3.6, Python 3.7, Python 3.8, Python 3.9 ___ Python tracker <https://bugs.python.org/issue38023> ___ ___ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
