[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

Change by Raymond Hettinger : -- resolution: -> not a bug stage: -> resolved status: open -> closed ___ Python tracker ___ ___

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

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 obvious loop". See

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

Barry Schwartz added the comment: I meant constant bounded -- ___ Python tracker ___ ___ Python-bugs-list mailing list

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

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's not what `O(1)`

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

Barry Schwartz added the comment: Yes. Actually the issue is branching, not order of complexity, because looping at most 64 times is a linear-bounded operation. The methods I point out involve no branching! And so can be rather fast. I don't suggest they be used, but that the listsort.txt

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

Raymond Hettinger added the comment: Presumably the OP is referring to this text: """ `powerloop()` emulates these divisions, 1 bit at a time, using comparisons, subtractions, and shifts in a loop. You'll notice the paper uses an O(1) method instead, but that relies on two things we don't

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

Change by Mark Dickinson : -- nosy: +tim.peters ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue46488] listsort.txt wrongly assumes you cannot calculate leading zeros in O(1) time.

New submission from Barry Schwartz : The Objects/listsort.txt incorrectly implies that it is not possible to compute leading zero bits in O(1) time, using only standard C. For a fixed integer size it can be done, for instance, using de Bruijn sequences. See