This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author belopolsky
Recipients belopolsky, mark.dickinson, rhettinger, stutzbach
Date 2010-05-12.02:19:38
SpamBayes Score 2.0635e-07
Marked as misclassified No
Message-id <>
In-reply-to <>
On Tue, May 11, 2010 at 9:07 PM, Daniel Stutzbach
<> wrote:
> Daniel Stutzbach <> added the comment:
> On Tue, May 11, 2010 at 7:38 PM, Alexander Belopolsky
> <> wrote:
>> Speaking of micro-optimizations, did you consider a better than naive
>> algorithm for "Count the number of set bits in n" in your patch?
>> ..
> I considered it, but decided to stick with code readability and
> portability.

Speaking of readability, with a separate popcount() function, you can
simply write

nminusnumbits_ob = PyLong_FromLong(n - popcount(n))

and eliminate not only the loop, but also num_bits and tmp variables
from math_factorial()

The popcount function can be defined as a __builtin_popcount on GCC
and your loop otherwise.

>  Counting the number of set bits is only done once per
> factorial, so it's not on the critical path.

I agree, performance consideration are completely irrelevant here.

Similarly, while unlikely to improve performance, I would prefer not
to use any bit-trick implementation of ilog2 (in a separate function,
of course) instead of calling floating point log2.  In my head, an
assignment of floating point result to an integer variable always
raises a red flag.

Another readability nit:  for me k % 2 == 0 is a more readable check
for even number than (k & 1) != 1.  Performance-wise the two choices
are the same, and either can be improved by combining k = (n + m) / 2
and k & 1 into one ldiv call.

I have not tried to do it, but my gut feeling is that
factorial_part_product() can benefit from passing semi-open rather
than closed interval.  (Also renaming n and m to start and stop in
this case will help understanding.)
Date User Action Args
2010-05-12 02:19:45belopolskysetrecipients: + belopolsky, rhettinger, mark.dickinson, stutzbach
2010-05-12 02:19:42belopolskylinkissue8692 messages
2010-05-12 02:19:38belopolskycreate