Split out integer functions from the math module (original) (raw)

Docs says: “This module provides access to the mathematical functions defined by the C standard.” It’s not a lie, strictly speaking, but close to. In fact, module has much more functions, working with integers and not related to the libm’s wrappers or floating-point arithmetic at all.

IMO, functions for integers (now placed in subsection Number-theoretic functions) deserve own module. How about “ntheory” or “imath”? Regarding backward compatibility, we can keep old aliases for functions with zero maintenance cost.

I slightly worry if this may open a Pandora’s box with feature requests like “I want ntheory.isprime()”. Though, such requests are possible for the math module as well.

Edit
The PEP draft: Draft PEP: imath --- module for number-theoretic functions by skirpichev · Pull Request #8 · skirpichev/peps · GitHub

blhsing (Ben Hsing) May 9, 2025, 7:04am 2

Integer math is still math, and beginners looking for a math function are a lot more likely to instinctively look for it in the math module. So to me it is more intuitive to keep math functions where they are, but change the documentation to read simply “This module provides access to mathematical functions” without a mention of the C standard.

Rosuav (Chris Angelico) May 9, 2025, 7:09am 3

By the same token, complex math is still math, but we have a separate module for that. Integers and floats aren’t the same, and shouldn’t be treated the same way.

+1 for imath, and then having functions like math.isqrt become aliases for imath.sqrt.

blhsing (Ben Hsing) May 9, 2025, 7:19am 4

cmath has tens of overlapping functions with math, which is what makes them worth their own namespace.

Currently the only overlapping function of integer math and floating point math is sqrt, and the ceildiv function currently in discussion doesn’t have a floating-point version in math either. So given the lack of overlaps I don’t think integer math functions need their own namespace just yet.

skirpichev (Sergey B Kirpichev) May 9, 2025, 7:39am 5

The argument still holds at some degree, because integer functions (esp. something like gcd) — much less “advanced” stuff than the cmath’s content.

Using sqrt() is still possible with any module naming.

The imath looks alike cmath, but as pointed out — the math and cmath have a lot of common functions (just with a different domain/codomain), which will not be the case for imath and math.

NeilGirdhar (Neil Girdhar) May 9, 2025, 9:53am 6

At the end of the day, math is a bad home for integer functions. It doesn’t matter if “beginners look there” since they find what they’re looking for immediately with Google.

It also doesn’t matter how much overlap there is between imath and math. That’s not the motivation for creating a library.

I also like imath by analogy to cmath, and like the idea of renaming math.isqrt to imath.sqrt.

I would rather not rename isqrt as sqrt because it is not the same function:

>>> math.isqrt(3)
1

It makes sense that math.sqrt is a restriction of cmath.sqrt or conversely that cmath.sqrt is an extension of math.sqrt. The isqrt function is not a restriction of the others.

In gmpy2 there are isqrt and isqrtrem. In python-flint there is fmpz.sqrt but it raises an error if not exact:

>>> flint.fmpz(4).sqrt()
2
>>> flint.fmpz(3).sqrt()
...
DomainError

That kind of sqrt is a restriction of the real sqrt to the integer domain. The sqrtrem meth is provided as an integer-specific alternative:

>>> flint.fmpz(3).sqrtrem()
(1, 2)

NeilGirdhar (Neil Girdhar) May 9, 2025, 1:14pm 8

Good points. But maybe isqrt is the wrong name then? floor_sqrt?

skirpichev (Sergey B Kirpichev) May 9, 2025, 1:39pm 9

IMO, it’s not too helpful. If someone carry about exactness — sqrtrem() is a better option than an exception from the sqrt().

Though, I’m not sure it’s a strong argument. Both variants (isqrt/sqrt) appear in languages/libraries (e.g. GMP has both mpz_sqrt and mpf_sqrt).

BTW, sqrt_rem() could be a useful addition for a new module.

No, it’s definitely not a wrong name, see e.g. Maple. The floor_sqrt seems to be an accurate description, but I can’t provide an example of language/library, where function was named that way.

NeilGirdhar (Neil Girdhar) May 9, 2025, 1:40pm 10

