Re: [Python-ideas] Add the imath module

[Steve Barnes] > Looking for some information on how long it has taken to generate large > primes I stumbled across > https://arxiv.org/ftp/arxiv/papers/1709/1709.09963.pdf which makes > interesting reading. It concentrates on giving no false negatives (never > saying n is not a prime when it is)

Re: [Python-ideas] Add the imath module

On 12 July 2018 at 23:41, Serhiy Storchaka wrote: > 12.07.18 16:15, Robert Vanden Eynde пише: >> >> About the name, why not intmath ? > > > Because cmath. But if most core developers prefer intmath, I have no > objections. My initial reaction from just the subject title was "But we already have

Re: [Python-ideas] Add the imath module

On Sat, Jul 14, 2018 at 03:39:25PM -0500, Tim Peters wrote: > While my code had no fluff at all. It's hard to believe you could add > enough cruft to slow it down by a factor of 1000, There's a factor of 20 because my computer is older and slower than yours. (I ran your version, and it was

Re: [Python-ideas] Add the imath module

[Tim] > > Steven's numbers are pretty baffling to me, since these are all composite > > and so iterating Miller-Rabin "should get out" pretty fast: > [Steven] > That's because you haven't seen my code :-) > I'd be baffled anyway ;-) about 4.7 seconds to test 2**800 + 1; > I got 1.71 msec,

Re: [Python-ideas] Add the imath module

Looking for some information on how long it has taken to generate large primes I stumbled across https://arxiv.org/ftp/arxiv/papers/1709/1709.09963.pdf which makes interesting reading. It concentrates on giving no false negatives (never saying n is not a prime when it is) but giving an

Re: [Python-ideas] Add the imath module

On Fri, Jul 13, 2018 at 10:52:38AM -0500, Tim Peters wrote: > Steven's numbers are pretty baffling to me, since these are all composite > and so iterating Miller-Rabin "should get out" pretty fast: That's because you haven't seen my code :-) It's over-engineered, class-based, and written as a

Re: [Python-ideas] Add the imath module

Danilo J. S. Bellini wrote: If we have a fast and exact primality test up to 2**64, a signature like this would help: def is_prime(n, probabilistic=False): Two separate functions would be better, by the "no constant boolean parameters" rule. -- Greg

Re: [Python-ideas] Add the imath module

Stephan Houben wrote: Should we call sort then probable_sort, since the non-zero probability exists of it going wrong due to a stray cosmic ray? And in the interests of full disclosure, we should call Python a probable language, running on a probable computer. -- Probable Greg

Re: [Python-ideas] Add the imath module

