Re: [Python-ideas] Add the imath module

[Tim Peters]

[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) but giving an increasing probability
> that n is a prime as testing goes on.
>

That's a very nice, gentle introduction!  Thanks for sharing it.

The `pp()` function I posted before is a Python implementation of the
Miller-Rabin test they ended with.  The latter is very widely used, because
the code is relatively simple. short, and fast, and has no "bad cases".

For _generating_ primes, the article uses other tricks to weed out
sure-to-be-composite candidates before bothering with probable-prime
testing.  But the tricks they use in the paper are specific to a base 10
representation.  In binary, it's common to skip candidates such that

gcd(candidate, 2 * 3 * 5 * ...) > 1

where the product-of-small-primes second argument is picked to be the
largest such that bigint division by it is exceptionally fast (usually one
"digit" in whatever internal power-of-2 base is used by the bigint
implementation).


I did find an article from 2016 that mentioned M77232917 (a 23,249,425
> digit Mersenne prime) and M74207281 (22,338,618 digit Mersenne prime)
> with the latter taking a month to check with the Lucas-Lehmer test.
>

More, it's a special version of Lucas-Lehmer (LL) that only works for
testing candidates of the form 2**p-1 where p is itself an odd prime.  In
that context, it's not probabilistic - it definitively answers whether
2**p-1 is prime.  Fast as it is, Miller-Rabin is impractical for guessing
about numbers of this size.  And as enormously faster as _it_ is, the
special version of LL used for Mersenne testing is largely hand-coded in
assembler to squeeze out every possible machine cycle.

I don't want any of that in Python's standard library either ;-)

Here!  You should enjoy this account of the even larger Mersenne prime
discovered this year:

https://www.mersenne.org/primes/press/M77232917.html

Note that the hyper-optimized testing code they use is so historically
error-prone (& so good at provoking HW errors on overheated machines!) that
they now verify each new Mersenne prime by 4 entirely different LL
implementations, on 4 different machines.
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Nick Coghlan]

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 cmath, why would we need imath?", based on the fact that
mathematicians write complex numbers as "X + Yi", rather than the "X +
Yj" that Python borrowed from electrical engineering (where "i"
already had a different meaning as the symbol for AC current).

Calling the proposed module "intmath" instead would be clearer to me
(and I agree with the rationale that as the number of int-specific
functions increases, separating them out from the more float-centric
math module makes sense).

Beyond that, I think the analogy with the statistics module is a good one:

1. There are a number of integer-specific algorithms where naive
implementations are going to be slower than they need to be, subtly
incorrect in some cases, or both. With a standard library module, we
can provide a robust test suite, and pointers towards higher
performance alternatives for folks that need them.
2. For educational purposes, being able to introduce the use cases for
a capability before delving into the explanation of how that
capability works can be quite a powerful technique (the standard
implementations can also provide a cross-check on the accuracy of
student implementations).

And in the intmath case, there are likely to be more opportunities to
delete private implementations from other standard library modules in
favour of the public intmath functions.

Cheers,
Nick.

-- 
Nick Coghlan   |   ncogh...@gmail.com   |   Brisbane, Australia
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Steven D'Aprano]

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 ~20 times slower on my computer 
than the numbers you give.)

So the cruft factor is only 50 times :)


> but pretty much
> impossible to believe adding cruft could make it way faster in the middle
> case above.
> 
> Or do you first try division by small primes?  2**900+1 could get out cheap
> in that case, because it happens to be divisible by 17.

Yes indeed. My approach is:

1. trial division by small primes;
2. Miller-Rabin by a minimal set of provably deterministic 
   witnesses (if such a set exists, which it does for n < 2**64);
3. or by the first twelve primes if no such known set exists;
4. followed by 30 random witnesses.

12+30 = 42 Miller-Rabin tests may be overkill :-)


-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Tim Peters]

[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, over a thousand times faster.


> less than a tenth of a millisecond to test 2**900 + 1;
>

I got 2.32 msec, over 20 times _slower_(!).

and about 8.6 seconds to test 2**1000 + 1.


And I got 3.14 msec, again over a thousand times faster.

It's over-engineered, class-based, and written as a learning exercise.
> There's a compatibility layer so it will work back to Python 2.4 and an
> instrumentation layer which I inserted in a fit of enthusiasm to gather
> staticistics, which I have never once looked at since.
>

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, but pretty much
impossible to believe adding cruft could make it way faster in the middle
case above.

Or do you first try division by small primes?  2**900+1 could get out cheap
in that case, because it happens to be divisible by 17.



> And *even so* it is still fast enough for casual use at the interactive
> interpreter, compared to more naive algorithms with worse Big O
> performance characteristics.
>
> You might think 5 seconds is slow, but I'm serious when I say some of
> the other algorithms I played with would take *days* to generate,
> or check, largish primes.
>

No argument from me.  There's a reason I wrote my `pp()` to begin with too
-)  State-of-the-art code for these things requires planet-sized brains and
commitment, but even a little expert knowledge can yield simple code that's
an enormous improvement over any "dead obvious" approach.
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

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) but giving an increasing probability 
that n is a prime as testing goes on.

I did find an article from 2016 that mentioned M77232917 (a 23,249,425 
digit Mersenne prime) and M74207281 (22,338,618 digit Mersenne prime) 
with the latter taking a month to check with the Lucas-Lehmer test.


