Author belopolsky
Recipients belopolsky, draghuram, mark.dickinson, rhettinger, stutzbach
Date 2010-05-12.19:24:13
SpamBayes Score 3.13806e-07
Marked as misclassified No
Message-id <AANLkTik2C5Ul-NiqZELPgOpDQhS0Vc-4NSUkrMjZa37g@mail.gmail.com>
In-reply-to <1273654207.37.0.409752338492.issue8692@psf.upfronthosting.co.za>
Content
On Wed, May 12, 2010 at 4:50 AM, Mark Dickinson  wrote:
..
> (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.

I am attaching a little study of three different part_product
implementations in python: the recursive one, straight product, and
not-recursive binary division:

$ ./python.exe -m timeit -s "import factorial3 as fm;
fm.partial_product = fm.partial_product; f = fm.factorial " "f(10000)"
10 loops, best of 3: 66.1 msec per loop
$ ./python.exe -m timeit -s "import factorial3 as fm;
fm.partial_product = fm.partial_product1; f = fm.factorial "
"f(10000)"
10 loops, best of 3: 67.6 msec per loop
$ ./python.exe -m timeit -s "import factorial3 as fm;
fm.partial_product = fm.partial_product2; f = fm.factorial "
"f(10000)"
10 loops, best of 3: 43.4 msec per loop

The last one seems to b a clear winner, but I am not certain where the
gain comes from - no recursion or first by last instead of ith by
(i+1)st multiplication.   Also python recursion overhead is probably
different from C.
Files
File name Uploaded
factorial3.py belopolsky, 2010-05-12.19:24:13
History
Date User Action Args
2010-05-12 19:24:16belopolskysetrecipients: + belopolsky, rhettinger, mark.dickinson, draghuram, stutzbach
2010-05-12 19:24:14belopolskylinkissue8692 messages
2010-05-12 19:24:13belopolskycreate