Abstract

This PEP proposes a new module for number-theoretical, combinatorial and other functions defined for integer arguments, like math.gcd() or math.isqrt().

Motivation

The math 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 intmath module 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 module and in math.

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 math module can’t serve as a catch-all place for mathematical functions since we also have the cmath and statistics 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 suggestions more helpful.

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

And this situation tends to get worse. When the module split was first proposed, there were only two integer-related functions: factorial() (accepting also float’s, like other functions in the module) and gcd() (moved from the fractions module). Then isqrt(), comb() and perm() were added, and addition of the new module was proposed second time, so all new functions would go directly to it, without littering the math namespace. Now there are six functions and factorial() 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.
• gcdext() — to solve linear Diophantine equation in two variables (the int 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, math.log() 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.

Rationale

Why not fix the math module documentation instead? Sure, we can be much more vague in the module preamble (i.e. roughly say that “the math module contains some mathematical functions”), we can accurately describe input/output for each function and its behavior (e.g. whether the factorial() 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 module, called intmath (see Open Issues for alternatives for it’s name):

• comb()
• factorial()
• gcd()
• isqrt()
• lcm()
• perm()

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

Module functions will accept integers and objects that implement the __index__() 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 will provide new module 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 module 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 math will be kept for an indefinite time (their use would be discouraged), there are no anticipated code breaks.

How to Teach This

The new module will be a place for functions, that 1) accept int-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 int’s methods, which cover most basic use-cases (e.g. int.bit_length() method), than to some dedicated place in the stdlib.

Reference Implementation

python/cpython#133909

Rejected ideas

Open Issues

Polling showed intmath as most popular candidate with imath as a second winner.

Other proposed names include ntheory (like SymPy’s submodule), integermath, zmath, dmath and imaths.

As a variant, the new module can be added as a submodule of the math: integer (most preferred), discrete or ntheory (author preference).

Acknowledgements

Thanks to Tim Peters for reviving the idea of splitting the math module. Thanks to Neil Girdhar for substantial improvements of the initial draft.

Copyright

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