On 14/07/2018 05:54, Steven D'Aprano wrote:
> 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 learning exercise.
> There's a compatibility layer so it will work back to Python 2.4 and an
> instrumentation layer which I inserted in a fit of enthusiasm to gather
> staticistics, which I have never once looked at since.
> 
> And *even so* it is still fast enough for casual use at the interactive
> interpreter, compared to more naive algorithms with worse Big O
> performance characteristics.
> 
> You might think 5 seconds is slow, but I'm serious when I say some of
> the other algorithms I played with would take *days* to generate,
> or check, largish primes.
> 
> 

-- 
Steve (Gadget) Barnes
Any opinions in this message are my personal opinions and do not reflect 
those of my employer.

---
This email has been checked for viruses by AVG.
https://www.avg.com

___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Steven D'Aprano]

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 learning exercise. 
There's a compatibility layer so it will work back to Python 2.4 and an 
instrumentation layer which I inserted in a fit of enthusiasm to gather 
staticistics, which I have never once looked at since.

And *even so* it is still fast enough for casual use at the interactive 
interpreter, compared to more naive algorithms with worse Big O 
performance characteristics.

You might think 5 seconds is slow, but I'm serious when I say some of 
the other algorithms I played with would take *days* to generate, 
or check, largish primes.


-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Greg Ewing]

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
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Greg Ewing]

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
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[George Leslie-Waksman]

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 3: 303 µs per loop
>>>
>>> That's 4 orders of magnitude faster...
>>
>>
> [Tim]
>
>> More like 6, yes?
>>
>
> Heh - sorry about that.  A speck of dirt on my monitor made me read '303"
> as "3.03".
>
>
>>   My Python version is more like 3, but is way fast enough for most
>> things I do:
>>
>
> So my Python Miller-Rabin code (already shared) was about one order of
> magnitude slower.
>  ...
>
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Tim Peters]

>
> [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 speck of dirt on my monitor made me read '303"
as "3.03".


>   My Python version is more like 3, but is way fast enough for most things
> I do:
>

So my Python Miller-Rabin code (already shared) was about one order of
magnitude slower.
 ...
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Danilo J. S. Bellini]

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 explicit about that, though.

Instead of an OverflowError,
a number beyond 2**64 might simply use a slower strategy.
But to make it an explicit option, the signature could be:

def is_prime(n, exact=True, unbounded=False):

By tellling it should be both exact and unbounded,
the user is aware that it might be slow.

The alternatives are:

   - exact, unbounded: Slower test
   - not exact, unbounded: Probabilistic test
   - exact, bounded: Default, raises OverflowError beyond 2**64
   - not exact, bounded: Invalid, but it can just ignore exact input

-- 
Danilo J. S. Bellini
---
"*It is not our business to set up prohibitions, but to arrive at
conventions.*" (R. Carnap)
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Tim Peters]

>
> [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 enough
for most things I do:

$ py -m timeit -s "from temp3 import pp; n=2**800+1" "pp(n)"
200 loops, best of 5: 1.71 msec per loop

$ py -m timeit -s "from temp3 import pp; n=2**900+1" "pp(n)"
100 loops, best of 5: 2.32 msec per loop

$ py -m timeit -s "from temp3 import pp; n=2**1000+1" "pp(n)"
100 loops, best of 5: 3.15 msec per loop

Steven's numbers are pretty baffling to me, since these are all composite
and so iterating Miller-Rabin "should get out" pretty fast:

about 4.7 seconds to test 2**800 + 1;
> less than a tenth of a millisecond to test 2**900 + 1;
> and about 8.6 seconds to test 2**1000 + 1.


Here's the Python code I used:

def pp(n, k=10):
"""
Return True iff n is a probable prime, using k Miller-Rabin tests.

When False, n is definitely composite.
"""
from random import randrange

if n < 4:
return 2 <= n <= 3
d = nm1 = n-1
s = 0
while d & 1 == 0:
s += 1
d >>= 1
if s == 0:
return False # n >= 4 and even
ss = range(1, s)
for _ in range(k):
a = randrange(2, nm1)
x = pow(a, d, n)
if x == 1 or x == nm1:
continue
for _ in ss:
x = x*x % n
if x == nm1:
break
if x == 1:
return False
else:
return False
return True
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Chris Angelico]

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 really want to lie, just
>
> In what way is
>
> is_probable_prime(11)  # returns True
>
> less true than
>
> isprime(11)  # returns True
>
> If you want to *lie*, then claiming that 11 is a probable prime is
> certainly a lie.
>

It's a probable lie?

ChrisA
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Steven D'Aprano]

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)  # returns True

less true than

isprime(11)  # returns True

If you want to *lie*, then claiming that 11 is a probable prime is 
certainly a lie.


-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[David Mertz]

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
cosmic ray hitting a memory cell and altering the result." In any case, an
amateur programmer could write a tight loop testing random large numbers
and leave it running for the rest of their life without ever encountering a
false positive. Number theorists have constructed these false positives...
But if you know enough to do that construction, this isn't going to confuse
you.

