Alexander Belopolsky <belopol...@users.sourceforge.net> added the comment:
I agree, recursive version of partial_product is much simpler to follow. While allocation of all numbers can be avoided in iterative version, doing so would further complicate code with little benefit. I still believe, however that an iterative version can benefit from redefining partial_product to be product(2*i+1 for i in range(start, stop)). Divide and conquer algorithm for that is simply def partial_product(start, stop): length = stop - start .. handle length = 1 and 2 .. middle = start + (length >> 1) return partial_product(start, middle) * partial_product(middle, stop) I would also reconsider the decision of using iterative outer loop. Recursive outer loop matching redefined partial_product() can be written as def loop(n): p = r = 1 if n > 2: p, r = loop(n >> 1) p *= partial_product((n >> 2) + (n >> 1 & 1), (n >> 1) + (n & 1)) r *= p return p, r which I believe is not harder to follow than the iterative alternative and does not require bit_length calculation. I am replacing my python implementation, factorial.py, with the one that uses algorithms outlined above. If there is any interest, I can convert it to C. ---------- Added file: http://bugs.python.org/file17343/factorial.py _______________________________________ Python tracker <rep...@bugs.python.org> <http://bugs.python.org/issue8692> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com