Abstract

This PEP proposes a new submodule for number-theoretical, combinatorial andother functions defined for integer arguments, likemath.gcd() ormath.isqrt().

Motivation

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

For example, the following statement from the documentation: “Except whenexplicitly noted otherwise, all return values are floats.” This is no longertrue:None of the functions listed in theNumber-theoretic functionssubsection of the documentation return a float, but the documentation doesn’tsay so. In the documentation for the proposedmath.integer submodule the sentence“All return values are integers” would be accurate. In a similar way we cansimplify the description of the accepted arguments for functions in both thenew submodule and inmath.

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

Apparently, themath module can’t serve as a catch-allplace for mathematical functions since we also have thecmath andstatistics 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 aidsdiscoverability through grouping related functions and makes IDE (e.g. newCPython’s REPL) suggestions more helpful.

Currently themath module code in the CPython is around4200LOC, from which the new module code is roughly 1/3 (1300LOC). This iscomparable with thecmath (1340LOC), which isnot asimple wrapper to thelibm, as most functions in themath module.

And this situation tends to get worse. When the module splitwas firstproposed,there were only two integer-related functions:factorial() (accepting alsofloat’s, likeother functions in the module) andgcd() (movedfrom thefractions module). Thenisqrt(),comb() andperm() were added, and addition of the new modulewasproposed second time,so all new functions would go directly to it, without littering themath namespace. Now there are six functions andfactorial() doesn’t acceptfloatsanymore.

Some possible additions, among those proposed in the initial discussion threadand issuepython/cpython#81313 are:

• c_div() andn_div() — for integer division with rounding towardspositive infinity (ceiling divide) and to the nearest integer, seerelevantdiscussion thread. This is reinventedseveral times in the stdlib, e.g. indatetime andfractions.And it’s easy to do this wrongly, as demonstrated by the thread.
• gcdext() — to solve linearDiophantine equation in two variables (theint implementation actually includes an extendedEuclidean 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() hasspecial handling for integer arguments. It’s unique (with respect to othermodule functions) and not documented so far, see issuepython/cpython#120950.
• fibonacci() —Fibonacci sequence.

Separated namespace eliminates possible name clash with existingmath’s module functions. For example, possible namesceil_div() orceildiv() for integer ceiling division will interferewith theceil() (which is forfloat’s andsometimes does right things for integer division, as an accident — butusually 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 “themath module contains some mathematical functions”), wecan accurately describe input/output for each function and its behavior (e.g.whether thefactorial() output is exact or not,like thescipy.special.factorial,per default).

But the major issue is that the current module mixes different, almostnon-interlaced application domains. Adding more documentation will justhighlight 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 finda function, and that it can be found at all, you need to look at all thefunctions in the module), nor with tab-completion.

Specification

The PEP proposes moving the following integer-related functions to a newsubmodule, calledmath.integer:

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

Their aliases inmath will besoft 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 theobject to an integer number. Suitable functions must be computed exactly,given sufficient time and memory.

Theintmath package, available on PyPI, will provide new submodulecontent for older Python versions.

Possible Extensions

New functions (like mentioned inMotivation section) are notpart of this proposal.

Though, we should mention that, unless we can just provide bindings to somewell supported mathematical library like the GMP, the submodule scope should belimited. For example, no primality testing and factorization, asproduction-quality implementatons will require a decent mathematical backgroundfrom contributors and belongs rather to specialized libraries.

When proposed function already exists in thegmpy2, we should prefer acompatible interface for the stdlib.

Backwards Compatibility

As aliases inmath will be kept indefinitely (their usewould be discouraged), there are no anticipated code breaks.

How to Teach This

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

For users it would be natural first to look on theint’s methods, which cover most basic use-cases (e.g.int.bit_length() method), than to some dedicated place inthe 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-Universallicense, whichever is more permissive.