On Fri, Jul 13, 2018, 4:44 AM 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 there's going to be tests that show "This one is
> probably prime", instead of sure tests.
>
> I'd call the functions is_prime() and is_likely_prime() (or
> is_likely_not_prime(), depending on where it fails), to make it really
> clear which you're picking and avoid confusion.
>
> 2018-07-13 10:21 GMT+02:00 Jeroen Demeyer :
> > 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://en.wikipedia.org/wiki/Elliptic_curve_primality
> >
> > ___
> > Python-ideas mailing list
> > Python-ideas@python.org
> > https://mail.python.org/mailman/listinfo/python-ideas
> > Code of Conduct: http://python.org/psf/codeofconduct/
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Stephan Houben]

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 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 long variant of is_probable_prime()
>
> > If your bank is satisfied with "mere probable prime number" to transfer
> > billions of dollars around the world, then I'm sure that the users of
> > Python's std library should be too.
>
> That's besides the point. I agree that probable primes are good enough,
> just don't call them "prime".
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Jacco van Dorp]

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, 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 long variant of is_probable_prime()
>
>> If your bank is satisfied with "mere probable prime number" to transfer
>> billions of dollars around the world, then I'm sure that the users of
>> Python's std library should be too.
>
>
> That's besides the point. I agree that probable primes are good enough, just
> don't call them "prime".
>
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Jeroen Demeyer]

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 long variant of is_probable_prime()


If your bank is satisfied with "mere probable prime number" to transfer
billions of dollars around the world, then I'm sure that the users of
Python's std library should be too.


That's besides the point. I agree that probable primes are good enough, 
just don't call them "prime".

___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Jeroen Demeyer]

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 conservative choices about the rate of false
positives it is willing to accept.


It's an actual primality test, not a probable primality test. But for 
numbers which are not prime (like your examples), the difference doesn't 
actually matter.

___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Steven D'Aprano]

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...

Go on, rub it in why don't you...

I'm pretty sure that Sage is using numpy, which would almost certainly 
have a C-based implementation, not pure Python like mine. And it's 
probably making far less conservative choices about the rate of false 
positives it is willing to accept.

And your computer is probably newer and faster than mine :-(

My point was that for casual use, even the bad cases are still fast 
enough for interactive use. If you think 5 seconds is ridiculously slow, 
you've never tried a naive trial division algorithm that took literally 
days to crawl through the millions of divisions needed.

*wink*



-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Steven D'Aprano]

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_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()

*At most*, I would agree that the isprime() function could raise a 
"Probably Prime" warning when necessary, with the warning disabled by 
default. Those that care about this sort of thing can enable warnings, 
those that don't shouldn't have to read scary warnings that have no 
practical meaning.

If your bank is satisfied with "mere probable prime number" to transfer 
billions of dollars around the world, then I'm sure that the users of 
Python's std library should be too.


-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Steven D'Aprano]

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 there's going to be tests that show "This one is
> probably prime", instead of sure tests.

I think that it is precisely because this will be used by beginners that 
we shouldn't offer such a choice. Its our job to curate the APIs in the 
std lib, not to burden inexpert users with excess choices that will only 
worry them.

If this were a third-party module, I would say, "the more the merrier". 
Let it provide a dozen different implementations, that's cool. But the 
stdlib is batteries, not nuclear reactors. If you want a choice of 
algorithms, or the ability to configure space versus time versus 
guarantees, I think you ought to be using a 3rd party module, not the 
std library.


I'm not saying hide the fact that it is probabilistic, but that's an 
implementation detail that *in practice* makes no difference at all. 
Using Miller-Rabin and 30 randomly chosen witnesses, the probability of 
a wrong answer is < 0.01. If we tested a million numbers 
a second, it would take an average of 18,000+ years to come across a 
single such error.

In comparison, your computer probably experiences something of the order 
of 1 cosmic-ray induced bit-flip causing data corruption per week.

https://stackoverflow.com/questions/2580933/cosmic-rays-what-is-the-probability-they-will-affect-a-program

Since using probabilistic methods is good enough for PGP and other 
high-security protocols, it's surely good enough for Tom Schoolboy 
testing whether 1234567890123456789 is prime.

(For the record: it isn't.)


-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Jeroen Demeyer]

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 the Python stdlib should have a proven is_prime() 
function because that would be complicated, slow and have very limited 
benefit over is_probable_prime().

___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Jacco van Dorp]

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 Python stdlib. If
> you really need that (which you typically don't), there are existing number
> theory packages.

You forgot to include my reasons for this:

>> 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", instead of sure tests.

Depending on function names, of course. It needn't be the fastest
available, but its what people would expect, especially those with
less experience. Also, there's existing number theory packages for
everything suggested here, so that's not an argument.

At the very least, use is_likely_prime() as function name. Otherwise,
the name of the function is just plain wrong. Don't claim accuracy you
don't have.
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[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 Python stdlib. 
If you really need that (which you typically don't), there are existing 
number theory packages.

___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Jacco van Dorp]

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", instead of sure tests.

I'd call the functions is_prime() and is_likely_prime() (or
is_likely_not_prime(), depending on where it fails), to make it really
clear which you're picking and avoid confusion.

2018-07-13 10:21 GMT+02:00 Jeroen Demeyer :
> 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://en.wikipedia.org/wiki/Elliptic_curve_primality
>
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Jeroen Demeyer]

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://en.wikipedia.org/wiki/Elliptic_curve_primality
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Jeroen Demeyer]

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
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Chris Barker via Python-ideas]

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 library;
>
> - add math.py, which calls "from _math import *".
>