If it’s an accurate description, what does it matter what Maple calls it?

pf_moore (Paul Moore) May 9, 2025, 1:53pm 11

For the same reason that sqrt is a better name than square_root. It’s common terminology, and concise. I’ve seen the name isqrt used in many places, but never floor_sqrt. I don’t have the experience in this domain that @oscarbenjamin has, but I agree with his intuition that isqrt is the right name here.

NeilGirdhar (Neil Girdhar) May 9, 2025, 1:57pm 12

FWIW Wolfram calls it FloorSqrt, but I’m indifferent.

skirpichev (Sergey B Kirpichev) May 9, 2025, 2:12pm 13

It’s from some extension, not the Mathematica::

Wolfram Language 14.1.0 Engine for Linux x86 (64-bit)
Copyright 1988-2024 Wolfram Research, Inc.

In[1]:= FloorSqrt

Out[1]= FloorSqrt

In[2]:=

NeilGirdhar (Neil Girdhar) May 9, 2025, 2:13pm 14

As an aside, a new integer math library might be a good motivation to add a few of the most common integer math functions that may have been neglected for not having a good place.

These functions often come up in competitive programming, cryptography, algorithms, and systems programming.

For example:

1. Bitwise & Binary Utilities
2. Divisibility & Modular Arithmetic
3. Integer Roots & Checks
4. Primality & Factorization
5. Integer Sequences & Algorithms
6. Encoding & Number Representations

oscarbenjamin (Oscar Benjamin) May 9, 2025, 2:43pm 15

Another variant of sqrt that python-flint has that I didn’t mention before is sqrtmod:

>>> flint.fmpz(-1).sqrtmod(5)
2

An obvious generalisation of isqrt is an iroot function that can do cube roots etc.

Primality and factorisation would certainly be useful but that is too big a can of worms for stdlib.

skirpichev (Sergey B Kirpichev) May 9, 2025, 2:54pm 16

Pandora’s box)

I would say we could add something more or less trivial, but not include things, that require deep mathematical knowledge. Well, unless this will be just bindings to some well supported library like the GMP. IMO it’s possible (major technical issue with the GMP is it’s memory management — but this seems solvable), but that’s another story.

For your list:

  1. we already have int.bit_length()
  2. modinv & is_coprime could be replaced by more generic gcdext() function (solves linear Diophantine equation in two variables)
  3. is_perfect_square() could be replaced by isqrt_rem() (both integer square root and remainder)
  4. primality tests & factorization, probably — out of the scope, as being too complex

BTW, maybe this proposal does require a PEP? Then possible module extensions could be discussed as well in same shot.

pf_moore (Paul Moore) May 9, 2025, 3:21pm 17

Scope creep’s a great way to kill an idea. Let’s keep things focused, and worry about extra features once the basic idea is implemented.

NeilGirdhar (Neil Girdhar) May 9, 2025, 3:24pm 18

For clarity, I never proposed adding any functions as part of this idea. (And therefore this isn’t a change of scope at all.)

I’m saying, in support of the idea, that it would allow us to add other integer math functions more easily.

Also, a reviewer for a hypothetical PEP might ask whether it’s worth creating such a library for only four functions. They may ask, what else might eventually find a home in imath. My list is intended to answer that question.

oscarbenjamin (Oscar Benjamin) May 9, 2025, 3:55pm 19

Yes it is worthwhile to consider what functions might hypothetically one day be in an imath module even if they are not part of the immediate proposal. There should be some sense of the intended scope of the module so that it doesn’t end up muddled like math is already.

Another function that would good to have is an integer logarithm. Currently math.log does does this ambiguously by special casing int (see issue).

tim.one (Tim Peters) May 9, 2025, 6:41pm 20

I think it does, yes. When we added graphlib a few years back, it drew complaints from core devs who apparently felt they should have been consulted first. Why, I don’t know :wink:. More than one core dev was active in its creation and journey to final code, all done in full public view.

At the least, adding a new module is a big enough change that the Steering Council should bless it. The one clear way to accomplish that is to ask them to judge a finished PEP.