Instead of `imath`, how about `math.integer` for the module name? On Fri, Jul 13, 2018 at 9:20 AM Tim Peters wrote: > [Steven D'Aprano] >> > about 4.7 seconds to test 2**800 + 1; >> >> [Jeroen Demeyer] >> >>> In SageMath: >>> >>> sage: n = 2**800+1; timeit('is_prime(n)') >>> 625 loops, best of

Re: [Python-ideas] Add the imath module

> > [Steven D'Aprano] > > about 4.7 seconds to test 2**800 + 1; > > [Jeroen Demeyer] > >> In SageMath: >> >> sage: n = 2**800+1; timeit('is_prime(n)') >> 625 loops, best of 3: 303 µs per loop >> >> That's 4 orders of magnitude faster... > > [Tim] > More like 6, yes? > Heh - sorry about that. A

Re: [Python-ideas] Add the imath module

If we have a fast and exact primality test up to 2**64, a signature like this would help: def is_prime(n, probabilistic=False): When probabilistic is False and the number is beyond 2**64, it'll return OverflowError. When probabilistic is True, it's unbounded, but probabilistic. The docs should

Re: [Python-ideas] Add the imath module

> > [Steven D'Aprano] > about 4.7 seconds to test 2**800 + 1; [Jeroen Demeyer] > In SageMath: > > sage: n = 2**800+1; timeit('is_prime(n)') > 625 loops, best of 3: 303 µs per loop > > That's 4 orders of magnitude faster... > More like 6, yes? My Python version is more like 3, but is way fast

Re: [Python-ideas] Add the imath module

On Sat, Jul 14, 2018 at 1:05 AM, Steven D'Aprano wrote: > On Fri, Jul 13, 2018 at 02:51:18PM +0200, Jacco van Dorp wrote: > >> I think the extra 9 characters of "_probable" are worth the extra accuracy. >> >> Dont teach people to lie in their function names. It's a bad example. >> and if you

Re: [Python-ideas] Add the imath module

On Fri, Jul 13, 2018 at 02:51:18PM +0200, Jacco van Dorp wrote: > I think the extra 9 characters of "_probable" are worth the extra accuracy. > > Dont teach people to lie in their function names. It's a bad example. > and if you really want to lie, just In what way is is_probable_prime(11)

Re: [Python-ideas] Add the imath module

There is a VERY slow certain test for primality: divide by every candidate factor (up to sqrt(N)). This is certainly not what we want for very large numbers. But the uncertainty of the probabilistic tests is very small. Steven likened the odds of the test being wrong to "less than the chance of a

Re: [Python-ideas] Add the imath module

Should we call sort then probable_sort, since the non-zero probability exists of it going wrong due to a stray cosmic ray? It's pointless to worry about failure modes which are order of magnitudes unlikelier than hardware failure. Stephan Op vr 13 jul. 2018 14:45 schreef Jeroen Demeyer : > On

Re: [Python-ideas] Add the imath module

I think the extra 9 characters of "_probable" are worth the extra accuracy. Dont teach people to lie in their function names. It's a bad example. and if you really want to lie, just from imath import is_probably_prime as is_prime 2018-07-13 14:44 GMT+02:00 Jeroen Demeyer : > On 2018-07-13

Re: [Python-ideas] Add the imath module

On 2018-07-13 14:11, Steven D'Aprano wrote: What it *actually* does is: is_almost_certainly_prime_except_for_a_ludicrously_microscopic_chance_of_error_thousands_of_times_less_likely_than_a_stray_cosmic_ray_flipping_a_bit_in_memory_and_causing_the_wrong_result_to_be_returned() That's just a

Re: [Python-ideas] Add the imath module

On 2018-07-13 14:26, Steven D'Aprano wrote: I'm pretty sure that Sage is using numpy This computation uses PARI/GP, a dedicated library for number theory (https://pari.math.u-bordeaux.fr/) with a Python interface (https://github.com/defeo/cypari2). And it's probably making far less

Re: [Python-ideas] Add the imath module

On Fri, Jul 13, 2018 at 10:10:00AM +0200, Jeroen Demeyer wrote: > On 2018-07-12 20:11, Steven D'Aprano wrote: > >about 4.7 seconds to test 2**800 + 1; > > In SageMath: > > sage: n = 2**800+1; timeit('is_prime(n)') > 625 loops, best of 3: 303 µs per loop > > That's 4 orders of magnitude

Re: [Python-ideas] Add the imath module

On Fri, Jul 13, 2018 at 01:36:55PM +0200, Jeroen Demeyer wrote: > On 2018-07-13 11:50, Jacco van Dorp wrote: > >At the very least, use is_likely_prime() as function name. > > I agree with you here: the function name should reflect what it actually > does. What it *actually* does is:

Re: [Python-ideas] Add the imath module

On Fri, Jul 13, 2018 at 10:43:12AM +0200, Jacco van Dorp wrote: > If there's going to be failure possible primality tests, there should > also exist certain ones. No matter how slow it can be to do it. > > Python if often a language for beginners. I think it'd be confusing to > a lot of people

Re: [Python-ideas] Add the imath module

On 2018-07-13 11:50, Jacco van Dorp wrote: At the very least, use is_likely_prime() as function name. I agree with you here: the function name should reflect what it actually does. (Note that the technical term is "probable prime", so it should be is_probable_prime) But I don't think that

Re: [Python-ideas] Add the imath module

2018-07-13 11:13 GMT+02:00 Jeroen Demeyer : > On 2018-07-13 10:43, Jacco van Dorp wrote: >> >> If there's going to be failure possible primality tests, there should >> also exist certain ones. No matter how slow it can be to do it. > > > A certain primality test would be too specialized for the

Re: [Python-ideas] Add the imath module

On 2018-07-13 10:43, Jacco van Dorp wrote: If there's going to be failure possible primality tests, there should also exist certain ones. No matter how slow it can be to do it. A certain primality test would be too specialized for the Python stdlib. If you really need that (which you

Re: [Python-ideas] Add the imath module

If there's going to be failure possible primality tests, there should also exist certain ones. No matter how slow it can be to do it. Python if often a language for beginners. I think it'd be confusing to a lot of people that there's going to be tests that show "This one is probably prime",

Re: [Python-ideas] Add the imath module

On 2018-07-13 04:02, Chris Angelico wrote: Haha. Okay. I'm not familiar with every possible primality test, so I had no idea that they ALL have the same failure mode :) There exist guaranteed primality tests, but those are much slower and more complicated. The state of the art is ECPP:

Re: [Python-ideas] Add the imath module

On 2018-07-12 20:11, Steven D'Aprano wrote: about 4.7 seconds to test 2**800 + 1; In SageMath: sage: n = 2**800+1; timeit('is_prime(n)') 625 loops, best of 3: 303 µs per loop That's 4 orders of magnitude faster... ___ Python-ideas mailing list

Re: [Python-ideas] Add the imath module

On Thu, Jul 12, 2018 at 11:05 AM, Steven D'Aprano wrote: > 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

Re: [Python-ideas] Add the imath module

On Fri, Jul 13, 2018 at 2:58 PM, Tim Peters wrote: > [Chris Angelico, on "probable prime" testers] >> >> You can say that about algorithms easily enough. My point is that this >> ought to be a constraint on the function - implementations may choose >> other algorithms, but they MUST follow one

Re: [Python-ideas] Add the imath module

[Chris Angelico, on "probable prime" testers] > You can say that about algorithms easily enough. My point is that this > ought to be a constraint on the function - implementations may choose > other algorithms, but they MUST follow one pattern or the other, > meaning that a Python script can

Re: [Python-ideas] Add the imath module

On Fri, Jul 13, 2018 at 11:48 AM, Steven D'Aprano wrote: > On Fri, Jul 13, 2018 at 10:56:21AM +1000, Chris Angelico wrote: > >> You can say that about algorithms easily enough. My point is that this >> ought to be a constraint on the function - implementations may choose >> other algorithms, but

Re: [Python-ideas] Add the imath module

On Fri, Jul 13, 2018 at 10:56:21AM +1000, Chris Angelico wrote: > You can say that about algorithms easily enough. My point is that this > ought to be a constraint on the function - implementations may choose > other algorithms, but they MUST follow one pattern or the other, > meaning that a

Re: [Python-ideas] Add the imath module

On Thu, Jul 12, 2018 at 05:35:54PM -0500, Tim Peters wrote: > [David Mertz] > > > Miller-Rabin or other pseudo-primality tests do not produce false > > negatives IIUC. > > > > That's true if they're properly implemented ;-) If they say False, the > input is certainly composite (but there isn't

Re: [Python-ideas] Add the imath module

On Fri, Jul 13, 2018 at 10:40 AM, Steven D'Aprano wrote: > On Fri, Jul 13, 2018 at 04:20:55AM +1000, Chris Angelico wrote: >> On Fri, Jul 13, 2018 at 4:11 AM, Steven D'Aprano wrote: >> > There is no reason why primality testing can't be deterministic up to >> > 2**64, and probabilistic with a

Re: [Python-ideas] Add the imath module

On Fri, Jul 13, 2018 at 04:20:55AM +1000, Chris Angelico wrote: > On Fri, Jul 13, 2018 at 4:11 AM, Steven D'Aprano wrote: > > There is no reason why primality testing can't be deterministic up to > > 2**64, and probabilistic with a ludicrously small chance of false > > positives beyond that. The

Re: [Python-ideas] Add the imath module

[David Mertz] > Oops... yeah. I had fixed the "up to and including" previously, but > somehow I copied the wrong version to the thread. > Doesn't matter ;-) The point here, to me, is that the prime generator I pointed at is significantly faster, more memory-frugal, and even "more correct",

Re: [Python-ideas] Add the imath module

Oops... yeah. I had fixed the "up to and including" previously, but somehow I copied the wrong version to the thread. On Thu, Jul 12, 2018 at 6:36 PM Tim Peters wrote: > [David Mertz] > >> Miller-Rabin or other pseudo-primality tests do not produce false >> negatives IIUC. >> > > That's true

Re: [Python-ideas] Add the imath module

[David Mertz] > Miller-Rabin or other pseudo-primality tests do not produce false > negatives IIUC. > That's true if they're properly implemented ;-) If they say False, the input is certainly composite (but there isn't a clue as to what a factor may be); if the say True, the input is "probably"

Re: [Python-ideas] Add the imath module

I take it back... Tim's (really Will Ness's) version is *always* faster and more memory friendly. I'm still trying to understand it though :-). On Thu, Jul 12, 2018 at 6:05 PM David Mertz wrote: > > On Thu, Jul 12, 2018 at 2:22 PM Chris Angelico wrote: > >> On Fri, Jul 13, 2018 at 4:11 AM,

Re: [Python-ideas] Add the imath module

On Thu, Jul 12, 2018 at 2:22 PM Chris Angelico wrote: > On Fri, Jul 13, 2018 at 4:11 AM, Steven D'Aprano > wrote: > > There is no reason why primality testing can't be deterministic up to > > 2**64, and probabilistic with a ludicrously small chance of false > > positives beyond that. The

Re: [Python-ideas] Add the imath module

]Serhiy Storchaka ] > 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

Re: [Python-ideas] Add the imath module

On Fri, Jul 13, 2018 at 4:11 AM, Steven D'Aprano wrote: > There is no reason why primality testing can't be deterministic up to > 2**64, and probabilistic with a ludicrously small chance of false > positives beyond that. The implementation I use can be expected to fail > on average once every 18

Re: [Python-ideas] Add the imath module

On Thu, Jul 12, 2018 at 01:26:45PM -0400, David Mertz wrote: [talking about prime numbers] > That's the point I was getting at. "For your purposes" isn't general enough > to include in the standard library. There are quite a few algorithms and > efficiency trade-offs to decide on. It's not

Re: [Python-ideas] Add the imath module

On Thu, Jul 12, 2018 at 07:50:32PM +0300, Serhiy Storchaka wrote: > 12.07.18 19:14, Steven D'Aprano пише: > >Sorry, I don't understand why you say that divide and round up can't be > >trivially written in Python. Don't you give two implementations > >yourself? > > Sorry, perhaps I was unclear,

Re: [Python-ideas] Add the imath module

On Thu, Jul 12, 2018, 9:31 AM Serhiy Storchaka wrote: > 12.07.18 15:15, David Mertz пише: > > On Thu, Jul 12, 2018, 7:56 AM Serhiy Storchaka > I didn't mean any concrete implementation. Sure there are enough > efficient and simple. I sometimes need a sequence of prime numbers for > solving toy

Re: [Python-ideas] Add the imath module

12.07.18 19:14, Steven D'Aprano пише: Sorry, I don't understand why you say that divide and round up can't be trivially written in Python. Don't you give two implementations yourself? Sorry, perhaps I was unclear, but I said the opposite. ___

Re: [Python-ideas] Add the imath module

On Thu, Jul 12, 2018 at 06:28:19PM +0300, Serhiy Storchaka wrote: > This is the one that is useful in many applications and can't be > trivially written as expression in Python, but is useful in many > applications (date and time, Fraction, Decimal). > > Divide and rounding down: n//m. >

Re: [Python-ideas] Add the imath module

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

Re: [Python-ideas] Add the imath module

12.07.18 17:30, Paul Moore пише: I'm -1 on having inefficient versions like your primes(n) implementation above in the stdlib. People will use them not realising they may not be suitable for anything other than toy problems. This is just the shortest version that I write every time when I need

Re: [Python-ideas] Add the imath module

On 12 July 2018 at 14:30, Serhiy Storchaka wrote: > 12.07.18 15:15, David Mertz пише: >> >> On Thu, Jul 12, 2018, 7:56 AM Serhiy Storchaka > > wrote: >> >> * isprime(n) >> Tests if n is a prime number. >> >> >> How would you test this? The Miller-Rabin

Re: [Python-ideas] Add the imath module

12.07.18 16:15, Robert Vanden Eynde пише: About the name, why not intmath ? Because cmath. But if most core developers prefer intmath, I have no objections. And why not using sage ? Or create a package on pypi ? Because some of these function could be useful in the stdlib. Because the

Re: [Python-ideas] Add the imath module

12.07.18 15:15, David Mertz пише: On Thu, Jul 12, 2018, 7:56 AM Serhiy Storchaka > wrote: * isprime(n) Tests if n is a prime number. How would you test this? The Miller-Rabin Primality test? For large numbers, iterating through candidate prime divisors is

Re: [Python-ideas] Add the imath module

About the name, why not intmath ? And why not using sage ? Or create a package on pypi ? Le jeu. 12 juil. 2018 à 15:11, Serhiy Storchaka a écrit : > 12.07.18 14:55, Serhiy Storchaka пише: > > What are your thoughts about adding a new imath module for integer > > mathematics? It could contain

Re: [Python-ideas] Add the imath module

12.07.18 14:55, Serhiy Storchaka пише: What are your thoughts about adding a new imath module for integer mathematics? It could contain the following functions: I forgot yet one useful function: def divide_and_round(a, b): q, r = divmod(a, b) r *= 2 greater_than_half = r > b if b

Re: [Python-ideas] Add the imath module

On Thu, Jul 12, 2018 at 5:20 AM Daniel Moisset wrote: > (I don't have a good name): something telling that an integer can be > represented exactly as a float One might also ask that question of e.g. decimal.Decimal, fractions.Fraction, so maybe it's better as a method or somewhere else. (Is

Re: [Python-ideas] Add the imath module

primefactors(n): an iterator on the primes that evenly divide n (repeating such as the product is n (I don't have a good name): something telling that an integer can be represented exactly as a float On 12 July 2018 at 12:55, Serhiy Storchaka wrote: > What are your thoughts about adding a new

Re: [Python-ideas] Add the imath module

On Thu, Jul 12, 2018, 7:56 AM Serhiy Storchaka wrote: > * isprime(n) > Tests if n is a prime number. > How would you test this? The Miller-Rabin Primality test? For large numbers, iterating through candidate prime divisors is pricey. * primes() > Returns an iterator of prime numbers: 2, 3, 5,

Re: [Python-ideas] Add the imath module

If you want inspiration: https://github.com/sagemath/sage/blob/master/src/sage/arith/misc.py ___ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: