Mark Dickinson dicki...@gmail.com added the comment:
Committed in r81196. Thanks, everyone!
--
status: open - closed
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
___
Mark Dickinson dicki...@gmail.com 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:
Mark Dickinson dicki...@gmail.com 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
Alexander Belopolsky belopol...@users.sourceforge.net added the comment:
On Sat, May 15, 2010 at 6:32 AM, Mark Dickinson rep...@bugs.python.org wrote:
New patch (factorial3.patch) addressing all of Alexander's points except the
one about including Python source somewhere.
Thanks for making
Mark Dickinson dicki...@gmail.com 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
Mark Dickinson dicki...@gmail.com 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
Alexander Belopolsky alexander.belopol...@gmail.com added the comment:
There is one place in the notes still referring to
factorial_part_product.
--
nosy: +Alexander.Belopolsky
___
Python tracker rep...@bugs.python.org
Daniel Stutzbach dan...@stutzbachenterprises.com added the comment:
The comment for bit_length is missing a space or two:
Objects/longobject.c.Someday
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
Mark Dickinson dicki...@gmail.com 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
Alexander Belopolsky alexander.belopol...@gmail.com 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?
Mark Dickinson dicki...@gmail.com added the comment:
Okay, thanks. I'm still not seeing what's wrong with this, though (sorry for
being slow :( )
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
Alexander Belopolsky alexander.belopol...@gmail.com 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 rep...@bugs.python.org
wrote:
Mark Dickinson dicki...@gmail.com added the comment:
Mark Dickinson dicki...@gmail.com 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
Alexander Belopolsky alexander.belopol...@gmail.com added the comment:
Sorry I didn't realize that ...
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
___
Mark Dickinson dicki...@gmail.com added the comment:
Daniel Stutzbach dan...@stutzbachenterprises.com 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
Mark Dickinson dicki...@gmail.com 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.
Changes by Daniel Stutzbach dan...@stutzbachenterprises.com:
Removed file: http://bugs.python.org/file17300/factorial.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
___
Daniel Stutzbach dan...@stutzbachenterprises.com 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
Changes by Alexander Belopolsky belopol...@users.sourceforge.net:
Removed file: http://bugs.python.org/file17310/factorial.py
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
___
Changes by Alexander Belopolsky belopol...@users.sourceforge.net:
Removed file: http://bugs.python.org/file17312/factorial3.py
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
___
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,
Alexander Belopolsky belopol...@users.sourceforge.net added the comment:
I still believe, however that an iterative version can benefit ..
s/iterative/recursive/
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
Changes by Daniel Stutzbach dan...@stutzbachenterprises.com:
Removed file: http://bugs.python.org/file17338/factorial.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
___
Daniel Stutzbach dan...@stutzbachenterprises.com 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
Mark Dickinson dicki...@gmail.com 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
Mark Dickinson dicki...@gmail.com 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.
--
Mark Dickinson dicki...@gmail.com 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
Mark Dickinson dicki...@gmail.com added the comment:
it's the *size* of the small bitfield
*smallest
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
___
Daniel Stutzbach dan...@stutzbachenterprises.com added the comment:
On Fri, May 14, 2010 at 3:25 PM, Mark Dickinson rep...@bugs.python.org 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
Mark Dickinson dicki...@gmail.com 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
Daniel Stutzbach dan...@stutzbachenterprises.com added the comment:
Looks good.
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
___
___
Alexander Belopolsky belopol...@users.sourceforge.net 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
Alexander Belopolsky belopol...@users.sourceforge.net 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
Daniel Stutzbach dan...@stutzbachenterprises.com 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
Alexander Belopolsky belopol...@users.sourceforge.net 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]
...
Daniel Stutzbach dan...@stutzbachenterprises.com 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)]
Mark Dickinson dicki...@gmail.com 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) { multiply running product
by i }?
Alexander Belopolsky belopol...@users.sourceforge.net added the comment:
On Thu, May 13, 2010 at 5:31 PM, Mark Dickinson rep...@bugs.python.org 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
Mark Dickinson dicki...@gmail.com 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
Daniel Stutzbach dan...@stutzbachenterprises.com 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
Alexander Belopolsky belopol...@users.sourceforge.net added the comment:
On Wed, May 12, 2010 at 3:47 PM, Mark Dickinson rep...@bugs.python.org wrote:
...
Realistically though, I don't see an iterative version of
factorial_part_product as
an option for the C patch, without a significant
Alexander Belopolsky belopol...@users.sourceforge.net added the comment:
On Thu, May 13, 2010 at 5:58 PM, Mark Dickinson rep...@bugs.python.org 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
Daniel Stutzbach dan...@stutzbachenterprises.com added the comment:
That's a clever idea. Do you have a Python script that generates the
precomputed values?
--
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
Daniel Stutzbach dan...@stutzbachenterprises.com 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 rep...@bugs.python.org
Alexander Belopolsky belopol...@users.sourceforge.net 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,
Daniel Stutzbach dan...@stutzbachenterprises.com 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
Changes by Alexander Belopolsky belopol...@users.sourceforge.net:
Added file: http://bugs.python.org/file17327/factorial-precompute-partials.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
Changes by Alexander Belopolsky belopol...@users.sourceforge.net:
Removed file:
http://bugs.python.org/file17327/factorial-precompute-partials.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
Changes by Alexander Belopolsky belopol...@users.sourceforge.net:
Removed file:
http://bugs.python.org/file17325/factorial-precompute-partials.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
Changes by Alexander Belopolsky belopol...@users.sourceforge.net:
Added file: http://bugs.python.org/file17328/factorial-precompute-partials.patch
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
Daniel Stutzbach dan...@stutzbachenterprises.com 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:
Alexander Belopolsky belopol...@users.sourceforge.net 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) {
multiply
Mark Dickinson dicki...@gmail.com 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
Alexander Belopolsky belopol...@users.sourceforge.net added the comment:
On Tue, May 11, 2010 at 5:58 PM, Mark Dickinson rep...@bugs.python.org 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,
Changes by Raghuram Devarakonda draghu...@gmail.com:
--
nosy: +draghuram
___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue8692
___
___
Alexander Belopolsky belopol...@users.sourceforge.net added the comment:
On Tue, May 11, 2010 at 10:19 PM, Alexander Belopolsky
rep...@bugs.python.org 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
Daniel Stutzbach dan...@stutzbachenterprises.com 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
Daniel Stutzbach dan...@stutzbachenterprises.com added the comment:
On Wed, May 12, 2010 at 10:31 AM, Alexander Belopolsky
rep...@bugs.python.org 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
Mark Dickinson dicki...@gmail.com 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
Mark Dickinson dicki...@gmail.com 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 rep...@bugs.python.org
http://bugs.python.org/issue8692
Mark Dickinson dicki...@gmail.com 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
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
Mark Dickinson dicki...@gmail.com 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
Alexander Belopolsky belopol...@users.sourceforge.net 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
Daniel Stutzbach dan...@stutzbachenterprises.com added the comment:
On Wed, May 12, 2010 at 3:34 PM, Alexander Belopolsky
rep...@bugs.python.org 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
New submission from Daniel Stutzbach dan...@stutzbachenterprises.com:
(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
Alexander Belopolsky belopol...@users.sourceforge.net added the comment:
I've noticed that your patch changes
math.factorial(2.**63)
Traceback (most recent call last):
File stdin, line 1, in module
OverflowError: Python int too large to convert to C long
to
math.factorial(2.**63)
Daniel Stutzbach dan...@stutzbachenterprises.com added the comment:
On Tue, May 11, 2010 at 4:18 PM, Alexander Belopolsky
rep...@bugs.python.org 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
Mark Dickinson dicki...@gmail.com 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
Alexander Belopolsky belopol...@users.sourceforge.net 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
Mark Dickinson dicki...@gmail.com added the comment:
On Tue, May 11, 2010 at 11:33 PM, Alexander Belopolsky
rep...@bugs.python.org 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
Daniel Stutzbach dan...@stutzbachenterprises.com added the comment:
On Tue, May 11, 2010 at 5:33 PM, Alexander Belopolsky
rep...@bugs.python.org 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
Alexander Belopolsky belopol...@users.sourceforge.net added the comment:
On Tue, May 11, 2010 at 7:42 PM, Daniel Stutzbach
rep...@bugs.python.org 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 -
Daniel Stutzbach dan...@stutzbachenterprises.com added the comment:
On Tue, May 11, 2010 at 7:15 PM, Alexander Belopolsky
rep...@bugs.python.org wrote:
The main value in setting a theoretically justified limit is that
overflow exception can carry a meaningful message, e.g. factorial
result
Daniel Stutzbach dan...@stutzbachenterprises.com added the comment:
On Tue, May 11, 2010 at 7:38 PM, Alexander Belopolsky
rep...@bugs.python.org 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
Alexander Belopolsky belopol...@users.sourceforge.net added the comment:
On Tue, May 11, 2010 at 9:07 PM, Daniel Stutzbach
rep...@bugs.python.org wrote:
Daniel Stutzbach dan...@stutzbachenterprises.com added the comment:
On Tue, May 11, 2010 at 7:38 PM, Alexander Belopolsky
Alexander Belopolsky belopol...@users.sourceforge.net added the comment:
On Tue, May 11, 2010 at 10:19 PM, Alexander Belopolsky
rep...@bugs.python.org wrote:
..
Similarly, while unlikely to improve performance, I would prefer not
to use any bit-trick implementation of ilog2 (in a separate
77 matches
Mail list logo