FWIW, Guido rejected that idea when we added math.isclose() -- Victor had
even written it up already.

Not that people never change their mind...

-CHB

-- 

Christopher Barker, Ph.D.
Oceanographer

Emergency Response Division
NOAA/NOS/OR(206) 526-6959   voice
7600 Sand Point Way NE   (206) 526-6329   fax
Seattle, WA  98115   (206) 526-6317   main reception

chris.bar...@noaa.gov
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Chris Angelico]

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 pattern or the other,
>> meaning that a Python script can depend on it without knowing the
>> implementation. Like guaranteeing that list.sort() is stable without
>> stipulating the actual sort algo used.
>
>
> I agree!  Don't worry about it - if this module gets added, I'll make sure
> of it.  My own "probable prime" function starts like so:
>
> def pp(n, k=10):
> """
> Return True iff n is a probable prime, using k Miller-Rabin tests.
>
> When False, n is definitely composite.
> """
>
> In the context of algorithmic number theory, "no false negatives" is implied
> by that context, but it should be spelled out anyway.  A "probable prime",
> by definition, is an integer that satisfies some property that _all_ primes
> satisfy, but that some composites may satisfy too.  The variation among
> probable prime algorithms is in which specific property(ies) they test for.
>
> For example:
>
> def pp1(n):
> return True
>
> meets the promise, but is useless ;-)
>
> def pp2(n):
> return  n % 3 != 0 or n == 3
>
> is slightly less useless.
>
> But
>
> def pp3(n):
> return n % 3 != 0
>
> would be incorrect, because pp3(3) returns False - `n % 3 != 0` is not a
> property that all primes satisfy.
>

Thank you. Great explanation. Much appreciated!

ChrisA
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Tim Peters]

[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 depend on it without knowing the
> implementation. Like guaranteeing that list.sort() is stable without
> stipulating the actual sort algo used.
>

I agree!  Don't worry about it - if this module gets added, I'll make sure
of it.  My own "probable prime" function starts like so:

def pp(n, k=10):
"""
Return True iff n is a probable prime, using k Miller-Rabin tests.

When False, n is definitely composite.
"""

In the context of algorithmic number theory, "no false negatives" is
implied by that context, but it should be spelled out anyway.  A "probable
prime", by definition, is an integer that satisfies some property that
_all_ primes satisfy, but that some composites may satisfy too.  The
variation among probable prime algorithms is in which specific
property(ies) they test for.

For example:

def pp1(n):
return True

meets the promise, but is useless ;-)

def pp2(n):
return  n % 3 != 0 or n == 3

is slightly less useless.

But

def pp3(n):
return n % 3 != 0

would be incorrect, because pp3(3) returns False - `n % 3 != 0` is not a
property that all primes satisfy.
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Chris Angelico]

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 they MUST follow one pattern or the other,
>> meaning that a Python script can depend on it without knowing the
>> implementation. Like guaranteeing that list.sort() is stable without
>> stipulating the actual sort algo used.
>
> I cannot imagine an algorithm that wasn't totally brain-dead (like "flip
> a coin") which could wrongly report a prime number as composite. Maybe
> I'm not imaginative enough :-)

Haha. Okay. I'm not familiar with every possible primality test, so I
had no idea that they ALL have the same failure mode :)

ChrisA
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Steven D'Aprano]

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 Python script can depend on it without knowing the
> implementation. Like guaranteeing that list.sort() is stable without
> stipulating the actual sort algo used.

I cannot imagine an algorithm that wasn't totally brain-dead (like "flip 
a coin") which could wrongly report a prime number as composite. Maybe 
I'm not imaginative enough :-)

But yeah, if you want to formally specify that any such isprime test 
will never have false negatives (never report an actual prime as 
composite), sure thing. I think that's stating the bleeding obvious, 
like demanding that any algorithm we use for factorial(n) must not 
return the sqrt of n by mistake, but whatever :-)

I suppose that if you cared more about running time than correctness, 
one might simply report anything bigger than (let's say) 2**20 as 
"composite". But I call that "brain dead" :-)



-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Steven D'Aprano]

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 a clue as to what a factor
> may be); if the say True, the input is "probably" a prime.

I'm sure Tim knows this, but that's only sometimes true. Since I had no 
formal education on primality testing and had to pick this up in dribs 
and drabs over many years, I was under the impression for the longest 
time that Miller-Rabin was always probabilitistic, but that's not quite 
right.

Without going into the gory details, it turns out that for any N, you 
can do a brute-force primality test by checking against *every* 
candidate up to some maximum value. (Which is how trial division works, 
only Miller-Rabin tests are more expensive than a single division.) Such 
an exhaustive check is not practical, hence the need to fall back on 
randomly choosing candidates.

However, that's in the most general case. At least for small enough N, 
there are rather small sets of candidates which give a completely 
deterministic and conclusive result. For N <= 2**64, it never requires 
more than 12 Miller-Rabin tests to give a conclusive answer, and for 
some N, as few as a single test is enough.

To be clear, these are specially chosen tests, not random tests.

So in a good implementation, for N up to 2**64, there is never a need 
for a "probably prime" result. It either is, or isn't prime, and there's 
no question which.

