Alexander Belopolsky <belopol...@users.sourceforge.net> added the comment:
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.
----------
Added file: http://bugs.python.org/file17312/factorial3.py
_______________________________________
Python tracker <rep...@bugs.python.org>
<http://bugs.python.org/issue8692>
_______________________________________
import functools
import operator
product = functools.partial(functools.reduce, operator.mul)
def naive_factorial(n):
"""Naive implementation of factorial: product([1, ..., n])
>>> naive_factorial(4)
24
"""
return product(range(1, n+1), 1)
def factorial(n):
"""Implementation of Binary-Split Factorial algorithm
See http://www.luschny.de/math/factorial/binarysplitfact.html
>>> for n in range(20):
... assert(factorial(n) == naive_factorial(n))
>>> import math
>>> assert(factorial(100) == math.factorial(100))
"""
_, r = loop(n)
return r << (n - count_bits(n))
def loop(n):
p = r = 1
for i in range(n.bit_length() - 2, -1, -1):
m = n >> i
if m > 2:
p *= partial_product(((m >> 1) + 1) >> 1, (m - 1) >> 1)
r *= p
return p, r
def partial_product(j, i):
if i == j:
return j << 1 | 1
if i == j + 1:
return (j << 1 | 1) * (i << 1 | 1)
l = i + j >> 1
return partial_product(j, l) * partial_product(l + 1, i)
def partial_product1(j, i):
return product((l << 1 | 1 for l in range(j, i + 1)), 1)
def partial_product2(j, i):
a = [l << 1 | 1 for l in range(j, i + 1)]
n = i - j + 1
p = 1
while n:
n >>= 1
for k in range(n):
a[k] *= a[n-k]
return a[0]
def count_bits(n):
count = 0
while n:
n &= n - 1
count += 1
return count
if __name__ == '__main__':
import doctest
doctest.testmod()
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
