Author mark.dickinson
Recipients belopolsky, mark.dickinson, rhettinger, stutzbach
Date 2010-05-12.08:50:04
SpamBayes Score 2.49309e-07
Marked as misclassified No
Message-id <1273654207.37.0.409752338492.issue8692@psf.upfronthosting.co.za>
In-reply-to
Content
Some quick comments:

(1) Agree about the extra bound checks:  let's treat those as a separate issue and just concentrate on performance here.

(2) log2 isn't portable:  it's not part of C89 (though it is in C99) and I don't think it exists on Windows.  Which is a shame, since it probably *does* reliably work well for boundary cases on most platforms.  I'm embarrassed to read that snippet that Alexander found, but it's true that an alternative like log(n)/log(2) has problems in boundary cases, thanks to the usual floating-point issues.  There's a bit-counting method in the int.bit_length() implementation (in Objects/longobject.c) that could possibly be re-used here.  Alternatively, if a simple for-loop to count bits doesn't have any noticeable impact on speed, then we could use that.

(3) Is the 'count set bits' code a bottleneck?  If not, then it looks fine to me as it is.  Doesn't it just get called once per factorial computation?

(4) I wonder whether the recursion in factorial_part_product slows things down;  it might be interesting to compare with an iterative version (but still one that clumps together small pieces rather than doing lots of small*big multiplies).  It seems possible that the cost of the recursive calls is insignificant compared to the cost of the various Py* calls, though.

(5) Was there a reason for using long rather than unsigned long for the computations?  Using unsigned long would give you an easily computable multiply_cutoff, and save the need for that extra static variable (it could be a macro instead).
History
Date User Action Args
2010-05-12 08:50:07mark.dickinsonsetrecipients: + mark.dickinson, rhettinger, belopolsky, stutzbach
2010-05-12 08:50:07mark.dickinsonsetmessageid: <1273654207.37.0.409752338492.issue8692@psf.upfronthosting.co.za>
2010-05-12 08:50:06mark.dickinsonlinkissue8692 messages
2010-05-12 08:50:04mark.dickinsoncreate