[Python-ideas] Add the imath module

[Steven D'Aprano]

On Thu, Jul 12, 2018 at 02:55:58PM +0300, Serhiy Storchaka wrote:

> What are your thoughts about adding a new imath module for integer 
> mathematics? 

I'm not sure that we need a specific module for integer-valued maths. I 
think a more important change would be to allow math functions to be 
written in Python, not just C:

- move the current math library to a private _math library;

- add math.py, which calls "from _math import *".

I often miss having a good, fast, integer square root function in the 
stdlib. I have a slow implementation here:

http://code.activestate.com/recipes/577821-integer-square-root-function/

and as the commentary discusses, a lot of implementations on the 
internet are buggy.

As well as isqrt(n), there's also nsqrt(n), to return the integer 
nearest to the square root of n. They're equivalent to:

isqrt = floor sqrt
nsqrt = round sqrt

without overflowing for large n. (Presumably there's a ceiling sqrt 
function too, but I've never needed it, or seen anyone else use it.)



As far as your other suggestions:

* factorial(n)
* gcd(n, m)

Moving those seem like a fairly pedantic change. But if we did it, we 
could allow gcd to take an arbitrary number of values:

    gcd(*args)

and add a least common multiple function to match.


* as_integer_ration(x)

I think that's mispelled "ratio" :-)

There's currently a private function statistics._exact_ratio which 
does that.


* binom(n, k)

If we have number of combinations, I'd like to have number of 
permutations as well.


* isprime(n)
* primes()

Primality testing and generation of primes is a bigger job than it might 
seem, probably deserving of an entire library. (Not necessarily in the 
std lib.)

But if we did provide a "batteries included" solution, it should also 
include next prime and previous prime functions.

For isprime(), I have a pure-Python solution which is not too shabby, 
capable of giving exact results for all integers up to 2**64 and 
probabilitistic results above that. Despite being pure Python, it's 
reasonably fast. In the REPL, these are essentially instantaneous to the 
naked eye:

py> pyprimes.prev_prime(2**64)
18446744073709551557L
py> pyprimes.is_prime(18446744073709551557L)
True
py> pyprimes.next_prime(2**64)
pyprimes/__init__.py:278: MaybeComposite: 18446744073709551629 is only 
only probably prime
  warnings.warn(message, MaybeComposite)
18446744073709551629L


At the moment this is Python 2 only and frankly overkill for the stdlib. 
I have something like a dozen different implementations for generating 
or testing primes, some of which are (intentionally) just awful. One of 
my favourite so-awful-it's-good algorithms is this one for testing 
whether a number is prime:

def isprime(n):
    # Kids: don't try this at home!
    return not re.match(r'^1?$|^(11+?)\1+$', '1'*n)


But if there is interest in a pure-Python solution, I might be able to 
find time to clean it up to stdlib quality. (Not the regex solution, 
obviously.)



-- 
Steve