bpo-37798: Add C fastpath for statistics.NormalDist.inv_cdf() (GH-15266)
diff --git a/Modules/Setup b/Modules/Setup
index ed5ee6c..983fa01 100644
--- a/Modules/Setup
+++ b/Modules/Setup
@@ -182,6 +182,7 @@
#_heapq _heapqmodule.c # Heap queue algorithm
#_asyncio _asynciomodule.c # Fast asyncio Future
#_json -I$(srcdir)/Include/internal -DPy_BUILD_CORE_BUILTIN _json.c # _json speedups
+#_statistics _statisticsmodule.c # statistics accelerator
#unicodedata unicodedata.c # static Unicode character database
diff --git a/Modules/_statisticsmodule.c b/Modules/_statisticsmodule.c
new file mode 100644
index 0000000..78ec90a
--- /dev/null
+++ b/Modules/_statisticsmodule.c
@@ -0,0 +1,122 @@
+/* statistics accelerator C extensor: _statistics module. */
+
+#include "Python.h"
+#include "structmember.h"
+#include "clinic/_statisticsmodule.c.h"
+
+/*[clinic input]
+module _statistics
+
+[clinic start generated code]*/
+/*[clinic end generated code: output=da39a3ee5e6b4b0d input=864a6f59b76123b2]*/
+
+
+static PyMethodDef speedups_methods[] = {
+ _STATISTICS__NORMAL_DIST_INV_CDF_METHODDEF
+ {NULL, NULL, 0, NULL}
+};
+
+/*[clinic input]
+_statistics._normal_dist_inv_cdf -> double
+ p: double
+ mu: double
+ sigma: double
+ /
+[clinic start generated code]*/
+
+static double
+_statistics__normal_dist_inv_cdf_impl(PyObject *module, double p, double mu,
+ double sigma)
+/*[clinic end generated code: output=02fd19ddaab36602 input=24715a74be15296a]*/
+{
+ double q, num, den, r, x;
+ q = p - 0.5;
+ // Algorithm AS 241: The Percentage Points of the Normal Distribution
+ if(fabs(q) <= 0.425) {
+ r = 0.180625 - q * q;
+ // Hash sum AB: 55.88319 28806 14901 4439
+ num = (((((((2.5090809287301226727e+3 * r +
+ 3.3430575583588128105e+4) * r +
+ 6.7265770927008700853e+4) * r +
+ 4.5921953931549871457e+4) * r +
+ 1.3731693765509461125e+4) * r +
+ 1.9715909503065514427e+3) * r +
+ 1.3314166789178437745e+2) * r +
+ 3.3871328727963666080e+0) * q;
+ den = (((((((5.2264952788528545610e+3 * r +
+ 2.8729085735721942674e+4) * r +
+ 3.9307895800092710610e+4) * r +
+ 2.1213794301586595867e+4) * r +
+ 5.3941960214247511077e+3) * r +
+ 6.8718700749205790830e+2) * r +
+ 4.2313330701600911252e+1) * r +
+ 1.0);
+ x = num / den;
+ return mu + (x * sigma);
+ }
+ r = q <= 0.0? p : 1.0-p;
+ r = sqrt(-log(r));
+ if (r <= 5.0) {
+ r = r - 1.6;
+ // Hash sum CD: 49.33206 50330 16102 89036
+ num = (((((((7.74545014278341407640e-4 * r +
+ 2.27238449892691845833e-2) * r +
+ 2.41780725177450611770e-1) * r +
+ 1.27045825245236838258e+0) * r +
+ 3.64784832476320460504e+0) * r +
+ 5.76949722146069140550e+0) * r +
+ 4.63033784615654529590e+0) * r +
+ 1.42343711074968357734e+0);
+ den = (((((((1.05075007164441684324e-9 * r +
+ 5.47593808499534494600e-4) * r +
+ 1.51986665636164571966e-2) * r +
+ 1.48103976427480074590e-1) * r +
+ 6.89767334985100004550e-1) * r +
+ 1.67638483018380384940e+0) * r +
+ 2.05319162663775882187e+0) * r +
+ 1.0);
+ } else {
+ r -= 5.0;
+ // Hash sum EF: 47.52583 31754 92896 71629
+ num = (((((((2.01033439929228813265e-7 * r +
+ 2.71155556874348757815e-5) * r +
+ 1.24266094738807843860e-3) * r +
+ 2.65321895265761230930e-2) * r +
+ 2.96560571828504891230e-1) * r +
+ 1.78482653991729133580e+0) * r +
+ 5.46378491116411436990e+0) * r +
+ 6.65790464350110377720e+0);
+ den = (((((((2.04426310338993978564e-15 * r +
+ 1.42151175831644588870e-7) * r +
+ 1.84631831751005468180e-5) * r +
+ 7.86869131145613259100e-4) * r +
+ 1.48753612908506148525e-2) * r +
+ 1.36929880922735805310e-1) * r +
+ 5.99832206555887937690e-1) * r +
+ 1.0);
+ }
+ x = num / den;
+ if (q < 0.0) x = -x;
+ return mu + (x * sigma);
+}
+
+static struct PyModuleDef statisticsmodule = {
+ PyModuleDef_HEAD_INIT,
+ "_statistics",
+ _statistics__normal_dist_inv_cdf__doc__,
+ -1,
+ speedups_methods,
+ NULL,
+ NULL,
+ NULL,
+ NULL
+};
+
+
+PyMODINIT_FUNC
+PyInit__statistics(void)
+{
+ PyObject *m = PyModule_Create(&statisticsmodule);
+ if (!m) return NULL;
+ return m;
+}
diff --git a/Modules/clinic/_statisticsmodule.c.h b/Modules/clinic/_statisticsmodule.c.h
new file mode 100644
index 0000000..f5a2e46
--- /dev/null
+++ b/Modules/clinic/_statisticsmodule.c.h
@@ -0,0 +1,50 @@
+/*[clinic input]
+preserve
+[clinic start generated code]*/
+
+PyDoc_STRVAR(_statistics__normal_dist_inv_cdf__doc__,
+"_normal_dist_inv_cdf($module, p, mu, sigma, /)\n"
+"--\n"
+"\n");
+
+#define _STATISTICS__NORMAL_DIST_INV_CDF_METHODDEF \
+ {"_normal_dist_inv_cdf", (PyCFunction)(void(*)(void))_statistics__normal_dist_inv_cdf, METH_FASTCALL, _statistics__normal_dist_inv_cdf__doc__},
+
+static double
+_statistics__normal_dist_inv_cdf_impl(PyObject *module, double p, double mu,
+ double sigma);
+
+static PyObject *
+_statistics__normal_dist_inv_cdf(PyObject *module, PyObject *const *args, Py_ssize_t nargs)
+{
+ PyObject *return_value = NULL;
+ double p;
+ double mu;
+ double sigma;
+ double _return_value;
+
+ if (!_PyArg_CheckPositional("_normal_dist_inv_cdf", nargs, 3, 3)) {
+ goto exit;
+ }
+ p = PyFloat_AsDouble(args[0]);
+ if (PyErr_Occurred()) {
+ goto exit;
+ }
+ mu = PyFloat_AsDouble(args[1]);
+ if (PyErr_Occurred()) {
+ goto exit;
+ }
+ sigma = PyFloat_AsDouble(args[2]);
+ if (PyErr_Occurred()) {
+ goto exit;
+ }
+ _return_value = _statistics__normal_dist_inv_cdf_impl(module, p, mu, sigma);
+ if ((_return_value == -1.0) && PyErr_Occurred()) {
+ goto exit;
+ }
+ return_value = PyFloat_FromDouble(_return_value);
+
+exit:
+ return return_value;
+}
+/*[clinic end generated code: output=ba6af124acd34732 input=a9049054013a1b77]*/