[Python-ideas] Re: Add the imath module

[Chris Angelico]

On Mon, Mar 23, 2020 at 5:13 AM Neil Girdhar  wrote:
>
> I mean:
>
> def binom(n, *ks):
> # Check that there is at least one ki, and that their sum is less than n, 
> and that they are all nonnegative.
> # Returns n! / (prod(ki! for ki in ks) * (n-sum(ks))!)
>
> This would still work for binom(n, k), but would also work for the mulinomial 
> case.
>

Thanks for pulling this up again. I actually would have very much
liked to have an efficient and accurate binom(n,k) function available
- everything I could find was either floating-point (with the
limitations thereof) or too inefficient to be used for ridiculously
large values of n and/or k.

+1 on moving forward with adding an imath module.

ChrisA
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at 
https://mail.python.org/archives/list/python-ideas@python.org/message/2LGYCYCDZGGZKMFAWBKBS2NWGDIRPAIJ/
Code of Conduct: http://python.org/psf/codeofconduct/

[Python-ideas] Re: Add the imath module

[Neil Girdhar]

I mean:

def binom(n, *ks):
# Check that there is at least one ki, and that their sum is less than 
n, and that they are all nonnegative.
# Returns n! / (prod(ki! for ki in ks) * (n-sum(ks))!)

This would still work for binom(n, k), but would also work for the 
mulinomial case.

On Sunday, March 22, 2020 at 2:01:18 PM UTC-4, Neil Girdhar wrote:
>
> I really like this idea.  It fixes the weirdness whereby cmath is for 
> complex numbers, and math is for real numbers and integers.  I like 
> separating them into three categories.
>
> One suggestion: Consider generalizing binom to the multinomial coefficent.
>
> def binom(n, *ks):
> # Returns n! / prod(ki! for ki in ks)
>
> Best,
>
> Neil 
>
> On Thursday, July 12, 2018 at 7:57:08 AM UTC-4, 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...@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
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at 
https://mail.python.org/archives/list/python-ideas@python.org/message/AB6FYCQ6B3BKMJRV5C7BOPIVGON3MWTQ/
Code of Conduct: http://python.org/psf/codeofconduct/

[Python-ideas] Re: Add the imath module

[Neil Girdhar]

I really like this idea.  It fixes the weirdness whereby cmath is for 
complex numbers, and math is for real numbers and integers.  I like 
separating them into three categories.

One suggestion: Consider generalizing binom to the multinomial coefficent.

def binom(n, *ks):
# Returns n! / prod(ki! for ki in ks)

Best,

Neil 

On Thursday, July 12, 2018 at 7:57:08 AM UTC-4, 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...@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
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at 
https://mail.python.org/archives/list/python-ideas@python.org/message/NTSXZQAIC2OLSA2K4HP5N7HSFUNW7ZYF/
Code of Conduct: http://python.org/psf/codeofconduct/

[Python-ideas] Re: Add the imath module

[Steven D'Aprano]

On Sat, Mar 21, 2020 at 04:18:32PM +, Jonathan Fine wrote:
> Hi
> 
> In https://bugs.python.org/issue40028 ,
> Ross Rhodes suggested adding to the standard library a function that finds
> the prime factors of a non-negative integer. So far as I know, any general
> algorithm for doing this requires a list of prime numbers.

No, that's incorrect. Having a precomputed list of prime numbers is 
impractical for heavy-duty factorization of even moderately largish 
numbers, let alone genuinely large numbers, although trial division by 
the first few primes is often useful to eliminate the easy cases.

But trying to hold onto a table of millions of primes is wasteful and 
most importantly unnecessary. Primes can be cheaply generated on the 
fly, as needed, and probably faster than they can be read off a hard 
drive:

https://primes.utm.edu/notes/faq/LongestList.html

There are 16,352,460,426,841,680,446,427,399 primes below `10**27`

https://oeis.org/A006880

so even if we used a table of compact 32-bit integers, rather than int 
objects, that would take over 50 thousand million petabytes of storage 
if my calculations are correct. There may be more compact ways to store 
it, but I doubt you could get it under a few million petabytes.

And 10**27 is not an especially large number. It has only 27 digits. 
`(2*17*31*101*157*199)**100` has over 900 digits, and sympy can 
factorise it effectively instantly, without needing to pre-compute a 
multiple petabyte table of primes :-)

(In fairness, I did kinda cheat by generating a number I knew was easily 
factorisable. Working on an arbitrary 900+ digit number isn't so fast.)


[...]
> > Consider
> > >>> 2**32
> > 4294967296

> > And if someone needs to find primes of this size, they've
> > probably got a spare gigabyte or two.

For what it's worth, I just found the above prime factorization on a 
computer with 145 MB available in my home directory. (I *really* need a 
new computer.)

In your research, you may consider 2**32 to be a large number, but to 
people working with primes (for fun, or for research), it's tiny. 
Thousands of digits is getting large; the largest known prime, as of 
January 2020, has over 24 million digits.


-- 
Steven
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at 
https://mail.python.org/archives/list/python-ideas@python.org/message/RJ5XESEZ7K6BUBE4WXBM5JTHWWIOSP2G/
Code of Conduct: http://python.org/psf/codeofconduct/

[Python-ideas] Re: Add the imath module

[Jonathan Fine]

Hi

In https://bugs.python.org/issue40028 ,
Ross Rhodes suggested adding to the standard library a function that finds
the prime factors of a non-negative integer. So far as I know, any general
algorithm for doing this requires a list of prime numbers.

To this issue I've just added
https://bugs.python.org/issue40028?#msg364757 which
reads:

A pre-computed table of primes might be better. Of course, how long should
> the table be. There's an infinity of primes.
>


> Consider
> >>> 2**32
> 4294967296
>


> This number is approximately 4 * (10**9). According to
> https://en.wikipedia.org/wiki/Prime_number_theorem, there are 50,847,534
> primes less than 10**9. So, very roughly, there are 200,000,000 primes less
> than 2**32.
>


> Thus, storing a list of all these prime numbers as 32 bit unsigned
> integers would occupy about
> >>> 200_000_000 / (1024**3) * 4
> 0.7450580596923828
> or in other words 3/4 gigabytes on disk.
>


> A binary search into this list, using as starting point the expected
> location provided by the prime number theorem, might very well require on
> average less than two block reads into the file that holds the prime number
> list on disk. And if someone needs to find primes of this size, they've
> probably got a spare gigabyte or two.
>


> I'm naturally inclined to this approach because by mathematical research
> involves spending gigahertz days computing tables. I then use the tables to
> examine hypotheses. See https://arxiv.org/abs/1011.4269. This involves
> subsets of the vertices of the 5-dimensional cube. There are of course
> 2**32 such subsets.


-- 
Jonathan
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at 
https://mail.python.org/archives/list/python-ideas@python.org/message/SU5EIJ2O3OGPXHZMJ27G5JXSL2KMSAZ5/
Code of Conduct: http://python.org/psf/codeofconduct/

[Python-ideas] Re: Add the imath module

[Ross]

Hello Serhiy,

I support this proposal, thanks for sharing this thread in my enhancement 
proposal (issue #40028). I would be more than happy to help you where time 
permits in implementing this module if approval is granted.

Ross
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at 
https://mail.python.org/archives/list/python-ideas@python.org/message/FGED4WMHJBUIXX3OL2OLUEGKYHWWYSDH/
Code of Conduct: http://python.org/psf/codeofconduct/

[Python-ideas] Re: Add the imath module

[Ross]

I support this proposal. This would fit nicely with my recent enhancement 
proposal raised to introduce a method for finding prime factors of non-negative 
integer n.
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at 
https://mail.python.org/archives/list/python-ideas@python.org/message/7DIOJ7XJZ3XQTC7S3J5TL5GCXU4SL7X4/
Code of Conduct: http://python.org/psf/codeofconduct/