[issue8692] Use divide-and-conquer for faster factorials
Daniel Stutzbach
report at bugs.python.org
Wed May 12 18:01:04 CEST 2010
Daniel Stutzbach <daniel at stutzbachenterprises.com> added the comment:
On Wed, May 12, 2010 at 10:31 AM, Alexander Belopolsky
<report at 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 right
instead of the left, we can do:
k = (n + m) / 2;
k |= 1; /* Ensure that k is odd */
left = factorial_part_product(n, k-2);
if (left == NULL) goto done;
right = factorial_part_product(k, m);
if (right == NULL) goto done;
That will split 1*3*5*7*9*11 into (1*3*5) * (7*9*11), just like the
old code. It will split 1*3*5*7*9 into (1*3) * (5*7*9) while the old
code did (1*3*5) * (7*9), which is fine.
It's easier to read and fewer operations. :-)
----------
_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue8692>
_______________________________________
More information about the Python-bugs-list
mailing list