In principle, there could be similar small sets of conclusive tests for 
larger N too, but (as far as I know) nobody has discovered them yet. 
Hence we fall back on choosing Miller-Rabin tests at random. The chances 
of an arbitrary composite number passing k such tests is on average 
1/4**k, so we can make the average probability of failure as small as we 
like, by doing more tests. With a dozen or twenty tests, the probability 
of a false positive (a composite number wrongly reported as prime) is of 
the same order of magnitude as that of a passing cosmic ray flipping a 
bit in memory and causing the wrong answer to appear.



-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Chris Angelico]

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 ludicrously small chance of false
>> > positives beyond that. The implementation I use can be expected to fail
>> > on average once every 18 thousand years if you did nothing but test
>> > primes every millisecond of the day, 24 hours a day. That's good enough
>> > for most purposes :-)
>>
>> What about false negatives? Guaranteed none? The failure mode of the
>> function should, IMO, be a defined and documented aspect of it.
>
> If a non-deterministic primality tester such as (but not limited to)
> Miller-Rabin says a number is composite, it is definitely composite
> (ignoring bugs in the implementation, or hardware failures). If it says
> it is prime, in the worst case it is merely "probably prime", with an
> error rate proportional to 1/4**k where we can choose the k.
>
> (The bigger the k the more work may be done in the worst case.)

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 depend on it without knowing the
implementation. Like guaranteeing that list.sort() is stable without
stipulating the actual sort algo used.

ChrisA
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Steven D'Aprano]

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 implementation I use can be expected to fail
> > on average once every 18 thousand years if you did nothing but test
> > primes every millisecond of the day, 24 hours a day. That's good enough
> > for most purposes :-)
> 
> What about false negatives? Guaranteed none? The failure mode of the
> function should, IMO, be a defined and documented aspect of it.

If a non-deterministic primality tester such as (but not limited to) 
Miller-Rabin says a number is composite, it is definitely composite 
(ignoring bugs in the implementation, or hardware failures). If it says 
it is prime, in the worst case it is merely "probably prime", with an 
error rate proportional to 1/4**k where we can choose the k.

(The bigger the k the more work may be done in the worst case.)


-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Tim Peters]

[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", than even experienced Python programmers are likely to come up
with at first.

That gives it real value as a candidate for a standard library.  But
something much fancier than that?  I don't think so, for reasons already
given - the code is still understandable for non-experts if they give it
some effort.  Fancier stuff may not be.

For example, in my own code I use a fancier version of that incorporating a
wheel sieve too, and even the _setup_ function for that is harder to
understand all on its own:

def _setup_sieve(ps, show=True):
from math import gcd

assert ps[0] == 2
prod = totient = 1
for p in ps:
assert pp(p)
prod *= p
totient *= p-1
if show:
print("ps", ps, "prod", prod)
mod2i = [None] * prod
mod2i[1] = 0
deltas = []
last = 1
for i in range(3, prod, 2):
if gcd(prod, i) == 1:
deltas.append(i - last)
mod2i[i] = len(deltas)
last = i
deltas.append(2)# wrap around from prod-1 to 1
assert len(deltas) == totient
assert sum(deltas) == prod
if show:
print("deltas", deltas, len(deltas))
print("mod2i", mod2i)
return ps, deltas * 2, mod2i

_siv_glob = _setup_sieve([2, 3, 5, 7], show=False)

I don't want that in the standard library - and twice as much don't want it
if somebody else wrote  it ;-)
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

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.

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 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" a prime.
>
>
>> I'm more concerned in the space/time tradeoff in the primes() generator.
>> I like this implementation for teaching purposes, but I'm well aware that
>> it grows in memory usage rather quickly (the one Tim Peters posted is
>> probably a better balance; but it depends on how many of these you create
>> and how long you run them).
>>
>
> As you noted later:
>
> I take it back... Tim's (really Will Ness's) version is *always* faster
>> and more
>
> memory friendly.
>
>
> The original version of this came from an ActiveState recipe that many on
> c.l.py contributed to (including me) years ago, and that's where all the
> speed came from.  There is, for example, no division or square roots.
> Will's contribution was the unexpected way to slash memory use, via the
> generator calling itself recursively.  Elegant and effective!
>
>
>> I'm still trying to understand it though :-).
>
>
> Picture doing the Sieve of Eratosthenes by hand, crossing out multiples of
> "the next" prime you find.  That's basically what it's doing, except doing
> the "crossing out" part incrementally, using a dict to remember, for each
> prime p, "the next" multiple of p you haven't yet gotten to.
>
>
>
>> from math import sqrt, ceil
>>
>> def up_to(seq, lim):
>> for n in seq:
>> if n < lim:
>> yield n
>> else:
>> break
>>
>> def sieve_generator():
>> "Pretty good Sieve; skip the even numbers, stop at sqrt(candidate)"
>> yield 2
>> candidate = 3
>> found = []
>> while True:
>> lim = int(ceil(sqrt(candidate)))
>> if all(candidate % prime != 0 for prime in up_to(found, lim)):
>> yield candidate
>> found.append(candidate)
>> candidate += 2
>>
>>
>>
> Note that this generates squares of odd primes too (9, 25, ...).  `up_to`
> needs to be more like `up_to_and_including`.
>
>
>

-- 
Keeping medicines from the bloodstreams of the sick; food
from the bellies of the hungry; books from the hands of the
uneducated; technology from the underdeveloped; and putting
advocates of freedom in prisons.  Intellectual property is
to the 21st century what the slave trade was to the 16th.
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Tim Peters]

