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

[Alexander Belopolsky]

Alexander Belopolsky <belopolsky at 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 running product by i> }?

Not a direct answer to your question, but replacing a bisect with a no-frills algorithm in my precompute patch gives the following timings:

   n    bisect   no-frills
   100  38.9 us  38.5 us
  1000  .904 ms  1.08 ms
 10000  35.4 ms  50.3 ms


The no-frills product still takes 20 lines of C code though:

    n = last - first + 1;
    if (n <= 0)
        return PyLong_FromLong(1L);

    result = PyLong_FromUnsignedLong(ODD(first));
    if (result == NULL)
        return NULL;
    for  (i = 1; i < n; ++i) {
        x = PyLong_FromUnsignedLong(ODD(first + i));
        if (x == NULL)
            goto error;
        tmp = PyNumber_Multiply(result, x);
        Py_DECREF(x);
        if (tmp == NULL)
            goto error;
        Py_DECREF(result);
        result = tmp;
    }
    return result;
 error:
    Py_DECREF(result);
    return NULL;

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue8692>
_______________________________________