Author stutzbach
Recipients belopolsky, mark.dickinson, rhettinger, stutzbach
Date 2010-05-12.01:07:53
SpamBayes Score 0.014089
Marked as misclassified No
Message-id <AANLkTimglGfLBajFp3Kzx5eRInl3z7FjdLbibThQdVc6@mail.gmail.com>
In-reply-to <AANLkTil2JQ6qpoPMlBHo13d9m294iJr4_Ov5m_8fGfSr@mail.gmail.com>
Content
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?
> HAKMEM 169 comes to mind and being a divide and conquer too, it seems
> like a good fit.   Certainly an overkill if used just for
> math.factorial(), but this is probably a useful function to have
> around.

I considered it, but decided to stick with code readability and
portability.  Counting the number of set bits is only done once per
factorial, so it's not on the critical path.

FWIW, the following page has a pretty extensive summary of performance
comparisons of different solutions to the "count the set bits"
problem:
http://www.dalkescientific.com/writings/diary/archive/2008/07/03/hakmem_and_other_popcounts.html
History
Date User Action Args
2010-05-12 01:07:56stutzbachsetrecipients: + stutzbach, rhettinger, mark.dickinson, belopolsky
2010-05-12 01:07:54stutzbachlinkissue8692 messages
2010-05-12 01:07:53stutzbachcreate