Author belopolsky
Recipients belopolsky, draghuram, mark.dickinson, rhettinger, stutzbach
Date 2010-05-14.18:05:04
SpamBayes Score 2.88214e-07
Marked as misclassified No
Message-id <1273860307.82.0.964072110155.issue8692@psf.upfronthosting.co.za>
In-reply-to
Content
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.
History
Date User Action Args
2010-05-14 18:05:07belopolskysetrecipients: + belopolsky, rhettinger, mark.dickinson, draghuram, stutzbach
2010-05-14 18:05:07belopolskysetmessageid: <1273860307.82.0.964072110155.issue8692@psf.upfronthosting.co.za>
2010-05-14 18:05:06belopolskylinkissue8692 messages
2010-05-14 18:05:05belopolskycreate