[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" a prime.


> I'm more concerned in the space/time tradeoff in the primes() generator. I
> like this implementation for teaching purposes, but I'm well aware that it
> grows in memory usage rather quickly (the one Tim Peters posted is probably
> a better balance; but it depends on how many of these you create and how
> long you run them).
>

As you noted later:

I take it back... Tim's (really Will Ness's) version is *always* faster and
> more

memory friendly.


The original version of this came from an ActiveState recipe that many on
c.l.py contributed to (including me) years ago, and that's where all the
speed came from.  There is, for example, no division or square roots.
Will's contribution was the unexpected way to slash memory use, via the
generator calling itself recursively.  Elegant and effective!


> I'm still trying to understand it though :-).


Picture doing the Sieve of Eratosthenes by hand, crossing out multiples of
"the next" prime you find.  That's basically what it's doing, except doing
the "crossing out" part incrementally, using a dict to remember, for each
prime p, "the next" multiple of p you haven't yet gotten to.



> from math import sqrt, ceil
>
> def up_to(seq, lim):
> for n in seq:
> if n < lim:
> yield n
> else:
> break
>
> def sieve_generator():
> "Pretty good Sieve; skip the even numbers, stop at sqrt(candidate)"
> yield 2
> candidate = 3
> found = []
> while True:
> lim = int(ceil(sqrt(candidate)))
> if all(candidate % prime != 0 for prime in up_to(found, lim)):
> yield candidate
> found.append(candidate)
> candidate += 2
>
>
>
Note that this generates squares of odd primes too (9, 25, ...).  `up_to`
needs to be more like `up_to_and_including`.
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[David Mertz]

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, 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 thousand years if you did nothing but test
>> > primes every millisecond of the day, 24 hours a day. That's good enough
>> > for most purposes :-)
>>
>> What about false negatives? Guaranteed none? The failure mode of the
>> function should, IMO, be a defined and documented aspect of it.
>>
>
> Miller-Rabin or other pseudo-primality tests do not produce false
> negatives IIUC.
>
> I'm more concerned in the space/time tradeoff in the primes() generator. I
> like this implementation for teaching purposes, but I'm well aware that it
> grows in memory usage rather quickly (the one Tim Peters posted is probably
> a better balance; but it depends on how many of these you create and how
> long you run them).
>
> from math import sqrt, ceil
>
> def up_to(seq, lim):
> for n in seq:
> if n < lim:
> yield n
> else:
> break
>
> def sieve_generator():
> "Pretty good Sieve; skip the even numbers, stop at sqrt(candidate)"
> yield 2
> candidate = 3
> found = []
> while True:
> lim = int(ceil(sqrt(candidate)))
> if all(candidate % prime != 0 for prime in up_to(found, lim)):
> yield candidate
> found.append(candidate)
> candidate += 2
>
>
> So then how do you implement isprime().  One naive way is to compare it
> against elements of sieve_generator() until we are equal or larger than the
> test element.  But that's not super fast.   A pseudo-primality test is much
> faster (except for in the first few hundred thousand primes, maybe).
>
> --
> Keeping medicines from the bloodstreams of the sick; food
> from the bellies of the hungry; books from the hands of the
> uneducated; technology from the underdeveloped; and putting
> advocates of freedom in prisons.  Intellectual property is
> to the 21st century what the slave trade was to the 16th.
>


-- 
Keeping medicines from the bloodstreams of the sick; food
from the bellies of the hungry; books from the hands of the
uneducated; technology from the underdeveloped; and putting
advocates of freedom in prisons.  Intellectual property is
to the 21st century what the slave trade was to the 16th.
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[David Mertz]

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 implementation I use can be expected to fail
> > on average once every 18 thousand years if you did nothing but test
> > primes every millisecond of the day, 24 hours a day. That's good enough
> > for most purposes :-)
>
> What about false negatives? Guaranteed none? The failure mode of the
> function should, IMO, be a defined and documented aspect of it.
>

Miller-Rabin or other pseudo-primality tests do not produce false negatives
IIUC.

I'm more concerned in the space/time tradeoff in the primes() generator. I
like this implementation for teaching purposes, but I'm well aware that it
grows in memory usage rather quickly (the one Tim Peters posted is probably
a better balance; but it depends on how many of these you create and how
long you run them).

from math import sqrt, ceil

def up_to(seq, lim):
for n in seq:
if n < lim:
yield n
else:
break

def sieve_generator():
"Pretty good Sieve; skip the even numbers, stop at sqrt(candidate)"
yield 2
candidate = 3
found = []
while True:
lim = int(ceil(sqrt(candidate)))
if all(candidate % prime != 0 for prime in up_to(found, lim)):
yield candidate
found.append(candidate)
candidate += 2


So then how do you implement isprime().  One naive way is to compare it
against elements of sieve_generator() until we are equal or larger than the
test element.  But that's not super fast.   A pseudo-primality test is much
faster (except for in the first few hundred thousand primes, maybe).

-- 
Keeping medicines from the bloodstreams of the sick; food
from the bellies of the hungry; books from the hands of the
uneducated; technology from the underdeveloped; and putting
advocates of freedom in prisons.  Intellectual property is
to the 21st century what the slave trade was to the 16th.
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Tim Peters]

]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
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/1939/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 ;-)
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Chris Angelico]

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 thousand years if you did nothing but test
> primes every millisecond of the day, 24 hours a day. That's good enough
> for most purposes :-)

