/* Math module -- standard C math library functions, pi and e */ /* Here are some comments from Tim Peters, extracted from the discussion attached to http://bugs.python.org/issue1640. They describe the general aims of the math module with respect to special values, IEEE-754 floating-point exceptions, and Python exceptions. These are the "spirit of 754" rules: 1. If the mathematical result is a real number, but of magnitude too large to approximate by a machine float, overflow is signaled and the result is an infinity (with the appropriate sign). 2. If the mathematical result is a real number, but of magnitude too small to approximate by a machine float, underflow is signaled and the result is a zero (with the appropriate sign). 3. At a singularity (a value x such that the limit of f(y) as y approaches x exists and is an infinity), "divide by zero" is signaled and the result is an infinity (with the appropriate sign). This is complicated a little by that the left-side and right-side limits may not be the same; e.g., 1/x approaches +inf or -inf as x approaches 0 from the positive or negative directions. In that specific case, the sign of the zero determines the result of 1/0. 4. At a point where a function has no defined result in the extended reals (i.e., the reals plus an infinity or two), invalid operation is signaled and a NaN is returned. And these are what Python has historically /tried/ to do (but not always successfully, as platform libm behavior varies a lot): For #1, raise OverflowError. For #2, return a zero (with the appropriate sign if that happens by accident ;-)). For #3 and #4, raise ValueError. It may have made sense to raise Python's ZeroDivisionError in #3, but historically that's only been raised for division by zero and mod by zero. */ /* In general, on an IEEE-754 platform the aim is to follow the C99 standard, including Annex 'F', whenever possible. Where the standard recommends raising the 'divide-by-zero' or 'invalid' floating-point exceptions, Python should raise a ValueError. Where the standard recommends raising 'overflow', Python should raise an OverflowError. In all other circumstances a value should be returned. */ #ifndef Py_BUILD_CORE_BUILTIN #define Py_BUILD_CORE_MODULE … #endif #include "Python.h" #include "pycore_abstract.h" // _PyNumber_Index() #include "pycore_bitutils.h" // _Py_bit_length() #include "pycore_call.h" // _PyObject_CallNoArgs() #include "pycore_long.h" // _PyLong_GetZero() #include "pycore_moduleobject.h" // _PyModule_GetState() #include "pycore_object.h" // _PyObject_LookupSpecial() #include "pycore_pymath.h" // _PY_SHORT_FLOAT_REPR /* For DBL_EPSILON in _math.h */ #include <float.h> /* For _Py_log1p with workarounds for buggy handling of zeros. */ #include "_math.h" #include <stdbool.h> #include "clinic/mathmodule.c.h" /*[clinic input] module math [clinic start generated code]*/ /*[clinic end generated code: output=da39a3ee5e6b4b0d input=76bc7002685dd942]*/ math_module_state; static inline math_module_state* get_math_module_state(PyObject *module) { … } /* Double and triple length extended precision algorithms from: Accurate Sum and Dot Product by Takeshi Ogita, Siegfried M. Rump, and Shin’Ichi Oishi https://doi.org/10.1137/030601818 https://www.tuhh.de/ti3/paper/rump/OgRuOi05.pdf */ DoubleLength; static DoubleLength dl_fast_sum(double a, double b) { … } static DoubleLength dl_sum(double a, double b) { … } #ifndef UNRELIABLE_FMA static DoubleLength dl_mul(double x, double y) { … } #else /* The default implementation of dl_mul() depends on the C math library having an accurate fma() function as required by § 7.12.13.1 of the C99 standard. The UNRELIABLE_FMA option is provided as a slower but accurate alternative for builds where the fma() function is found wanting. The speed penalty may be modest (17% slower on an Apple M1 Max), so don't hesitate to enable this build option. The algorithms are from the T. J. Dekker paper: A Floating-Point Technique for Extending the Available Precision https://csclub.uwaterloo.ca/~pbarfuss/dekker1971.pdf */ static DoubleLength dl_split(double x) { // Dekker (5.5) and (5.6). double t = x * 134217729.0; // Veltkamp constant = 2.0 ** 27 + 1 double hi = t - (t - x); double lo = x - hi; return (DoubleLength) {hi, lo}; } static DoubleLength dl_mul(double x, double y) { // Dekker (5.12) and mul12() DoubleLength xx = dl_split(x); DoubleLength yy = dl_split(y); double p = xx.hi * yy.hi; double q = xx.hi * yy.lo + xx.lo * yy.hi; double z = p + q; double zz = p - z + q + xx.lo * yy.lo; return (DoubleLength) {z, zz}; } #endif TripleLength; static const TripleLength tl_zero = …; static TripleLength tl_fma(double x, double y, TripleLength total) { … } static double tl_to_d(TripleLength total) { … } /* sin(pi*x), giving accurate results for all finite x (especially x integral or close to an integer). This is here for use in the reflection formula for the gamma function. It conforms to IEEE 754-2008 for finite arguments, but not for infinities or nans. */ static const double pi = …; static const double logpi = …; /* Version of PyFloat_AsDouble() with in-line fast paths for exact floats and integers. Gives a substantial speed improvement for extracting float arguments. */ #define ASSIGN_DOUBLE(target_var, obj, error_label) … static double m_sinpi(double x) { … } /* Implementation of the real gamma function. Kept here to work around issues (see e.g. gh-70309) with quality of libm's tgamma/lgamma implementations on various platforms (Windows, MacOS). In extensive but non-exhaustive random tests, this function proved accurate to within <= 10 ulps across the entire float domain. Note that accuracy may depend on the quality of the system math functions, the pow function in particular. Special cases follow C99 annex F. The parameters and method are tailored to platforms whose double format is the IEEE 754 binary64 format. Method: for x > 0.0 we use the Lanczos approximation with parameters N=13 and g=6.024680040776729583740234375; these parameters are amongst those used by the Boost library. Following Boost (again), we re-express the Lanczos sum as a rational function, and compute it that way. The coefficients below were computed independently using MPFR, and have been double-checked against the coefficients in the Boost source code. For x < 0.0 we use the reflection formula. There's one minor tweak that deserves explanation: Lanczos' formula for Gamma(x) involves computing pow(x+g-0.5, x-0.5) / exp(x+g-0.5). For many x values, x+g-0.5 can be represented exactly. However, in cases where it can't be represented exactly the small error in x+g-0.5 can be magnified significantly by the pow and exp calls, especially for large x. A cheap correction is to multiply by (1 + e*g/(x+g-0.5)), where e is the error involved in the computation of x+g-0.5 (that is, e = computed value of x+g-0.5 - exact value of x+g-0.5). Here's the proof: Correction factor ----------------- Write x+g-0.5 = y-e, where y is exactly representable as an IEEE 754 double, and e is tiny. Then: pow(x+g-0.5,x-0.5)/exp(x+g-0.5) = pow(y-e, x-0.5)/exp(y-e) = pow(y, x-0.5)/exp(y) * C, where the correction_factor C is given by C = pow(1-e/y, x-0.5) * exp(e) Since e is tiny, pow(1-e/y, x-0.5) ~ 1-(x-0.5)*e/y, and exp(x) ~ 1+e, so: C ~ (1-(x-0.5)*e/y) * (1+e) ~ 1 + e*(y-(x-0.5))/y But y-(x-0.5) = g+e, and g+e ~ g. So we get C ~ 1 + e*g/y, and pow(x+g-0.5,x-0.5)/exp(x+g-0.5) ~ pow(y, x-0.5)/exp(y) * (1 + e*g/y), Note that for accuracy, when computing r*C it's better to do r + e*g/y*r; than r * (1 + e*g/y); since the addition in the latter throws away most of the bits of information in e*g/y. */ #define LANCZOS_N … static const double lanczos_g = …; static const double lanczos_g_minus_half = …; static const double lanczos_num_coeffs[LANCZOS_N] = …; /* denominator is x*(x+1)*...*(x+LANCZOS_N-2) */ static const double lanczos_den_coeffs[LANCZOS_N] = …; /* gamma values for small positive integers, 1 though NGAMMA_INTEGRAL */ #define NGAMMA_INTEGRAL … static const double gamma_integral[NGAMMA_INTEGRAL] = …; /* Lanczos' sum L_g(x), for positive x */ static double lanczos_sum(double x) { … } static double m_tgamma(double x) { … } /* lgamma: natural log of the absolute value of the Gamma function. For large arguments, Lanczos' formula works extremely well here. */ static double m_lgamma(double x) { … } /* IEEE 754-style remainder operation: x - n*y where n*y is the nearest multiple of y to x, taking n even in the case of a tie. Assuming an IEEE 754 binary floating-point format, the result is always exact. */ static double m_remainder(double x, double y) { … } /* Various platforms (Solaris, OpenBSD) do nonstandard things for log(0), log(-ve), log(NaN). Here are wrappers for log and log10 that deal with special values directly, passing positive non-special values through to the system log/log10. */ static double m_log(double x) { … } /* log2: log to base 2. Uses an algorithm that should: (a) produce exact results for powers of 2, and (b) give a monotonic log2 (for positive finite floats), assuming that the system log is monotonic. */ static double m_log2(double x) { … } static double m_log10(double x) { … } /*[clinic input] math.gcd *integers as args: array Greatest Common Divisor. [clinic start generated code]*/ static PyObject * math_gcd_impl(PyObject *module, PyObject * const *args, Py_ssize_t args_length) /*[clinic end generated code: output=a26c95907374ffb4 input=ded7f0ea3850c05c]*/ { … } static PyObject * long_lcm(PyObject *a, PyObject *b) { … } /*[clinic input] math.lcm *integers as args: array Least Common Multiple. [clinic start generated code]*/ static PyObject * math_lcm_impl(PyObject *module, PyObject * const *args, Py_ssize_t args_length) /*[clinic end generated code: output=c8a59a5c2e55c816 input=3e4f4b7cdf948a98]*/ { … } /* Call is_error when errno != 0, and where x is the result libm * returned. is_error will usually set up an exception and return * true (1), but may return false (0) without setting up an exception. */ static int is_error(double x) { … } /* math_1 is used to wrap a libm function f that takes a double argument and returns a double. The error reporting follows these rules, which are designed to do the right thing on C89/C99 platforms and IEEE 754/non IEEE 754 platforms. - a NaN result from non-NaN inputs causes ValueError to be raised - an infinite result from finite inputs causes OverflowError to be raised if can_overflow is 1, or raises ValueError if can_overflow is 0. - if the result is finite and errno == EDOM then ValueError is raised - if the result is finite and nonzero and errno == ERANGE then OverflowError is raised The last rule is used to catch overflow on platforms which follow C89 but for which HUGE_VAL is not an infinity. For the majority of one-argument functions these rules are enough to ensure that Python's functions behave as specified in 'Annex F' of the C99 standard, with the 'invalid' and 'divide-by-zero' floating-point exceptions mapping to Python's ValueError and the 'overflow' floating-point exception mapping to OverflowError. math_1 only works for functions that don't have singularities *and* the possibility of overflow; fortunately, that covers everything we care about right now. */ static PyObject * math_1(PyObject *arg, double (*func) (double), int can_overflow) { … } /* variant of math_1, to be used when the function being wrapped is known to set errno properly (that is, errno = EDOM for invalid or divide-by-zero, errno = ERANGE for overflow). */ static PyObject * math_1a(PyObject *arg, double (*func) (double)) { … } /* math_2 is used to wrap a libm function f that takes two double arguments and returns a double. The error reporting follows these rules, which are designed to do the right thing on C89/C99 platforms and IEEE 754/non IEEE 754 platforms. - a NaN result from non-NaN inputs causes ValueError to be raised - an infinite result from finite inputs causes OverflowError to be raised. - if the result is finite and errno == EDOM then ValueError is raised - if the result is finite and nonzero and errno == ERANGE then OverflowError is raised The last rule is used to catch overflow on platforms which follow C89 but for which HUGE_VAL is not an infinity. For most two-argument functions (copysign, fmod, hypot, atan2) these rules are enough to ensure that Python's functions behave as specified in 'Annex F' of the C99 standard, with the 'invalid' and 'divide-by-zero' floating-point exceptions mapping to Python's ValueError and the 'overflow' floating-point exception mapping to OverflowError. */ static PyObject * math_2(PyObject *const *args, Py_ssize_t nargs, double (*func) (double, double), const char *funcname) { … } #define FUNC1(funcname, func, can_overflow, docstring) … #define FUNC1A(funcname, func, docstring) … #define FUNC2(funcname, func, docstring) … FUNC1(…) FUNC1(…) FUNC1(…) FUNC1(…) FUNC1(…) FUNC2(…) FUNC1(…) FUNC1(…) /*[clinic input] math.ceil x as number: object / Return the ceiling of x as an Integral. This is the smallest integer >= x. [clinic start generated code]*/ static PyObject * math_ceil(PyObject *module, PyObject *number) /*[clinic end generated code: output=6c3b8a78bc201c67 input=2725352806399cab]*/ { … } FUNC2(…) FUNC1(…) FUNC1(…) FUNC1A(…) FUNC1A(…) FUNC1(…) FUNC1(…) FUNC1(…) FUNC1(…) /*[clinic input] math.floor x as number: object / Return the floor of x as an Integral. This is the largest integer <= x. [clinic start generated code]*/ static PyObject * math_floor(PyObject *module, PyObject *number) /*[clinic end generated code: output=c6a65c4884884b8a input=63af6b5d7ebcc3d6]*/ { … } FUNC1A(…) FUNC1A(…) FUNC1(…) FUNC2(…) FUNC1(…) FUNC1(…) FUNC1(…) FUNC1(…) FUNC1(…) /* Precision summation function as msum() by Raymond Hettinger in <https://code.activestate.com/recipes/393090-binary-floating-point-summation-accurate-to-full-p/>, enhanced with the exact partials sum and roundoff from Mark Dickinson's post at <http://bugs.python.org/file10357/msum4.py>. See those links for more details, proofs and other references. Note 1: IEEE 754 floating-point semantics with a rounding mode of roundTiesToEven are assumed. Note 2: No provision is made for intermediate overflow handling; therefore, fsum([1e+308, -1e+308, 1e+308]) returns 1e+308 while fsum([1e+308, 1e+308, -1e+308]) raises an OverflowError due to the overflow of the first partial sum. Note 3: The algorithm has two potential sources of fragility. First, C permits arithmetic operations on `double`s to be performed in an intermediate format whose range and precision may be greater than those of `double` (see for example C99 §5.2.4.2.2, paragraph 8). This can happen for example on machines using the now largely historical x87 FPUs. In this case, `fsum` can produce incorrect results. If `FLT_EVAL_METHOD` is `0` or `1`, or `FLT_EVAL_METHOD` is `2` and `long double` is identical to `double`, then we should be safe from this source of errors. Second, an aggressively optimizing compiler can re-associate operations so that (for example) the statement `yr = hi - x;` is treated as `yr = (x + y) - x` and then re-associated as `yr = y + (x - x)`, giving `y = yr` and `lo = 0.0`. That re-association would be in violation of the C standard, and should not occur except possibly in the presence of unsafe optimizations (e.g., -ffast-math, -fassociative-math). Such optimizations should be avoided for this module. Note 4: The signature of math.fsum() differs from builtins.sum() because the start argument doesn't make sense in the context of accurate summation. Since the partials table is collapsed before returning a result, sum(seq2, start=sum(seq1)) may not equal the accurate result returned by sum(itertools.chain(seq1, seq2)). */ #define NUM_PARTIALS … /* Extend the partials array p[] by doubling its size. */ static int /* non-zero on error */ _fsum_realloc(double **p_ptr, Py_ssize_t n, double *ps, Py_ssize_t *m_ptr) { … } /* Full precision summation of a sequence of floats. def msum(iterable): partials = [] # sorted, non-overlapping partial sums for x in iterable: i = 0 for y in partials: if abs(x) < abs(y): x, y = y, x hi = x + y lo = y - (hi - x) if lo: partials[i] = lo i += 1 x = hi partials[i:] = [x] return sum_exact(partials) Rounded x+y stored in hi with the roundoff stored in lo. Together hi+lo are exactly equal to x+y. The inner loop applies hi/lo summation to each partial so that the list of partial sums remains exact. Sum_exact() adds the partial sums exactly and correctly rounds the final result (using the round-half-to-even rule). The items in partials remain non-zero, non-special, non-overlapping and strictly increasing in magnitude, but possibly not all having the same sign. Depends on IEEE 754 arithmetic guarantees and half-even rounding. */ /*[clinic input] math.fsum seq: object / Return an accurate floating-point sum of values in the iterable seq. Assumes IEEE-754 floating-point arithmetic. [clinic start generated code]*/ static PyObject * math_fsum(PyObject *module, PyObject *seq) /*[clinic end generated code: output=ba5c672b87fe34fc input=4506244ded6057dc]*/ { … } #undef NUM_PARTIALS static unsigned long count_set_bits(unsigned long n) { … } /* Integer square root Given a nonnegative integer `n`, we want to compute the largest integer `a` for which `a * a <= n`, or equivalently the integer part of the exact square root of `n`. We use an adaptive-precision pure-integer version of Newton's iteration. Given a positive integer `n`, the algorithm produces at each iteration an integer approximation `a` to the square root of `n >> s` for some even integer `s`, with `s` decreasing as the iterations progress. On the final iteration, `s` is zero and we have an approximation to the square root of `n` itself. At every step, the approximation `a` is strictly within 1.0 of the true square root, so we have (a - 1)**2 < (n >> s) < (a + 1)**2 After the final iteration, a check-and-correct step is needed to determine whether `a` or `a - 1` gives the desired integer square root of `n`. The algorithm is remarkable in its simplicity. There's no need for a per-iteration check-and-correct step, and termination is straightforward: the number of iterations is known in advance (it's exactly `floor(log2(log2(n)))` for `n > 1`). The only tricky part of the correctness proof is in establishing that the bound `(a - 1)**2 < (n >> s) < (a + 1)**2` is maintained from one iteration to the next. A sketch of the proof of this is given below. In addition to the proof sketch, a formal, computer-verified proof of correctness (using Lean) of an equivalent recursive algorithm can be found here: https://github.com/mdickinson/snippets/blob/master/proofs/isqrt/src/isqrt.lean Here's Python code equivalent to the C implementation below: def isqrt(n): """ Return the integer part of the square root of the input. """ n = operator.index(n) if n < 0: raise ValueError("isqrt() argument must be nonnegative") if n == 0: return 0 c = (n.bit_length() - 1) // 2 a = 1 d = 0 for s in reversed(range(c.bit_length())): # Loop invariant: (a-1)**2 < (n >> 2*(c - d)) < (a+1)**2 e = d d = c >> s a = (a << d - e - 1) + (n >> 2*c - e - d + 1) // a return a - (a*a > n) Sketch of proof of correctness ------------------------------ The delicate part of the correctness proof is showing that the loop invariant is preserved from one iteration to the next. That is, just before the line a = (a << d - e - 1) + (n >> 2*c - e - d + 1) // a is executed in the above code, we know that (1) (a - 1)**2 < (n >> 2*(c - e)) < (a + 1)**2. (since `e` is always the value of `d` from the previous iteration). We must prove that after that line is executed, we have (a - 1)**2 < (n >> 2*(c - d)) < (a + 1)**2 To facilitate the proof, we make some changes of notation. Write `m` for `n >> 2*(c-d)`, and write `b` for the new value of `a`, so b = (a << d - e - 1) + (n >> 2*c - e - d + 1) // a or equivalently: (2) b = (a << d - e - 1) + (m >> d - e + 1) // a Then we can rewrite (1) as: (3) (a - 1)**2 < (m >> 2*(d - e)) < (a + 1)**2 and we must show that (b - 1)**2 < m < (b + 1)**2. From this point on, we switch to mathematical notation, so `/` means exact division rather than integer division and `^` is used for exponentiation. We use the `√` symbol for the exact square root. In (3), we can remove the implicit floor operation to give: (4) (a - 1)^2 < m / 4^(d - e) < (a + 1)^2 Taking square roots throughout (4), scaling by `2^(d-e)`, and rearranging gives (5) 0 <= | 2^(d-e)a - √m | < 2^(d-e) Squaring and dividing through by `2^(d-e+1) a` gives (6) 0 <= 2^(d-e-1) a + m / (2^(d-e+1) a) - √m < 2^(d-e-1) / a We'll show below that `2^(d-e-1) <= a`. Given that, we can replace the right-hand side of (6) with `1`, and now replacing the central term `m / (2^(d-e+1) a)` with its floor in (6) gives (7) -1 < 2^(d-e-1) a + m // 2^(d-e+1) a - √m < 1 Or equivalently, from (2): (7) -1 < b - √m < 1 and rearranging gives that `(b-1)^2 < m < (b+1)^2`, which is what we needed to prove. We're not quite done: we still have to prove the inequality `2^(d - e - 1) <= a` that was used to get line (7) above. From the definition of `c`, we have `4^c <= n`, which implies (8) 4^d <= m also, since `e == d >> 1`, `d` is at most `2e + 1`, from which it follows that `2d - 2e - 1 <= d` and hence that (9) 4^(2d - 2e - 1) <= m Dividing both sides by `4^(d - e)` gives (10) 4^(d - e - 1) <= m / 4^(d - e) But we know from (4) that `m / 4^(d-e) < (a + 1)^2`, hence (11) 4^(d - e - 1) < (a + 1)^2 Now taking square roots of both sides and observing that both `2^(d-e-1)` and `a` are integers gives `2^(d - e - 1) <= a`, which is what we needed. This completes the proof sketch. */ /* The _approximate_isqrt_tab table provides approximate square roots for 16-bit integers. For any n in the range 2**14 <= n < 2**16, the value a = _approximate_isqrt_tab[(n >> 8) - 64] is an approximate square root of n, satisfying (a - 1)**2 < n < (a + 1)**2. The table was computed in Python using the expression: [min(round(sqrt(256*n + 128)), 255) for n in range(64, 256)] */ static const uint8_t _approximate_isqrt_tab[192] = …; /* Approximate square root of a large 64-bit integer. Given `n` satisfying `2**62 <= n < 2**64`, return `a` satisfying `(a - 1)**2 < n < (a + 1)**2`. */ static inline uint32_t _approximate_isqrt(uint64_t n) { … } /*[clinic input] math.isqrt n: object / Return the integer part of the square root of the input. [clinic start generated code]*/ static PyObject * math_isqrt(PyObject *module, PyObject *n) /*[clinic end generated code: output=35a6f7f980beab26 input=5b6e7ae4fa6c43d6]*/ { … } /* Divide-and-conquer factorial algorithm * * Based on the formula and pseudo-code provided at: * http://www.luschny.de/math/factorial/binarysplitfact.html * * Faster algorithms exist, but they're more complicated and depend on * a fast prime factorization algorithm. * * Notes on the algorithm * ---------------------- * * factorial(n) is written in the form 2**k * m, with m odd. k and m are * computed separately, and then combined using a left shift. * * The function factorial_odd_part computes the odd part m (i.e., the greatest * odd divisor) of factorial(n), using the formula: * * factorial_odd_part(n) = * * product_{i >= 0} product_{0 < j <= n / 2**i, j odd} j * * Example: factorial_odd_part(20) = * * (1) * * (1) * * (1 * 3 * 5) * * (1 * 3 * 5 * 7 * 9) * * (1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19) * * Here i goes from large to small: the first term corresponds to i=4 (any * larger i gives an empty product), and the last term corresponds to i=0. * Each term can be computed from the last by multiplying by the extra odd * numbers required: e.g., to get from the penultimate term to the last one, * we multiply by (11 * 13 * 15 * 17 * 19). * * To see a hint of why this formula works, here are the same numbers as above * but with the even parts (i.e., the appropriate powers of 2) included. For * each subterm in the product for i, we multiply that subterm by 2**i: * * factorial(20) = * * (16) * * (8) * * (4 * 12 * 20) * * (2 * 6 * 10 * 14 * 18) * * (1 * 3 * 5 * 7 * 9 * 11 * 13 * 15 * 17 * 19) * * The factorial_partial_product function computes the product of all odd j in * range(start, stop) for given start and stop. It's used to compute the * partial products like (11 * 13 * 15 * 17 * 19) in the example above. It * operates recursively, repeatedly splitting the range into two roughly equal * pieces until the subranges are small enough to be computed using only C * integer arithmetic. * * The two-valuation k (i.e., the exponent of the largest power of 2 dividing * the factorial) is computed independently in the main math_factorial * function. By standard results, its value is: * * two_valuation = n//2 + n//4 + n//8 + .... * * It can be shown (e.g., by complete induction on n) that two_valuation is * equal to n - count_set_bits(n), where count_set_bits(n) gives the number of * '1'-bits in the binary expansion of n. */ /* factorial_partial_product: Compute product(range(start, stop, 2)) using * divide and conquer. Assumes start and stop are odd and stop > start. * max_bits must be >= bit_length(stop - 2). */ static PyObject * factorial_partial_product(unsigned long start, unsigned long stop, unsigned long max_bits) { … } /* factorial_odd_part: compute the odd part of factorial(n). */ static PyObject * factorial_odd_part(unsigned long n) { … } /* Lookup table for small factorial values */ static const unsigned long SmallFactorials[] = …; /*[clinic input] math.factorial n as arg: object / Find n!. Raise a ValueError if x is negative or non-integral. [clinic start generated code]*/ static PyObject * math_factorial(PyObject *module, PyObject *arg) /*[clinic end generated code: output=6686f26fae00e9ca input=713fb771677e8c31]*/ { … } /*[clinic input] math.trunc x: object / Truncates the Real x to the nearest Integral toward 0. Uses the __trunc__ magic method. [clinic start generated code]*/ static PyObject * math_trunc(PyObject *module, PyObject *x) /*[clinic end generated code: output=34b9697b707e1031 input=2168b34e0a09134d]*/ { … } /*[clinic input] math.frexp x: double / Return the mantissa and exponent of x, as pair (m, e). m is a float and e is an int, such that x = m * 2.**e. If x is 0, m and e are both 0. Else 0.5 <= abs(m) < 1.0. [clinic start generated code]*/ static PyObject * math_frexp_impl(PyObject *module, double x) /*[clinic end generated code: output=03e30d252a15ad4a input=96251c9e208bc6e9]*/ { … } /*[clinic input] math.ldexp x: double i: object / Return x * (2**i). This is essentially the inverse of frexp(). [clinic start generated code]*/ static PyObject * math_ldexp_impl(PyObject *module, double x, PyObject *i) /*[clinic end generated code: output=b6892f3c2df9cc6a input=17d5970c1a40a8c1]*/ { … } /*[clinic input] math.modf x: double / Return the fractional and integer parts of x. Both results carry the sign of x and are floats. [clinic start generated code]*/ static PyObject * math_modf_impl(PyObject *module, double x) /*[clinic end generated code: output=90cee0260014c3c0 input=b4cfb6786afd9035]*/ { … } /* A decent logarithm is easy to compute even for huge ints, but libm can't do that by itself -- loghelper can. func is log or log10, and name is "log" or "log10". Note that overflow of the result isn't possible: an int can contain no more than INT_MAX * SHIFT bits, so has value certainly less than 2**(2**64 * 2**16) == 2**2**80, and log2 of that is 2**80, which is small enough to fit in an IEEE single. log and log10 are even smaller. However, intermediate overflow is possible for an int if the number of bits in that int is larger than PY_SSIZE_T_MAX. */ static PyObject* loghelper(PyObject* arg, double (*func)(double)) { … } /* AC: cannot convert yet, see gh-102839 and gh-89381, waiting for support of multiple signatures */ static PyObject * math_log(PyObject *module, PyObject * const *args, Py_ssize_t nargs) { … } PyDoc_STRVAR(math_log_doc, "log(x, [base=math.e])\n\ Return the logarithm of x to the given base.\n\n\ If the base is not specified, returns the natural logarithm (base e) of x."); /*[clinic input] math.log2 x: object / Return the base 2 logarithm of x. [clinic start generated code]*/ static PyObject * math_log2(PyObject *module, PyObject *x) /*[clinic end generated code: output=5425899a4d5d6acb input=08321262bae4f39b]*/ { … } /*[clinic input] math.log10 x: object / Return the base 10 logarithm of x. [clinic start generated code]*/ static PyObject * math_log10(PyObject *module, PyObject *x) /*[clinic end generated code: output=be72a64617df9c6f input=b2469d02c6469e53]*/ { … } /*[clinic input] math.fma x: double y: double z: double / Fused multiply-add operation. Compute (x * y) + z with a single round. [clinic start generated code]*/ static PyObject * math_fma_impl(PyObject *module, double x, double y, double z) /*[clinic end generated code: output=4fc8626dbc278d17 input=e3ad1f4a4c89626e]*/ { … } /*[clinic input] math.fmod x: double y: double / Return fmod(x, y), according to platform C. x % y may differ. [clinic start generated code]*/ static PyObject * math_fmod_impl(PyObject *module, double x, double y) /*[clinic end generated code: output=7559d794343a27b5 input=4f84caa8cfc26a03]*/ { … } /* Given a *vec* of values, compute the vector norm: sqrt(sum(x ** 2 for x in vec)) The *max* variable should be equal to the largest fabs(x). The *n* variable is the length of *vec*. If n==0, then *max* should be 0.0. If an infinity is present in the vec, *max* should be INF. The *found_nan* variable indicates whether some member of the *vec* is a NaN. To avoid overflow/underflow and to achieve high accuracy giving results that are almost always correctly rounded, four techniques are used: * lossless scaling using a power-of-two scaling factor * accurate squaring using Veltkamp-Dekker splitting [1] or an equivalent with an fma() call * compensated summation using a variant of the Neumaier algorithm [2] * differential correction of the square root [3] The usual presentation of the Neumaier summation algorithm has an expensive branch depending on which operand has the larger magnitude. We avoid this cost by arranging the calculation so that fabs(csum) is always as large as fabs(x). To establish the invariant, *csum* is initialized to 1.0 which is always larger than x**2 after scaling or after division by *max*. After the loop is finished, the initial 1.0 is subtracted out for a net zero effect on the final sum. Since *csum* will be greater than 1.0, the subtraction of 1.0 will not cause fractional digits to be dropped from *csum*. To get the full benefit from compensated summation, the largest addend should be in the range: 0.5 <= |x| <= 1.0. Accordingly, scaling or division by *max* should not be skipped even if not otherwise needed to prevent overflow or loss of precision. The assertion that hi*hi <= 1.0 is a bit subtle. Each vector element gets scaled to a magnitude below 1.0. The Veltkamp-Dekker splitting algorithm gives a *hi* value that is correctly rounded to half precision. When a value at or below 1.0 is correctly rounded, it never goes above 1.0. And when values at or below 1.0 are squared, they remain at or below 1.0, thus preserving the summation invariant. Another interesting assertion is that csum+lo*lo == csum. In the loop, each scaled vector element has a magnitude less than 1.0. After the Veltkamp split, *lo* has a maximum value of 2**-27. So the maximum value of *lo* squared is 2**-54. The value of ulp(1.0)/2.0 is 2**-53. Given that csum >= 1.0, we have: lo**2 <= 2**-54 < 2**-53 == 1/2*ulp(1.0) <= ulp(csum)/2 Since lo**2 is less than 1/2 ulp(csum), we have csum+lo*lo == csum. To minimize loss of information during the accumulation of fractional values, each term has a separate accumulator. This also breaks up sequential dependencies in the inner loop so the CPU can maximize floating-point throughput. [4] On an Apple M1 Max, hypot(*vec) takes only 3.33 µsec when len(vec) == 1000. The square root differential correction is needed because a correctly rounded square root of a correctly rounded sum of squares can still be off by as much as one ulp. The differential correction starts with a value *x* that is the difference between the square of *h*, the possibly inaccurately rounded square root, and the accurately computed sum of squares. The correction is the first order term of the Maclaurin series expansion of sqrt(h**2 + x) == h + x/(2*h) + O(x**2). [5] Essentially, this differential correction is equivalent to one refinement step in Newton's divide-and-average square root algorithm, effectively doubling the number of accurate bits. This technique is used in Dekker's SQRT2 algorithm and again in Borges' ALGORITHM 4 and 5. The hypot() function is faithfully rounded (less than 1 ulp error) and usually correctly rounded (within 1/2 ulp). The squaring step is exact. The Neumaier summation computes as if in doubled precision (106 bits) and has the advantage that its input squares are non-negative so that the condition number of the sum is one. The square root with a differential correction is likewise computed as if in doubled precision. For n <= 1000, prior to the final addition that rounds the overall result, the internal accuracy of "h" together with its correction of "x / (2.0 * h)" is at least 100 bits. [6] Also, hypot() was tested against a Decimal implementation with prec=300. After 100 million trials, no incorrectly rounded examples were found. In addition, perfect commutativity (all permutations are exactly equal) was verified for 1 billion random inputs with n=5. [7] References: 1. Veltkamp-Dekker splitting: http://csclub.uwaterloo.ca/~pbarfuss/dekker1971.pdf 2. Compensated summation: http://www.ti3.tu-harburg.de/paper/rump/Ru08b.pdf 3. Square root differential correction: https://arxiv.org/pdf/1904.09481.pdf 4. Data dependency graph: https://bugs.python.org/file49439/hypot.png 5. https://www.wolframalpha.com/input/?i=Maclaurin+series+sqrt%28h**2+%2B+x%29+at+x%3D0 6. Analysis of internal accuracy: https://bugs.python.org/file49484/best_frac.py 7. Commutativity test: https://bugs.python.org/file49448/test_hypot_commutativity.py */ static inline double vector_norm(Py_ssize_t n, double *vec, double max, int found_nan) { … } #define NUM_STACK_ELEMS … /*[clinic input] math.dist p: object q: object / Return the Euclidean distance between two points p and q. The points should be specified as sequences (or iterables) of coordinates. Both inputs must have the same dimension. Roughly equivalent to: sqrt(sum((px - qx) ** 2.0 for px, qx in zip(p, q))) [clinic start generated code]*/ static PyObject * math_dist_impl(PyObject *module, PyObject *p, PyObject *q) /*[clinic end generated code: output=56bd9538d06bbcfe input=74e85e1b6092e68e]*/ { … } /*[clinic input] math.hypot *coordinates as args: array Multidimensional Euclidean distance from the origin to a point. Roughly equivalent to: sqrt(sum(x**2 for x in coordinates)) For a two dimensional point (x, y), gives the hypotenuse using the Pythagorean theorem: sqrt(x*x + y*y). For example, the hypotenuse of a 3/4/5 right triangle is: >>> hypot(3.0, 4.0) 5.0 [clinic start generated code]*/ static PyObject * math_hypot_impl(PyObject *module, PyObject * const *args, Py_ssize_t args_length) /*[clinic end generated code: output=c9de404e24370068 input=1bceaf7d4fdcd9c2]*/ { … } #undef NUM_STACK_ELEMS /** sumprod() ***************************************************************/ /* Forward declaration */ static inline int _check_long_mult_overflow(long a, long b); static inline bool long_add_would_overflow(long a, long b) { … } /*[clinic input] math.sumprod p: object q: object / Return the sum of products of values from two iterables p and q. Roughly equivalent to: sum(map(operator.mul, p, q, strict=True)) For float and mixed int/float inputs, the intermediate products and sums are computed with extended precision. [clinic start generated code]*/ static PyObject * math_sumprod_impl(PyObject *module, PyObject *p, PyObject *q) /*[clinic end generated code: output=6722dbfe60664554 input=a2880317828c61d2]*/ { … } /* pow can't use math_2, but needs its own wrapper: the problem is that an infinite result can arise either as a result of overflow (in which case OverflowError should be raised) or as a result of e.g. 0.**-5. (for which ValueError needs to be raised.) */ /*[clinic input] math.pow x: double y: double / Return x**y (x to the power of y). [clinic start generated code]*/ static PyObject * math_pow_impl(PyObject *module, double x, double y) /*[clinic end generated code: output=fff93e65abccd6b0 input=c26f1f6075088bfd]*/ { … } static const double degToRad = …; static const double radToDeg = …; /*[clinic input] math.degrees x: double / Convert angle x from radians to degrees. [clinic start generated code]*/ static PyObject * math_degrees_impl(PyObject *module, double x) /*[clinic end generated code: output=7fea78b294acd12f input=81e016555d6e3660]*/ { … } /*[clinic input] math.radians x: double / Convert angle x from degrees to radians. [clinic start generated code]*/ static PyObject * math_radians_impl(PyObject *module, double x) /*[clinic end generated code: output=34daa47caf9b1590 input=91626fc489fe3d63]*/ { … } /*[clinic input] math.isfinite x: double / Return True if x is neither an infinity nor a NaN, and False otherwise. [clinic start generated code]*/ static PyObject * math_isfinite_impl(PyObject *module, double x) /*[clinic end generated code: output=8ba1f396440c9901 input=46967d254812e54a]*/ { … } /*[clinic input] math.isnan x: double / Return True if x is a NaN (not a number), and False otherwise. [clinic start generated code]*/ static PyObject * math_isnan_impl(PyObject *module, double x) /*[clinic end generated code: output=f537b4d6df878c3e input=935891e66083f46a]*/ { … } /*[clinic input] math.isinf x: double / Return True if x is a positive or negative infinity, and False otherwise. [clinic start generated code]*/ static PyObject * math_isinf_impl(PyObject *module, double x) /*[clinic end generated code: output=9f00cbec4de7b06b input=32630e4212cf961f]*/ { … } /*[clinic input] math.isclose -> bool a: double b: double * rel_tol: double = 1e-09 maximum difference for being considered "close", relative to the magnitude of the input values abs_tol: double = 0.0 maximum difference for being considered "close", regardless of the magnitude of the input values Determine whether two floating-point numbers are close in value. Return True if a is close in value to b, and False otherwise. For the values to be considered close, the difference between them must be smaller than at least one of the tolerances. -inf, inf and NaN behave similarly to the IEEE 754 Standard. That is, NaN is not close to anything, even itself. inf and -inf are only close to themselves. [clinic start generated code]*/ static int math_isclose_impl(PyObject *module, double a, double b, double rel_tol, double abs_tol) /*[clinic end generated code: output=b73070207511952d input=12d41764468bfdb8]*/ { … } static inline int _check_long_mult_overflow(long a, long b) { … } /*[clinic input] math.prod iterable: object / * start: object(c_default="NULL") = 1 Calculate the product of all the elements in the input iterable. The default start value for the product is 1. When the iterable is empty, return the start value. This function is intended specifically for use with numeric values and may reject non-numeric types. [clinic start generated code]*/ static PyObject * math_prod_impl(PyObject *module, PyObject *iterable, PyObject *start) /*[clinic end generated code: output=36153bedac74a198 input=4c5ab0682782ed54]*/ { … } /* least significant 64 bits of the odd part of factorial(n), for n in range(128). Python code to generate the values: import math for n in range(128): fac = math.factorial(n) fac_odd_part = fac // (fac & -fac) reduced_fac_odd_part = fac_odd_part % (2**64) print(f"{reduced_fac_odd_part:#018x}u") */ static const uint64_t reduced_factorial_odd_part[] = …; /* inverses of reduced_factorial_odd_part values modulo 2**64. Python code to generate the values: import math for n in range(128): fac = math.factorial(n) fac_odd_part = fac // (fac & -fac) inverted_fac_odd_part = pow(fac_odd_part, -1, 2**64) print(f"{inverted_fac_odd_part:#018x}u") */ static const uint64_t inverted_factorial_odd_part[] = …; /* exponent of the largest power of 2 dividing factorial(n), for n in range(68) Python code to generate the values: import math for n in range(128): fac = math.factorial(n) fac_trailing_zeros = (fac & -fac).bit_length() - 1 print(fac_trailing_zeros) */ static const uint8_t factorial_trailing_zeros[] = …; /* Number of permutations and combinations. * P(n, k) = n! / (n-k)! * C(n, k) = P(n, k) / k! */ /* Calculate C(n, k) for n in the 63-bit range. */ static PyObject * perm_comb_small(unsigned long long n, unsigned long long k, int iscomb) { … } /* Calculate P(n, k) or C(n, k) using recursive formulas. * It is more efficient than sequential multiplication thanks to * Karatsuba multiplication. */ static PyObject * perm_comb(PyObject *n, unsigned long long k, int iscomb) { … } /*[clinic input] math.perm n: object k: object = None / Number of ways to choose k items from n items without repetition and with order. Evaluates to n! / (n - k)! when k <= n and evaluates to zero when k > n. If k is not specified or is None, then k defaults to n and the function returns n!. Raises TypeError if either of the arguments are not integers. Raises ValueError if either of the arguments are negative. [clinic start generated code]*/ static PyObject * math_perm_impl(PyObject *module, PyObject *n, PyObject *k) /*[clinic end generated code: output=e021a25469653e23 input=5311c5a00f359b53]*/ { … } /*[clinic input] math.comb n: object k: object / Number of ways to choose k items from n items without repetition and without order. Evaluates to n! / (k! * (n - k)!) when k <= n and evaluates to zero when k > n. Also called the binomial coefficient because it is equivalent to the coefficient of k-th term in polynomial expansion of the expression (1 + x)**n. Raises TypeError if either of the arguments are not integers. Raises ValueError if either of the arguments are negative. [clinic start generated code]*/ static PyObject * math_comb_impl(PyObject *module, PyObject *n, PyObject *k) /*[clinic end generated code: output=bd2cec8d854f3493 input=9a05315af2518709]*/ { … } /*[clinic input] math.nextafter x: double y: double / * steps: object = None Return the floating-point value the given number of steps after x towards y. If steps is not specified or is None, it defaults to 1. Raises a TypeError, if x or y is not a double, or if steps is not an integer. Raises ValueError if steps is negative. [clinic start generated code]*/ static PyObject * math_nextafter_impl(PyObject *module, double x, double y, PyObject *steps) /*[clinic end generated code: output=cc6511f02afc099e input=7f2a5842112af2b4]*/ { … } /*[clinic input] math.ulp -> double x: double / Return the value of the least significant bit of the float x. [clinic start generated code]*/ static double math_ulp_impl(PyObject *module, double x) /*[clinic end generated code: output=f5207867a9384dd4 input=31f9bfbbe373fcaa]*/ { … } static int math_exec(PyObject *module) { … } static int math_clear(PyObject *module) { … } static void math_free(void *module) { … } static PyMethodDef math_methods[] = …; static PyModuleDef_Slot math_slots[] = …; PyDoc_STRVAR(module_doc, "This module provides access to the mathematical functions\n" "defined by the C standard."); static struct PyModuleDef mathmodule = …; PyMODINIT_FUNC PyInit_math(void) { … }
Codebase Browser
cpython