Abstract

This PEP proposes a new submodule for number-theoretical, combinatorial and other functions defined for integer arguments, like or .

Motivation

The documentation says: “This module provides access to the mathematical functions defined by the C standard.” But, over time the module was populated with functions that aren’t related to the C standard or floating-point arithmetics. Now it’s much harder to describe module scope, content and interfaces (returned values or accepted arguments).

For example, the following statement from the documentation: “Except when explicitly noted otherwise, all return values are floats.” This is no longer true: None of the functions listed in the Number-theoretic functions subsection of the documentation return a float, but the documentation doesn’t say so. In the documentation for the proposed math.integer submodule the sentence “All return values are integers” would be accurate. In a similar way we can simplify the description of the accepted arguments for functions in both the new submodule and in .

Now it’s a lot harder to satisfy people’s expectations about the module content. For example, should they expect that math.factorial(100) will return an exact answer? Many languages, Python packages (like scipy) or pocket calculators have functions with same or similar name, that return a floating-point value, which is only an approximation in this example.

Apparently, the module can’t serve as a catch-all place for mathematical functions since we also have the and modules. Let’s do the same for integer-related functions. It provides shared context, which reduces verbosity in the documentation and conceptual load. It also aids discoverability through grouping related functions and makes IDE (e.g. new CPython’s REPL) suggestions more helpful.

Currently the module code in the CPython is around 4200LOC, from which the new module code is roughly 1/3 (1300LOC). This is comparable with the (1340LOC), which is not a simple wrapper to the libm, as most functions in the module.

And this situation tends to get worse. When the module split was first proposed, there were only two integer-related functions: (accepting also float’s, like other functions in the module) and (moved from the module). Then , and were added, and addition of the new module was proposed second time, so all new functions would go directly to it, without littering the namespace. Now there are six functions and doesn’t accept floats anymore.

Some possible additions, among those proposed in the initial discussion thread and issue python/cpython#81313 are:

• c_div() and n_div() — for integer division with rounding towards positive infinity (ceiling divide) and to the nearest integer, see relevant discussion thread. This is reinvented several times in the stdlib, e.g. in datetime and fractions. And it’s easy to do this wrongly, as demonstrated by the thread.
• gcdext() — to solve linear Diophantine equation in two variables (the implementation actually includes an extended Euclidean algorithm)
• isqrt_rem() — to return both an integer square root and a remainder (which is non-zero only if the integer isn’t a perfect square)
• ilog() — integer logarithm, has special handling for integer arguments. It’s unique (with respect to other module functions) and not documented so far, see issue python/cpython#120950.
• fibonacci() — Fibonacci sequence.

Separated namespace eliminates possible name clash with existing ‘s module functions. For example, possible names ceil_div() or ceildiv() for integer ceiling division will interfere with the (which is for float’s and sometimes does right things for integer division, as an accident — but usually not).

Rationale

Is this all about documentation, why not fix it instead? No, it isn’t. Sure, we can be much more vague in the module preamble (i.e. roughly say that “the module contains some mathematical functions”), we can accurately describe input/output for each function and its behavior (e.g. whether the output is exact or not, like the scipy.special.factorial, per default).

But the major issue is that the current module mixes different, almost non-interlaced application domains. Adding more documentation will just highlight this and make the issue worse for end users (more text to read/skip). And it will not fix the issue with discoverability (to know in which module to find a function, and that it can be found at all, you need to look at all the functions in the module), nor with tab-completion.

Specification

The PEP proposes moving the following integer-related functions to a new submodule, called math.integer:

Their aliases in will be soft deprecated. This PEP doesn’t introduce backward-incompatible changes.

Module functions will accept integers and objects that implement the method, which is used to convert the object to an integer number. Suitable functions must be computed exactly, given sufficient time and memory.

The intmath package, available on PyPI, will provide new submodule content for older Python versions.

Possible Extensions

New functions (like mentioned in Motivation section) are not part of this proposal.

Though, we should mention that, unless we can just provide bindings to some well supported mathematical library like the GMP, the submodule scope should be limited. For example, no primality testing and factorization, as production-quality implementatons will require a decent mathematical background from contributors and belongs rather to specialized libraries.

When proposed function already exists in the gmpy2, we should prefer a compatible interface for the stdlib.

Backwards Compatibility

As aliases in will be kept indefinitely (their use would be discouraged), there are no anticipated code breaks.

How to Teach This

The new submodule will be a place for functions, that 1) accept -like arguments and also return integers, and 2) are also in the field of arbitrary-precision integer arithmetic, i.e. have no dependency on the platform floating-point format or behaviour and/or on the platform math library (libm).

For users it would be natural first to look on the ‘s methods, which cover most basic use-cases (e.g. method), than to some dedicated place in the stdlib.

Reference Implementation

python/cpython#133909

Rejected ideas

Acknowledgements

Thanks to Victor Stinner for sponsoring this PEP. Thanks to everyone who participated in the discussions on discuss.python.org, providing feedback, especially to Oscar Benjamin, Steve Dower and Paul Moore.

Copyright

This document is placed in the public domain or under the CC0-1.0-Universal license, whichever is more permissive.