What about false negatives? Guaranteed none? The failure mode of the
function should, IMO, be a defined and documented aspect of it.

ChrisA
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Steven D'Aprano]

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 clear to me that any choice is
> sufficiently "one size fits all" to include.

We're talking about "batteries included", not a nuclear reactor. (Thanks 
to Nick for that great analogy!)

This is a fairly narrow and deterministic set of requirements:

- test whether a number is prime;
- return some primes;

and maybe a couple of other related functions. Not a data structure, 
where we have to make serious tradeoffs in the type of values they 
support (hashable, orderable, or any arbitrary value, say) and what can 
be done with them. We already know what we have to support : ints, as 
large as will fit in memory.

While of course there are efficiency trade-offs, at the point you really 
care about them, you're in nuclear reactor territory and are probably 
using some library too specialised even for numpy *wink*

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 thousand years if you did nothing but test 
primes every millisecond of the day, 24 hours a day. That's good enough 
for most purposes :-)


> I'm not saying there definitely IS NOT a reasonable compromise approach to
> these things, but I'd have to judge concrete suggestions... Or better
> still, people with better knowledge of number theory than mine should make
> those judgements.

Miller-Rabin + trial division by the first few small primes is the 
work-horse of primality testing. There are "better, faster" algorithms, 
but they are more complex (more risk of bugs) and probably don't show 
any improvement until you're dealing with huge numbers. I mean *really* 
huge. My pure-Python version of Miller-Rabin takes:

about 4.7 seconds to test 2**800 + 1;
less than a tenth of a millisecond to test 2**900 + 1;
and about 8.6 seconds to test 2**1000 + 1.

(None of which are prime.) On a less old-and-tired computer, you can 
probably divide those numbers by, oh, five or ten.

You probably won't find any record-breaking Mersenne Primes using my 
version (certainly not on *my* computer), but I think it would be good 
enough for the standard library if we decided to add an isprime() 
function.

As far as generating primes, there's a lot more choices, but since they 
all do the same thing (generate prime numbers) we can easily swap one 
implementation for another and nobody will even know unless they're 
timing it.

*If* it is desirable to have this in the stdlib, we shouldn't be 
paralysed by implementation choice. We can start with something "good 
enough", and move to more complex implementations when and if somebody 
wants to do the work.



-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Steven D'Aprano]

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, but I said the opposite.

Oh, sorry, you were talking about round to even! I misunderstood.


-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[David Mertz]

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 problems, and quickly write something like:
>
> def primes(n):
>  return (i for i in range(2, n) if all(i % j for j in
> primes(int(sqrt(i)) + 1)))
>
> Having such feature in the stdlib would be very convenient. Any
> reasonable implementation is enough efficient for my purposes.
>

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 clear to me that any choice is
sufficiently "one size fits all" to include.

I'm not saying there definitely IS NOT a reasonable compromise approach to
these things, but I'd have to judge concrete suggestions... Or better
still, people with better knowledge of number theory than mine should make
those judgements.
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Serhiy Storchaka]

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.

___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Steven D'Aprano]

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.
> Divide and rounding up: (n+m-1)//m or -((-n)//m).

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?

I have this in my toolbox:

def ceildiv(a, b):
"""Return the ceiling of a/b."""
return -(-a//b)

and if its buggy, I've never noticed it yet.



-- 
Steve
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [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
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Serhiy Storchaka]

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 
primes. For the stdlib implementation we don't have such strong limit on 
the size.



Your divide_and_round might be nice, but there are multiple common
ways of rounding 0.5 (up, down, towards 0, away from 0, to even, to
odd, ...) Your implementation does round to even, but that's not
necessarily the obvious one (schools often teach round up or down, so
use of your implementation in education could be confusing).


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.
Divide and rounding up: (n+m-1)//m or -((-n)//m).

___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Paul Moore]

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 Primality test? For large
>> numbers, iterating through candidate prime divisors is pricey.
>>
>> * primes()
>> Returns an iterator of prime numbers: 2, 3, 5, 7, 11, 13,...
>>
>>
>> How would you implements this? Sieve of Eratosthenes is really fun to show
>> students as a Python generator function. But the cached primes DO grow
>> unboundedly as you utilize the generator. Wheel factorization as first pass?
>> Do you cached the first N primes so the each instance of iterator can
>> provide initial elements much faster? What is N?
>
>
> 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
> problems, and quickly write something like:
>
> def primes(n):
> return (i for i in range(2, n) if all(i % j for j in primes(int(sqrt(i))
> + 1)))
>
> Having such feature in the stdlib would be very convenient. Any reasonable
> implementation is enough efficient for my purposes.

Agreed, having these functions in the stdlib would be convenient, but
I think it's important that we have at least reasonably performing
implementations (they don't have to be suitable for specialist use,
but they should be performant enough for production, non-specialist
use). IMO, the statistics module got this balance right - good enough
for general use, but specialists will want something better.

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.

I'd be interested in the following (which is mostly a duplicate of your list)

* factorial
* gcd
* binom
* isprime (it's important to be clear if this is a guaranteed check,
or a probabilistic one like Miller Rabin)
* primes (an infinite generator of primes)
* factors (generates the prime factors of a number, in increasing
order, so list(factors(12)) = [2, 2, 3])

