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 <AANLkTikg3ykV7gmbvWzBaeH0CFT0v5iXByehtDt3ywmo@mail.gmail.com>
In-reply-to <AANLkTimglGfLBajFp3Kzx5eRInl3z7FjdLbibThQdVc6@mail.gmail.com>
Content
On Tue, May 11, 2010 at 9:07 PM, Daniel Stutzbach
<report@bugs.python.org> wrote:
>
> Daniel Stutzbach <daniel@stutzbachenterprises.com> added the comment:
>
> On Tue, May 11, 2010 at 7:38 PM, Alexander Belopolsky
> <report@bugs.python.org> 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.)
History
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