[Python-ideas] Add the imath module

[Tim Peters]

]Serhiy Storchaka <storchaka at gmail.com>]

> What are your thoughts about adding a new imath module for integer
> mathematics? It could contain the following functions:
>

I have mixed feelings :-(  There are a number of integer functions broadly
useful to people attracted to such things, and "it would be nice" to have
basic implementations ship with the language.

But the "basic" is important to me.  Algorithms for unbounded integers can
grow in complexity seemingly without bound too, and by the time there are
10 special cases 8 of which have been coded in C, it becomes an ongoing
maintenance headache - and the code has become so complex that users can't
easily look at the source to judge whether the implementation is _still_
too naive for their application.

For example, for generating primes, I'd balk at anything fancier than my
recoding in Python 3 of Will Ness's beautiful algorithm:

    https://stackoverflow.com/a/19391111/2705542

That generates primes in increasing order, with no need (or even
possibility) to specify an upper bound in advance.  But unlike nearly all
other reasonably efficient approaches to that, the memory burden grows
(very roughly) with the square root of the largest prime generated so far.
Most sieve algorithms require instead remembering all the ~P/log(P) primes
<= P, which grows much faster than sqrt(P).  That's a real practical
difference.

There are faster ways to generate the primes, and even that way can be sped
significantly by complicating the code significantly to incorporate a
multiple-small-prime wheel.

But I'd much rather leave significantly more complicated code to
_specialized_, non-core packages.

Anyway, in addition to your list, there are at least four others I view as
fundamental:

def iroot(n, k):  # the obvious generalization of integer square root
    """Return the floor of the k'th root of n."""

def egcd(a, b):   # extended gcd
    """Return (g, ga, gb) s.t. ga*a + gb*b == g == gcd(a, b)."""

def minv(p, q):
    """
    Return multiplicative modular inverse of p with respect to modulus q.

    (p * minv(p, q)) % q == 1
    """

def factor(n):
    """Return a list containing n's prime factors."""

State-of-the-art code for `factor()` alone could double the size of the
Python source distribution ;-)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20180712/28e89099/attachment.html>