Your divide_and_round might be nice, but there are multiple common
ways of rounding 0.5 (up, down, towards 0, away from 0, to even, to
odd, ...) Your implementation does round to even, but that's not
necessarily the obvious one (schools often teach round up or down, so
use of your implementation in education could be confusing).

> Because cmath. But if most core developers prefer intmath, I have no 
> objections.

I prefer imath as a parallel with cmath, as you say. But it's not a
big deal to me.

Paul
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Serhiy Storchaka]

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 special purposed module is a better home for some math 
functions.
Because it is convenient to have these simple batteries included. Sage 
is too heavyweight.


The reasons are the same as for adding factorial() and gcd() in the math 
module. But after adding more such functions it is better to move them 
into the special module.


___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Serhiy Storchaka]

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 pricey.


* primes()
Returns an iterator of prime numbers: 2, 3, 5, 7, 11, 13,...


How would you implements this? Sieve of Eratosthenes is really fun to 
show students as a Python generator function. But the cached primes DO 
grow unboundedly as you utilize the generator. Wheel factorization as 
first pass? Do you cached the first N primes so the each instance of 
iterator can provide initial elements much faster? What is N?


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 problems, and quickly write something like:


def primes(n):
return (i for i in range(2, n) if all(i % j for j in 
primes(int(sqrt(i)) + 1)))


Having such feature in the stdlib would be very convenient. Any 
reasonable implementation is enough efficient for my purposes.


___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Robert Vanden Eynde]

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 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 > 0 else r < b
>  if greater_than_half or r == b and q % 2 == 1:
>  q += 1
>  return q
>
> (This is a copy of the implementation from datetime.py, there are yet
> few implementations in Python and C in other files.)
>
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Serhiy Storchaka]

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 > 0 else r < b
if greater_than_half or r == b and q % 2 == 1:
q += 1
return q

(This is a copy of the implementation from datetime.py, there are yet 
few implementations in Python and C in other files.)


___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Devin Jeanpierre]

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 this any different than float(x).as_integer_ratio() ==
(x.numerator, x.denominator) for ints/fractions?)

-- Devin
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Daniel Moisset]

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 imath module for integer
> mathematics? It could contain the following functions:
>
> * factorial(n)
>
> Is just moved from the math module, but non-integer types are rejected.
> Currently math.factorial() accepts also integer floats like 3.0. It looks
> to me, the rationale was that at the time when math.factorial() was added,
> all function in the math module worked with floats. But now we can revise
> this decision.
>
> * gcd(n, m)
>
> Is just moved from the math module.
>
> * as_integer_ration(x)
>
> Equivalents to:
>
> def as_integer_ration(x):
> if hasattr(x, 'as_integer_ration'):
> return x.as_integer_ration()
> else:
> return (x.numerator, x.denominator)
>
> * binom(n, k)
>
> Returns factorial(n) // (factorial(k) * factorial(n-k)), but uses more
> efficient algorithm.
>
> * sqrt(n)
>
> Returns the largest integer r such that r**2 <= n and (r+1)**2 > n.
>
> * isprime(n)
>
> Tests if n is a prime number.
>
> * primes()
>
> Returns an iterator of prime numbers: 2, 3, 5, 7, 11, 13,...
>
> Are there more ideas?
>
> ___
> Python-ideas mailing list
> Python-ideas@python.org
> https://mail.python.org/mailman/listinfo/python-ideas
> Code of Conduct: http://python.org/psf/codeofconduct/
>



-- 

Daniel Moisset
Technical Leader

A:   1 Fore St, EC2Y 9DT London 
P:   +44 7398 827139 <+44+7398+827139>
M:   dmois...@machinalis.com   |   S:   dmoisset

  

___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[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 pricey.

* primes()
> Returns an iterator of prime numbers: 2, 3, 5, 7, 11, 13,...
>

How would you implements this? Sieve of Eratosthenes is really fun to show
students as a Python generator function. But the cached primes DO grow
unboundedly as you utilize the generator. Wheel factorization as first
pass? Do you cached the first N primes so the each instance of iterator can
provide initial elements much faster? What is N?

>
___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/

Re: [Python-ideas] Add the imath module

[Jeroen Demeyer]

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: http://python.org/psf/codeofconduct/

[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:


* factorial(n)

Is just moved from the math module, but non-integer types are rejected. 
Currently math.factorial() accepts also integer floats like 3.0. It 
looks to me, the rationale was that at the time when math.factorial() 
was added, all function in the math module worked with floats. But now 
we can revise this decision.


* gcd(n, m)

Is just moved from the math module.

* as_integer_ration(x)

Equivalents to:

def as_integer_ration(x):
if hasattr(x, 'as_integer_ration'):
return x.as_integer_ration()
else:
return (x.numerator, x.denominator)

* binom(n, k)

Returns factorial(n) // (factorial(k) * factorial(n-k)), but uses more 
efficient algorithm.


* sqrt(n)

Returns the largest integer r such that r**2 <= n and (r+1)**2 > n.

* isprime(n)

Tests if n is a prime number.

* primes()

Returns an iterator of prime numbers: 2, 3, 5, 7, 11, 13,...

Are there more ideas?

___
Python-ideas mailing list
Python-ideas@python.org
https://mail.python.org/mailman/listinfo/python-ideas
Code of Conduct: http://python.org/psf/codeofconduct/