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:
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:
and add a least common multiple function to match.
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.)