[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: Committed in r81196. Thanks, everyone! -- status: open -> closed ___ Python tracker ___ ___ Python-

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: Sorry I didn't realize that ... -- ___ Python tracker ___ ___ Python-bugs-list mailing list Un

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: But factorial_partial_product and factorial_odd_part both exist: the former is just computing the product of all odd integers in the given interval, while the latter computes the odd part of factorial(n). I've double checked the comments and they still look

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: s/partial_product/odd_part/ It looks like you made this change in some places but not all. On May 15, 2010, at 11:16 AM, Mark Dickinson wrote: > > Mark Dickinson added the comment: > > Okay, thanks. I'm still not seeing what's wrong with this, thou

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: Okay, thanks. I'm still not seeing what's wrong with this, though (sorry for being slow :( ) -- ___ Python tracker ___ _

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: Sorry for terseness. Sending it from my phone. The line was in factorial4.patch: + * The factorial_partial_product function computes the product of all odd j in >> > > Hmm. I can't find it. Can you be more specific? > > -- Added file: http:

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: > There is one place in the notes still referring to > factorial_part_product. Hmm. I can't find it. Can you be more specific? I'll fix the spaces before 'Someday'. -- ___ Python tracker

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: The comment for bit_length is missing a space or two: "Objects/longobject.c.Someday" -- ___ Python tracker ___ ___

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: There is one place in the notes still referring to factorial_part_product. -- nosy: +Alexander.Belopolsky ___ Python tracker ___ ___

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: Ah; Alexander's right: I was misremembering. An extra comma in an *enum* list isn't allowed (cf. issue 5889); an extra comma in an array initializer is. I'll rewrite that bit. -- ___ Python tracker

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: > It's a matter of taste, but I was taught that C allows trailing commas > in initializers specifically for the cases like this to avoid using a > leading comma. Unfortunately, I think C89 doesn't allow for this, and there are tracker issues about Python compi

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: On Sat, May 15, 2010 at 6:32 AM, Mark Dickinson wrote: > New patch (factorial3.patch) addressing all of Alexander's points except the > one about including Python source somewhere. Thanks for making the changes. I think we converged to a really neat im

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: And the same patch, but with a (deliberately simple) pure Python version of the algorithm in test_math.py. -- Added file: http://bugs.python.org/file17352/factorial4.patch ___ Python tracker

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: New patch (factorial3.patch) addressing all of Alexander's points except the one about including Python source somewhere. I also expanded the lookup table to 20 entries on LP64 systems. -- Added file: http://bugs.python.org/file17351/factorial3.patch

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: Some more ... - Mark's notes talk about "odd-part-of-factorial". It would be clearer if r variable in math_factorial() was called odd_part. - I would also rename nminusnumbits to ntwos or something else that explains what it is rather than how it is com

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: Mark, It is always a pleasure to read your algorithm descriptions! Just a few comments: - It would be nice if a pure python implementation would make it somewhere in the code base. Maybe it can be placed in comments in C file or added to the test module

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: Looks good. -- ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: Okay, here's what I'm planning to commit (tomorrow), in case anyone wants to give it one last check. I've added some comments half-explaining the algorithm used (just in case the referenced URL goes out of existence). I made a couple of other minor changes

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: On Fri, May 14, 2010 at 3:25 PM, Mark Dickinson wrote: > The patch looks good.  Just one issue: I think the overflow check for > num_operands * last_bit is bogus.  It's possible for the product to overflow > and still end up being less than num_operands.  H

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: > it's the *size* of the small bitfield *smallest -- ___ Python tracker ___ ___ Python-bugs-list ma

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: One other note: I find the bit numbering in find_last_set_bit peculiar: isn't the least significant bit usually bit 0? (Well, okay some people number the msb 0, but that's just weird. :) I know the ffs and fls functions also start their bit numbering at o

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: Daniel, sorry: I spent so long writing that last message that I didn't read your update until now. The new patch looks fine; same caveat about the overflow check as before. Let me know when you want me to apply this. --

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: The patch looks good. Just one issue: I think the overflow check for num_operands * last_bit is bogus. It's possible for the product to overflow and still end up being less than num_operands. How about: if (num_operands <= BITS_IN_LONG && num_operands * la

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: I made a few minor updates to the patch. It redefines partial_product to product(range(n, m, 2)), which saved me a few operations and is more Pythonic than what I had before. :-) (Not quite what Alexander was after, but it's a step in the right direction.

[issue8692] Use divide-and-conquer for faster factorials

Changes by Daniel Stutzbach : Removed file: http://bugs.python.org/file17338/factorial.patch ___ Python tracker ___ ___ Python-bugs-list mailin

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: > I still believe, however that an iterative version can benefit .. s/iterative/recursive/ -- ___ Python tracker ___

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky 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

[issue8692] Use divide-and-conquer for faster factorials

Changes by Alexander Belopolsky : Removed file: http://bugs.python.org/file17312/factorial3.py ___ Python tracker ___ ___ Python-bugs-list mail

[issue8692] Use divide-and-conquer for faster factorials

Changes by Alexander Belopolsky : Removed file: http://bugs.python.org/file17310/factorial.py ___ Python tracker ___ ___ Python-bugs-list maili

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: Attached is an updated patch. In addition to the code cleanup and bug fix suggestions, it includes a new base-case for factorial_partial_product. Instead of: if (n >= m) return n if (n + 2 == m) return n*m otherwise divide-and-conquer It now does:

[issue8692] Use divide-and-conquer for faster factorials

Changes by Daniel Stutzbach : Removed file: http://bugs.python.org/file17300/factorial.patch ___ Python tracker ___ ___ Python-bugs-list mailin

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: > I am attaching an iterative version in C patch. Thanks for doing this comparison. > The performance appears to be identical to Daniel's with no small > integer multiplication optimization. Okay, let's stick with the recursive version, then. It has the adv

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: > Daniel Stutzbach added the comment: > > Speaking of getting side-tracked, I didn't see an answer to a question I > asked earlier.  I'd like to get some feedback before I proceed with revising > the patch. > > For the find-last-set-bit (to replace log2) and

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: Mark> Does anyone feel like doing a speed comparison between Daniel's C patch and a version with a direct no-frills iterative version of factorial_part_product (i.e., just a simple 'for (i = n; i <= m; i += 2) { }? Not a direct answer to your questio

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: Attached is a simple bash script to run math.factorial(n) through timeit for several values of n. It makes comparing the speed of different builds MUCH easier. -- Added file: http://bugs.python.org/file17329/factorial-speed.sh

[issue8692] Use divide-and-conquer for faster factorials

Changes by Alexander Belopolsky : Added file: http://bugs.python.org/file17328/factorial-precompute-partials.patch ___ Python tracker ___ ___ P

[issue8692] Use divide-and-conquer for faster factorials

Changes by Alexander Belopolsky : Removed file: http://bugs.python.org/file17325/factorial-precompute-partials.patch ___ Python tracker ___ __

[issue8692] Use divide-and-conquer for faster factorials

Changes by Alexander Belopolsky : Removed file: http://bugs.python.org/file17327/factorial-precompute-partials.patch ___ Python tracker ___ __

[issue8692] Use divide-and-conquer for faster factorials

Changes by Alexander Belopolsky : Added file: http://bugs.python.org/file17327/factorial-precompute-partials.patch ___ Python tracker ___ ___ P

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: Attached is a patch to improve the unit tests for the factorial function. To compute the check value, it keeps a running total instead of recomputing the factorial from scratch inside the loop. It checks up to range(999) and is quite fast. The previous co

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: Oh, my! How did that last term get into precomputed list?! It should have been precomputed[] = {3, 15, 5, 35, 315, 63, 693, 9009, 1287, 19305, 328185, 36465, 692835, 14549535, 1322685, 30421755, 760543875, 58503375, 1579591125ul}; T

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: It's a little too clever though. It gives the wrong answer for 29!. I'll have a revised version of my patch done sometime tomorrow. -- ___ Python tracker __

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: That's a clever idea. Do you have a Python script that generates the precomputed values? -- ___ Python tracker ___ __

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: On Thu, May 13, 2010 at 5:58 PM, Mark Dickinson wrote: > Optimizations that speed up, say, factorial(n) for n <= 1000 would seem more >valuable. I am attaching a variant of my patch which precomputes partial products that fit in 32 bit unsigned int. T

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: On Wed, May 12, 2010 at 3:47 PM, Mark Dickinson wrote: >... > Realistically though, I don't see an iterative version of > factorial_part_product as > an option for the C patch, without a significant increase in complexity. >  Daniel's > current patch i

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: On Thu, May 13, 2010 at 6:09 PM, Daniel Stutzbach wrote: .. > Speaking of getting side-tracked, I didn't see an answer to a question I asked > earlier.  I'd like to get some feedback before I proceed with revising the > patch. I did not respond because

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: Speaking of getting side-tracked, I didn't see an answer to a question I asked earlier. I'd like to get some feedback before I proceed with revising the patch. For the find-last-set-bit (to replace log2) and count-set-bits operations, would it be worthwhi

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: > I would expect that for large factorials the performance will be > determined by the number of long multiplications and the size of > multiplicands. Okay, but I don't think we should care about the performance of *really* large factorials for Python. People

[issue8692] Use divide-and-conquer for faster factorials

Changes by Alexander Belopolsky : Removed file: http://bugs.python.org/file17313/factorial4.py ___ Python tracker ___ ___ Python-bugs-list mail

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: On Thu, May 13, 2010 at 5:31 PM, Mark Dickinson wrote: > And why are we trying to speed up the pure Python factorial code here? I would expect that for large factorials the performance will be determined by the number of long multiplications and the size

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: And why are we trying to speed up the pure Python factorial code here? I don't imagine that those speed differences are going to translate well to C. -- ___ Python tracker __

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: Does anyone feel like doing a speed comparison between Daniel's C patch and a version with a direct no-frills iterative version of factorial_part_product (i.e., just a simple 'for (i = n; i <= m; i += 2) { }? I have a sneaking suspicion that the iterative v

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: Isn't it amazing how fast one can make incorrect code? ;-) Here is a fixed version of my partial_product3, but now it is no faster than partial_product. def partial_product3(j, i): a = [l << 1 | 1 for l in range(j, i + 1)] n = len(a) while 1:

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: Daniel, Your variant does not seem to work: >>> def partial_product3(j, i): ... a = [l << 1 | 1 for l in range(j, i + 1)] ... n = len(a) ... while 1: ... if n == 1: ... return a[0] ... half = n//2 ... for k

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: After experimenting with changing the order of the multiplications and not having much luck, I went back and looked for other differences in Alexander's Python functions that might cause the speed difference. I believe partial_product2 is fast because it p

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: On Wed, May 12, 2010 at 3:34 PM, Alexander Belopolsky wrote: > I wonder if one could write an elegant recursive version that would > multiply first by last in partial_product. That could be done with a three-parameter partial_product, where the third paramet

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: Here is one more datapoint. $ ./python.exe -m timeit -s "import factorial4 as fm; fm.partial_product = fm.partial_product; f = fm.factorial " "f(1)" 10 loops, best of 3: 66.1 msec per loop [32794 refs] $ ./python.exe -m timeit -s "import factorial4 as

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: Interesting---thanks for the analysis! Realistically though, I don't see an iterative version of factorial_part_product as an option for the C patch, without a significant increase in complexity. Daniel's current patch is remarkably clean and simple, and I'

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky 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 piec

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: >I was planning to add a "if (dx > (double) LONG_MAX)" check. Would > that be sufficient? Hmm. It's subtle. On an LP64 machine, LONG_MAX will be 2**63-1, which isn't exactly representable as a double. So (double) LONG_MAX would likely be 2.0**63 exactly (

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: On Wed, May 12, 2010 at 12:59 PM, Mark Dickinson wrote: > (4) And please do restore the PyLong_FromDouble line in the main routine, > rather than using a C double-to-long cast.  The direct conversion again leads > to undefined behaviour for large doubles (c

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: > (cf. C99 6.3.1.4,p2). Oops. C99 6.3.1.4,p1. That'll teach me not to cite chapter and verse. -- ___ Python tracker ___ _

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: Now that I've looked at the patch properly: I'm +1 on including some version of this patch. At the time that the original math.factorial went in (see issue 2138) we were hurrying a bit to get it in before the first 2.6 beta, so ended up with a simple impleme

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: On Wed, May 12, 2010 at 10:31 AM, Alexander Belopolsky wrote: > if ((k & 1) != 1) >          k = k - 1; > > looks odd to me. Maybe k += (k & 1) - 1? If we change the logic slightly to put the odd entry on the right instead of the left, we can do: k

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: Thank you both for the valuable feedback. I'm working on a revised patch that incorporates your many suggestions. I decided to use an iterative version for two reasons: - the reference has a note at the bottom in a tiny font suggesting it - I found it count

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: On Tue, May 11, 2010 at 10:19 PM, Alexander Belopolsky wrote: .. > Another readability nit:  for me k % 2 == 0 is a more readable check > for even number than (k & 1) != 1.  Performance-wise the two choices > are the same, and either can be improved by co

[issue8692] Use divide-and-conquer for faster factorials

Changes by Raghuram Devarakonda : -- nosy: +draghuram ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mai

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: On Tue, May 11, 2010 at 5:58 PM, Mark Dickinson wrote: > Yes, I'm interested in seeing the pure Python version. Here is my translation of the reference implementation. > It could go into test_math, and would be a useful form of documentation. Note tha

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: 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

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: On Tue, May 11, 2010 at 10:19 PM, Alexander Belopolsky wrote: .. > Similarly, while unlikely to improve performance, I would prefer not > to use any bit-trick implementation of ilog2 (in a separate function, > of course) instead of calling floating point

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: On Tue, May 11, 2010 at 9:07 PM, Daniel Stutzbach wrote: > > Daniel Stutzbach added the comment: > > On Tue, May 11, 2010 at 7:38 PM, Alexander Belopolsky > wrote: >> Speaking of micro-optimizations, did you consider a better than naive >> algorithm for

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: On Tue, May 11, 2010 at 7:38 PM, Alexander Belopolsky wrote: > Speaking of micro-optimizations, did you consider a better than naive > algorithm for "Count the number of set bits in n" in your patch? > HAKMEM 169 comes to mind and being a divide and conquer t

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: On Tue, May 11, 2010 at 7:15 PM, Alexander Belopolsky wrote: > The main value in setting a theoretically justified limit is that > overflow exception can carry a meaningful message, e.g. "factorial > result would have too many digits", rather than an unhelpfu

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: On Tue, May 11, 2010 at 7:42 PM, Daniel Stutzbach wrote: .. > Isn't that adding an extra check in every case ... Speaking of micro-optimizations, did you consider a better than naive algorithm for "Count the number of set bits in n" in your patch? HAKMEM

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: On Tue, May 11, 2010 at 7:42 PM, Daniel Stutzbach wrote: .. > Isn't that adding an extra check in every case to speed up a > you-can't-seriously-expect-that-to-work corner case? > The check is cheap - just a machine integer comparison, so I would not eve

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: On Tue, May 11, 2010 at 5:33 PM, Alexander Belopolsky wrote: > It seems to me that the value of n for which number of digits will exceed > sys.maxsize can be estimated fairly accurately using Stirling formula.  Only > two values are relevant in practice - o

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: On Tue, May 11, 2010 at 11:33 PM, Alexander Belopolsky wrote: > It seems to me that the value of n for which number of digits will exceed > sys.maxsize can be estimated fairly accurately using Stirling formula.  Only > two values are relevant in practice - on

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: I also started to wonder if a tighter upper limit for an acceptable argument can be found. In discussion of issue2138 I saw the following exchange: """ > Should there be some upper limit on the argument math.factorial would take? I'd say not. Any such

[issue8692] Use divide-and-conquer for faster factorials

Mark Dickinson added the comment: Yes, I'm interested in seeing the pure Python version. It could go into test_math, and would be a useful form of documentation. Are there sufficient tests already in test_math.py to exercise the code thoroughly, or are more needed? I'll try to find time to

[issue8692] Use divide-and-conquer for faster factorials

Daniel Stutzbach added the comment: On Tue, May 11, 2010 at 4:18 PM, Alexander Belopolsky wrote: > While the error message is wrong in both cases, I think OverflowError is a > better exception in this case and there should not be a difference between > math.factorial(2.**63) and math.factoria

[issue8692] Use divide-and-conquer for faster factorials

Alexander Belopolsky added the comment: I've noticed that your patch changes >>> math.factorial(2.**63) Traceback (most recent call last): File "", line 1, in OverflowError: Python int too large to convert to C long to >>> math.factorial(2.**63) Traceback (most recent call last): File "

[issue8692] Use divide-and-conquer for faster factorials

New submission from Daniel Stutzbach : (Making an educated guess about who to add to the Nosy list) Attached is a patch to improve math.factorial by using a divide-and-conquer algorithm. The old algorithm performs n-1 multiplications, mostly on numbers with a very large number of digits. The