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
Pytho
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:
https
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", instea
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 typically
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 Pyt
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 t
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 that
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:
is_almost_c
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 faster...
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 conserv
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 lon
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 14:11,
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 2
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
I noticed recently that *all* examples for collection.defaultdict (
https://docs.python.org/3.7/library/collections.html#collections.defaultdict)
are cases of grouping (for an int, a list and a set) from an iterator with
a key, value output.
I wondered how common those constructions were, and what
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)
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 reall
>
> [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 e
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 be
>
> [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
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
Thanks for linking to these. I looked at many of them in my own research,
but for some reason didn't think to write down the links. I'll respond to
each one separately.
Throughout, I'm going to use my proposed ``grouped`` builtin to demonstrate
possible revisions. Note that I am *not* suggesting a
On Mon, Jul 2, 2018 at 8:49 AM Chris Barker wrote:
> On Fri, Jun 29, 2018 at 11:25 PM, Guido van Rossum
> wrote:
>
>
>> Hm, this actually feels heavier to me. But then again I never liked or
>> understood the need for Counter --
>>
>
> actually, me neither -- and partly because it's too lightwei
On Fri, Jul 13, 2018 at 12:38 PM, Michael Selik wrote:
> Thanks for linking to these.
>
yup -- real use cases are really helpful.
Though the other paradigm for grouping is use of setdefault() rather than
defaultdict. So it would be nice to look for those, too.
> I looked at many of them in my
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
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
___
On Sun, Jul 8, 2018 at 12:30 PM David Foster wrote:
> In the past I have personally viewed Python as difficult to use for
> parallel applications, which need to do multiple things simultaneously
> for increased performance:
>
> * The old Threads, Locks, & Shared State model is inefficient in Pytho
On Tue, Jul 10, 2018 at 8:32 AM David Foster wrote:
>
> I was not aware of PyParallel. The PyParellel "parallel thread"
> line-of-execution implementation is pretty interesting. Trent, big kudos
> to you on that effort.
+1 It's a neat project. Trent's pretty smart. :)
> Since you're speaking i
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 le
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 increasi
30 matches
Mail list logo