Opened 5 years ago

Closed 5 years ago

#17852 closed enhancement (fixed)

Cleanup in rings.arith and rings.integer

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.6
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Vincent Delecroix Reviewers: Jeroen Demeyer
Report Upstream: N/A Work issues:
Branch: d7e1e37 (Commits) Commit: d7e1e37f954184aa281d22c25ef9485e8b8f453c
Dependencies: #16878 Stopgaps:

Description (last modified by vdelecroix)

In this ticket, we:

  • implement the two functions prime_part_m and binomial directly as methods of Sage integers and get rid of the late_import in sage.rings.integer
  • simplify the import logic in rings.arith
  • replace in arith prod([x for x in hum]) by prod(x for x in hum)
  • remove some useless comments in arith
  • deprecate powermodm_ui
  • remove 1 from the output of prime_powers() (consistent with #16878)
  • remove the method lcm from Rational

Change History (101)

comment:1 Changed 5 years ago by vdelecroix

  • Branch set to u/vdelecroix/17852
  • Commit set to 613ae23a399c16a03032e78e5483eaf90c42af15
  • Status changed from new to needs_review

New commits:

613ae23trac #17852: cleanup arith.py and integer.pyx

comment:2 Changed 5 years ago by jdemeyer

Conflicts with #17819

comment:3 follow-up: Changed 5 years ago by jdemeyer

I suggest you revert all changes to Integer.divisors

comment:4 in reply to: ↑ 3 Changed 5 years ago by vdelecroix

Replying to jdemeyer:

I suggest you revert all changes to Integer.divisors

there is none...

EDIT: there are... I messed up my develop branch!

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:5 Changed 5 years ago by git

  • Commit changed from 613ae23a399c16a03032e78e5483eaf90c42af15 to 7dcce3a9040cbb609bbc00432386c1d1dcbed945

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

7dcce3atrac #17852: cleanup in arith.py and integer.pyx

comment:6 Changed 5 years ago by vdelecroix

No conflicts anymore...

comment:7 Changed 5 years ago by jdemeyer

  • Type changed from PLEASE CHANGE to enhancement

comment:8 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

I don't like this:

cdef mpz_t g = <mpz_t> mm.value

Just use mm.value instead of g.

comment:9 Changed 5 years ago by jdemeyer

isinstance(z, (Rational)) -> isinstance(z, Rational)

comment:10 follow-up: Changed 5 years ago by jdemeyer

What's the point of eratosthenes(), shouldn't that be a deprecated_function_alias of prime_range?

comment:11 Changed 5 years ago by jdemeyer

Remove this:

    TESTS::

        sage:

comment:12 Changed 5 years ago by jdemeyer

For is_squarefree, add an example where the .is_squarefree() method is not used, for example ZZ[sqrt(-1)].

comment:13 Changed 5 years ago by jdemeyer

if isinstance(x, Integer):
    return x.binomial(m, **kwds)

should be try/except AttributeError

comment:14 Changed 5 years ago by jdemeyer

Replace

try:
    P = x.parent()
except AttributeError:
    P = type(x)
if m < 0:
    return P(0)

by

if m < 0:
    return parent(x)(0)

comment:15 Changed 5 years ago by jdemeyer

And powermodm_ui should be a deprecated alias for powermod: what's the point of an optimized path for unsigned long in a Python function?

Then you can also remove

MAX_UNSIGNED_LONG = 2 * sys.maxsize

(which is wrong anyway!)

comment:16 Changed 5 years ago by jdemeyer

if not self:
    raise ValueError("self must be nonzero")

should be ArithmeticError instead.

comment:17 Changed 5 years ago by jdemeyer

The argument ``m`` or (``self-m``) must fits into unsigned long::

fits -> fit

comment:18 Changed 5 years ago by jdemeyer

I'm done for now :-)

comment:19 Changed 5 years ago by git

  • Commit changed from 7dcce3a9040cbb609bbc00432386c1d1dcbed945 to 975c2a0a6563538377eca78590fd16ddf0342548

Branch pushed to git repo; I updated commit sha1. New commits:

975c2a0trac #17852: reviewer comments

comment:20 in reply to: ↑ 10 Changed 5 years ago by vdelecroix

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Replying to jdemeyer:

What's the point of eratosthenes(), shouldn't that be a deprecated_function_alias of prime_range?

It is excplicitely written "for educational purpose"... I do not want to deprecate it so roughly.

I agreed with all of the other suggestions and implemented them.

Vincent

comment:21 Changed 5 years ago by git

  • Commit changed from 975c2a0a6563538377eca78590fd16ddf0342548 to ad7d25a752db23ee3cae1a7d7b9fb2bbc7569bba

Branch pushed to git repo; I updated commit sha1. New commits:

ad7d25atrac #17852: extra doctest in is_squarefree

comment:22 Changed 5 years ago by vbraun

  • Status changed from needs_review to needs_work

comment:23 Changed 5 years ago by vbraun

  • Status changed from needs_work to needs_review

just testing... didn't have a problem changing the status.

comment:24 Changed 5 years ago by jdemeyer

  • Dependencies set to #16878
  • Status changed from needs_review to needs_work

Needs to be rebased on #16878.

comment:25 Changed 5 years ago by git

  • Commit changed from ad7d25a752db23ee3cae1a7d7b9fb2bbc7569bba to c7916a76b70e698c278fa1780da16e7d96df2fe9

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ade4f75Upgrade PARI to git master
9751ee8Trac #16878: faster is_prime
96f1f50Trac #16878: further fixes to is_prime() and friends
1f8abd9Doctest fix
c7916a7trac #17852: clean-up

comment:26 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Rebased over #16878

comment:27 follow-up: Changed 5 years ago by chapoton

This looks dubious to me:

-    R = parent(n)
-    if R in [int, long]:
+    if isinstance(int, long):

comment:28 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

comment:29 in reply to: ↑ 27 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Replying to chapoton:

This looks dubious to me:

-    R = parent(n)
-    if R in [int, long]:
+    if isinstance(int, long):

EDIT: you are definitely right... see the commit below!

If an object n is not a Sage Element parent(n) returns the type of n.

sage: parent(3r)
<type 'int'>
sage: parent(Graph())
<class 'sage.graphs.graph.Graph'>

The code parent(n) in [int,long] is (roughly) equivalent to type(n) in [int,long]. I find much cleaner to use isinstance. If you do have a use case for which there is a difference, then please tell me.

Vincent

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:30 Changed 5 years ago by git

  • Commit changed from c7916a76b70e698c278fa1780da16e7d96df2fe9 to 03d78d330b2693223c8cff3975206b38752174e8

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

1b1293atrac #17852: clean-up
03d78d3trac #17852: fix an isinstance

comment:31 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

I get a doc builder error (but I closed my session, so I cannot copy the error message now)

comment:32 Changed 5 years ago by chapoton

please replace the first :: by : in

 TESTS::
+ Check that output are always Sage integers (:trac:`922`)::

comment:33 Changed 5 years ago by git

  • Commit changed from 03d78d330b2693223c8cff3975206b38752174e8 to 101f5a0feaf66f5f5e3a7cb0e4d706220ee3ff71

Branch pushed to git repo; I updated commit sha1. New commits:

101f5a0trac #17852: documentation

comment:34 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:35 Changed 5 years ago by jdemeyer

  • Description modified (diff)

comment:36 Changed 5 years ago by jdemeyer

Why did you remove many doctests of prime_powers()? In particular this test:

prime_powers(95,1234)

comment:37 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

In prime_powers, why do you only allow Integer, int and long? Why not

if not isinstance(start, Integer):
    start = Integer(start)

Then you don't need to raise TypeError explicitly, as Integer(start) will do that if needed.

Last edited 5 years ago by jdemeyer (previous) (diff)

comment:38 Changed 5 years ago by jdemeyer

Replace

if isinstance(x, (float, complex, RealNumber, RealLiteral, ComplexNumber))

by

if isinstance(x, (float, complex, RealNumber, ComplexNumber))

comment:39 follow-up: Changed 5 years ago by jdemeyer

Why

P(1) * x.binomial(m, **kwds)

and not

x.binomial(m, **kwds)

or

P(x.binomial(m, **kwds))

comment:40 Changed 5 years ago by jdemeyer

For the binomial function: the documentation mentions

Either ``m`` or ``x-m`` must be an integer.

but the code doesn't reflect this.

I think therefore you need

try:
    m = Integer(m)
except TypeError:
    m = Integer(x - m)

Also, a doctest should be added for this case.

Last edited 5 years ago by jdemeyer (previous) (diff)

comment:41 follow-up: Changed 5 years ago by jdemeyer

And the conversion of x to ZZ should be added after the PARI branch.

comment:42 follow-up: Changed 5 years ago by jdemeyer

sage -t --long src/sage/rings/integer.pyx
**********************************************************************
File "src/sage/rings/integer.pyx", line 6118, in sage.rings.integer.Integer.binomial
Failed example:
    alarm(0.1); (2**100).binomial(2**30, algorithm='pari')
Expected:
    Traceback (most recent call last):
    ...
    AlarmInterrupt
Got:
    <BLANKLINE>
    Traceback (most recent call last):
      File "/usr/local/src/sage-git/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 492, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/usr/local/src/sage-git/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 854, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.rings.integer.Integer.binomial[12]>", line 1, in <module>
        alarm(RealNumber('0.1')); (Integer(2)**Integer(100)).binomial(Integer(2)**Integer(30), algorithm='pari')
      File "sage/rings/integer.pyx", line 6154, in sage.rings.integer.Integer.binomial (build/cythonized/sage/rings/integer.c:36402)
        return the_integer_ring(self._pari_().binomial(mm))
      File "sage/libs/pari/gen.pyx", line 5379, in sage.libs.pari.gen.gen.binomial (build/cythonized/sage/libs/pari/gen.c:25503)
        pari_catch_sig_on()
      File "sage/libs/pari/handle_error.pyx", line 163, in sage.libs.pari.handle_error._pari_err_handle (build/cythonized/sage/libs/pari/handle_error.c:2656)
        pari_instance.allocatemem(silent=True)
      File "sage/libs/pari/pari_instance.pyx", line 1122, in sage.libs.pari.pari_instance.PariInstance.allocatemem (build/cythonized/sage/libs/pari/pari_instance.c:7709)
        init_stack(s)
      File "sage/libs/pari/pari_instance.pyx", line 1657, in sage.libs.pari.pari_instance.init_stack (build/cythonized/sage/libs/pari/pari_instance.c:11894)
        raise MemoryError("Unable to allocate %s bytes for the PARI stack (instead, allocated %s bytes)"%(failed_size, new_size))
    MemoryError: Unable to allocate 6400000000 bytes for the PARI stack (instead, allocated 5120000000 bytes)
**********************************************************************
1 item had failures:
   1 of  14 in sage.rings.integer.Integer.binomial
    [1031 tests, 1 failure, 10.74 s]
sage -t --long src/doc/en/developer/coding_basics.rst
**********************************************************************
File "src/doc/en/developer/coding_basics.rst", line 845, in doc.en.developer.coding_basics
Failed example:
    z.powermodm_ui(2^32-1, 14)
Expected:
    8                                                               
Got:
    doctest:1: DeprecationWarning: powermodm_ui is deprecated. Please use powermod instead.
    See http://trac.sagemath.org/17852 for details.
    8
**********************************************************************

comment:43 Changed 5 years ago by git

  • Commit changed from 101f5a0feaf66f5f5e3a7cb0e4d706220ee3ff71 to cbbb06fa27b0b9178ad3f9d0de3dc3235c5ec1c3

Branch pushed to git repo; I updated commit sha1. New commits:

ebddce8trac #17852: review
782b139trac #17852: fix alarm interrupt for binomial
b365b9etrac #17852: fix binomial(n,0) for negative n
faed0c0trac #17852: remove lcm on rationals (category takes care)
cbbb06ftrac #17852: make a reference to the symbolic binomial

comment:44 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:45 in reply to: ↑ 41 Changed 5 years ago by vdelecroix

Replying to jdemeyer:

And the conversion of x to ZZ should be added after the PARI branch.

Why?

comment:46 in reply to: ↑ 39 Changed 5 years ago by vdelecroix

Replying to jdemeyer:

Why

P(1) * x.binomial(m, **kwds)

and not

x.binomial(m, **kwds)

Done

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:47 in reply to: ↑ 42 ; follow-up: Changed 5 years ago by vdelecroix

Replying to jdemeyer:

sage -t --long src/sage/rings/integer.pyx
**********************************************************************
File "src/sage/rings/integer.pyx", line 6118, in sage.rings.integer.Integer.binomial
Failed example:
    alarm(0.1); (2**100).binomial(2**30, algorithm='pari')
...

For the doctest I put more reasonable values for which the call took 2 sec on my computer. I also decrease the alarm time to 0.01. Does this look better?

comment:48 follow-up: Changed 5 years ago by jdemeyer

I'm not sure that I like this:

sage: a = binomial(float(1001), float(1)); a
1001.0
sage: type(a)
<type 'sage.rings.real_double.RealDoubleElement'>

Shouldn't float input also give float output?

comment:49 in reply to: ↑ 47 ; follow-up: Changed 5 years ago by jdemeyer

Replying to vdelecroix:

For the doctest I put more reasonable values for which the call took 2 sec on my computer. I also decrease the alarm time to 0.01. Does this look better?

The problem wasn't time, the problem was memory. We should find input for which the call needs at most 2GB of memory.

comment:50 in reply to: ↑ 49 Changed 5 years ago by vdelecroix

Replying to jdemeyer:

Replying to vdelecroix:

For the doctest I put more reasonable values for which the call took 2 sec on my computer. I also decrease the alarm time to 0.01. Does this look better?

The problem wasn't time, the problem was memory. We should find input for which the call needs at most 2GB of memory.

I also changed the values to (2**100).binomial(2**19) (it is a number with 43223705 bits). At least on my computer, the RAM used stays below 2G.

comment:51 in reply to: ↑ 48 Changed 5 years ago by vdelecroix

  • Status changed from needs_review to needs_work

There is a test in doc/en/developer/coding_basics.rst that uses Integer.powermod_ui as an example for difference behavior for 32 bits and 64 bits. Do you have an other example in mind?

Replying to jdemeyer:

I'm not sure that I like this:

sage: a = binomial(float(1001), float(1)); a
1001.0
sage: type(a)
<type 'sage.rings.real_double.RealDoubleElement'>

Shouldn't float input also give float output?

Right. On the previous version we had

sage: type(binomial(5r,2r))
<type 'int'>
sage: type(binomial(5r,2))
<type 'sage.rings.integer.Integer'>
sage: type(binomial(5,2r))
<type 'sage.rings.integer.Integer'>

I will change that.

comment:52 Changed 5 years ago by vdelecroix

There was also no care of the output type for rational input

sage: type(binomial(5/1,3/1))
<type 'sage.rings.integer.Integer'>

(in sage-6.5)

comment:53 follow-up: Changed 5 years ago by jdemeyer

            sage: hash(-920390823904823094890238490238484)
            -873977844            # 32-bit
            6874330978542788722   # 64-bit

comment:54 in reply to: ↑ 53 Changed 5 years ago by vdelecroix

Replying to jdemeyer:

            sage: hash(-920390823904823094890238490238484)
            -873977844            # 32-bit
            6874330978542788722   # 64-bit

Thanks!

I also noticed that on large input pari is faster than mpir:

sage: %timeit a = (2**50).binomial(2**10, algorithm='mpir')
1000 loops, best of 3: 462 µs per loop
sage: %timeit a = (2**50).binomial(2**10, algorithm='pari')
1000 loops, best of 3: 221 µs per loop

and the difference is even more significant with larger numbers... I will had a note related to that.

Finally, I have troubles with the modification of the output type in arith.binomial (comment:48, comment:51 and comment:52). It is responsible for some doctest failure in rings/polynomial/multi_polynomial_ideal.py (the random generation stuff). I was not able to track down the issue.

comment:55 Changed 5 years ago by git

  • Commit changed from cbbb06fa27b0b9178ad3f9d0de3dc3235c5ec1c3 to d40126995abbc7dcb7e484b3d628a5196ea026d0

Branch pushed to git repo; I updated commit sha1. New commits:

1655367trac #17852: replace powermod_ui by hash in the doc
d401269trac #17852: fix output type of arith.binomial

comment:56 Changed 5 years ago by jdemeyer

Before doing coercion, what matters is the parent(), not the type() which should be equal.

comment:57 Changed 5 years ago by git

  • Commit changed from d40126995abbc7dcb7e484b3d628a5196ea026d0 to 8fc6b3da7c26d5ff4695991c26d67e38b3c1f103

Branch pushed to git repo; I updated commit sha1. New commits:

8fc6b3dtrac #17852: type -> parent

comment:58 Changed 5 years ago by vdelecroix

  • Description modified (diff)

comment:59 Changed 5 years ago by git

  • Commit changed from 8fc6b3da7c26d5ff4695991c26d67e38b3c1f103 to 61b94c202141bf164d87bae24912c687553b7869

Branch pushed to git repo; I updated commit sha1. New commits:

61b94c2trac #17852: fix curious failing doctest in multi_polynomial_ideal

comment:60 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

For the strange doctest failure responsible for commit ​61b94c2 see this sage-devel thread.

comment:61 follow-up: Changed 5 years ago by rws

I'm not sure if rings/arith.py:binomial should do more than numerics because the console user will first see functions/other.py:binomial and use that. The programmer OTOH probably won't need other than numerics. So, your efforts in rings/arith.py:binomial regarding other rings looks wasted to me.

There is already #17489 removing function duplicity for factorial so this is something to think of.

comment:62 in reply to: ↑ 61 Changed 5 years ago by vdelecroix

Replying to rws:

I'm not sure if rings/arith.py:binomial should do more than numerics because the console user will first see functions/other.py:binomial and use that. The programmer OTOH probably won't need other than numerics. So, your efforts in rings/arith.py:binomial regarding other rings looks wasted to me.

In the new version, arith.binomial do less than before regarding other rings (especially the symbolic one). What do you mean by numerics: integers? rationals? reals? complex? algebraic numbers?

There is already #17489 removing function duplicity for factorial so this is something to think of.

Removing binomial from arith is not an option. On top of #17852 we have

sage: from sage.rings.arith import binomial as arith_binomial
sage: %timeit arith_binomial(10,4)
100000 loops, best of 3: 1.87 µs per loop
sage: %timeit binomial(10,4)
10000 loops, best of 3: 47.3 µs per loop

The slowdown is less dramatic for factorial but still visible

sage: from sage.rings.arith import factorial as arith_factorial
sage: %timeit arith_factorial(10)
1000000 loops, best of 3: 474 ns per loop
sage: %timeit factorial(10)
1000000 loops, best of 3: 1.02 µs per loop

comment:63 Changed 5 years ago by git

  • Commit changed from 61b94c202141bf164d87bae24912c687553b7869 to 6697e686ab123c65b147e03c8df1b3969ea548fa

Branch pushed to git repo; I updated commit sha1. New commits:

6697e68trac #17852: be nicer on non-integral domains

comment:64 Changed 5 years ago by vdelecroix

An additional commit to take care of #12179.

comment:65 Changed 5 years ago by git

  • Commit changed from 6697e686ab123c65b147e03c8df1b3969ea548fa to 2260680a81f19b47202401109a7ec10f59e32d50

Branch pushed to git repo; I updated commit sha1. New commits:

2260680trac #17852: merge beta-6.6

comment:66 Changed 5 years ago by vdelecroix

All test pass on 6.6-beta6!

Vincent

Last edited 5 years ago by vdelecroix (previous) (diff)

comment:67 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

Comment 36 hasn't been addressed.

comment:68 Changed 5 years ago by git

  • Commit changed from 2260680a81f19b47202401109a7ec10f59e32d50 to 7f9847fb45b5fe5601a909155371c5ee024d19db

Branch pushed to git repo; I updated commit sha1. New commits:

7f9847ftrac #17852: documentation of prime_powers

comment:69 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:70 Changed 5 years ago by jdemeyer

Now this test is duplicated:

sage: len(prime_powers(1000))

comment:71 Changed 5 years ago by git

  • Commit changed from 7f9847fb45b5fe5601a909155371c5ee024d19db to faf206825e26344ae20fbe41363b00ba4e301c07

Branch pushed to git repo; I updated commit sha1. New commits:

faf2068trac #17852: removed duplicate doctest

comment:72 Changed 5 years ago by jdemeyer

Sorry but I still don't like the binomial code.

In particular, do we really need the coercion there? The arguments x and m play a very different role, note that m is immediately converted to an integer anyway.

Also, the check that factorial(m) is invertible has no mathematical meaning and should just be removed.

I will continue my review of the rest of this branch, please do not change anything except binomial.

comment:73 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

comment:74 Changed 5 years ago by jdemeyer

Not your fault, but should be fixed anyway: the error message of integer_ceil has

raise NotImplementedError("computation of floor of %s not implemented"%repr(x))

comment:75 Changed 5 years ago by jdemeyer

Replace

sage: alarm(0.01); (2**100).binomial(2**19, algorithm='pari')

by

sage: alarm(0.5); (2^100).binomial(2^22, algorithm='pari')

(analogously for mpir)

With this value, the memory use is reasonable and the computation takes long enough (48s on my machine) that it will not answer in <0.5s in the near future.

comment:76 Changed 5 years ago by jdemeyer

No further comments: if you fix the above without introducing new bugs :-) then it will finally be positive_review.

comment:77 Changed 5 years ago by jdemeyer

  • Reviewers set to Jeroen Demeyer

comment:78 follow-ups: Changed 5 years ago by vdelecroix

Replying to jdemeyer:

Sorry but I still don't like the binomial code.

In particular, do we really need the coercion there? The arguments x and m play a very different role, note that m is immediately converted to an integer anyway.

I am not sure I understand. You don't want the case 2 that tries to convert x to an integer? It is much faster that way for real or rational input that are actually integers.

Also, the check that factorial(m) is invertible has no mathematical meaning and should just be removed.

I am not sure that what I did in the branch is the best, but there is definitely something that needs to be specified (see #12179). Would you be satisfied with

sage: factorial(Zmod(12)(10), 4)
3

comment:79 in reply to: ↑ 78 ; follow-up: Changed 5 years ago by vdelecroix

Replying to vdelecroix:

Replying to jdemeyer:

Sorry but I still don't like the binomial code.

In particular, do we really need the coercion there? The arguments x and m play a very different role, note that m is immediately converted to an integer anyway.

I am not sure I understand. You don't want the case 2 that tries to convert x to an integer? It is much faster that way for real or rational input that are actually integers.

Also, the check that factorial(m) is invertible has no mathematical meaning and should just be removed.

I am not sure that what I did in the branch is the best, but there is definitely something that needs to be specified (see #12179). Would you be satisfied with

sage: factorial(Zmod(12)(10), 4)
3

Actually, it does matter. When an operation on a given quotient ring is implemented from the initial ring, you expect it to not depend on the representative you used... but

sage: R = Integers(6)
sage: R(binomial(5,2))
4
sage: R(binomial(5+6,2))
1

Note that it would have been fine on quotients in which 2! is invertible.

comment:80 in reply to: ↑ 78 Changed 5 years ago by jdemeyer

Replying to vdelecroix:

Replying to jdemeyer:

Sorry but I still don't like the binomial code.

In particular, do we really need the coercion there? The arguments x and m play a very different role, note that m is immediately converted to an integer anyway.

I am not sure I understand.

I mean this:

    if parent(m) is not P:
        from sage.structure.element import get_coercion_model
        cm = get_coercion_model()
        x,m = cm.canonical_coercion(x,m)
        P = parent(x)

comment:81 in reply to: ↑ 79 Changed 5 years ago by jdemeyer

Replying to vdelecroix:

Actually, it does matter. When an operation on a given quotient ring is implemented from the initial ring, you expect it to not depend on the representative you used... but

sage: R = Integers(6)
sage: R(binomial(5,2))
4
sage: R(binomial(5+6,2))
1

Note that it would have been fine on quotients in which 2! is invertible.

Of course, you are right. Never mind what I said about this.

comment:82 Changed 5 years ago by git

  • Commit changed from faf206825e26344ae20fbe41363b00ba4e301c07 to d70e2e8254b0da61792f6ddc4db8d430e4684bf0

Branch pushed to git repo; I updated commit sha1. New commits:

d70e2e8Trac 17852: reviewer comments

comment:83 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:84 Changed 5 years ago by git

  • Commit changed from d70e2e8254b0da61792f6ddc4db8d430e4684bf0 to 4f0ca87b9f64858a22f3fcd23b63526ba7622f55

Branch pushed to git repo; I updated commit sha1. New commits:

4f0ca87Trac 17852: fix an error in combinat/subword.py

comment:85 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

I thought a bit more about the invertibility check: in fact it has nothing to do with integral domains, but with the characteristic of the ring.

This is also not well-defined, despite R being a field:

sage: R = Zmod(7)
sage: binomial(R(10), 7)
1
sage: R(binomial(17, 7))
2

The correct condition is that factorial(m) should be coprime to the characteristic of the ring. So the code should be something like

try:
    c = P.characteristic()
except AttributeError:
    # Assume that P has characteristic zero
    pass
else:
    if c > 0 and any(c.gcd(k) > 1 for k in range(2, m+1)):
        raise ...

(you don't need Q for this)

The example with Zmod(7) should be added as doctest.

Last edited 5 years ago by jdemeyer (previous) (diff)

comment:86 Changed 5 years ago by git

  • Commit changed from 4f0ca87b9f64858a22f3fcd23b63526ba7622f55 to e24a437155ef6a95b6e413fd5717985fc05a48a1

Branch pushed to git repo; I updated commit sha1. New commits:

e24a437Trac 17852: binomial, hadling finite characteristic

comment:87 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to needs_review

comment:88 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to positive_review
  • Summary changed from Small cleanup in rings.arith and rings.integer to Cleanup in rings.arith and rings.integer

comment:89 Changed 5 years ago by vdelecroix

Indeed, it is not small anymore... thanks!

Vincent

comment:90 follow-ups: Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work

On 32-bit:

sage -t --long src/sage/combinat/baxter_permutations.py
**********************************************************************
File "src/sage/combinat/baxter_permutations.py", line 232, in sage.combinat.baxter_permutations.BaxterPermutations_size.cardinality
Failed example:
    [BaxterPermutations(n).cardinality() for n in xrange(13)]
Expected:
    [1, 1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560]
Got:
    [1, 1, 2, 6, 22, 92, 422, 2074, 10754, 58202, 326240, 1882960, 11140560L]
**********************************************************************
1 item had failures:
   1 of   2 in sage.combinat.baxter_permutations.BaxterPermutations_size.cardinality
    [31 tests, 1 failure, 1.41 s]

Really, cardinality should always return Sage integers.

comment:91 Changed 5 years ago by git

  • Commit changed from e24a437155ef6a95b6e413fd5717985fc05a48a1 to 4f4cdad1ae7953971c1e21993f26ece509034377

Branch pushed to git repo; I updated commit sha1. New commits:

4f4cdadTrac 17852: fix BaxterPermutations cardinality

comment:92 in reply to: ↑ 90 Changed 5 years ago by vdelecroix

Replying to vbraun:

On 32-bit:

...

Fixed.

Really, cardinality should always return Sage integers.

Then we are not to blame here ;-)

sage: parent(BaxterPermutations(3).cardinality())
Rational Field

Vincent

comment:93 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to positive_review

comment:94 in reply to: ↑ 90 Changed 5 years ago by vdelecroix

Replying to vbraun:

Really, cardinality should always return Sage integers.

See #18159

Vincent

comment:95 Changed 5 years ago by vbraun

  • Status changed from positive_review to needs_work
sage -t --long --warn-long 48.0 src/sage/rings/arith.py
**********************************************************************
File "src/sage/rings/arith.py", line 2608, in sage.rings.arith.is_squarefree
Failed example:
    is_squarefree(a - 3)
Expected:
    Traceback (most recent call last):
    ...
    ValueError: Non-principal ideal in factorization
Got:
    <BLANKLINE>
    Traceback (most recent call last):
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 496, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 858, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.rings.arith.is_squarefree[13]>", line 1, in <module>
        is_squarefree(a - Integer(3))
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/rings/arith.py", line 2623, in is_squarefree
        return all(r[1] == 1 for r in factor(n))
      File "/mnt/disk/home/release/Sage/local/lib/python2.7/site-packages/sage/rings/arith.py", line 2391, in factor
        return n.factor(**kwds)
      File "sage/rings/number_field/number_field_element.pyx", line 1485, in sage.rings.number_field.number_field_element.NumberFieldElement.factor (build/cythonized/sage/rings/number_field/number_field_element.cpp:15877)
        raise ArithmeticError("non-principal ideal in factorization")
    ArithmeticError: non-principal ideal in factorization

comment:96 Changed 5 years ago by vdelecroix

Volker, I do not get this error. Did you test on top of 6.6.rc2 or 6.6.rc3?

Vincent

comment:97 Changed 5 years ago by vdelecroix

This comes from #17294, not from this ticket!!

comment:98 Changed 5 years ago by vbraun

Well life is tough :-P

comment:99 Changed 5 years ago by git

  • Commit changed from 4f4cdad1ae7953971c1e21993f26ece509034377 to d7e1e37f954184aa281d22c25ef9485e8b8f453c

Branch pushed to git repo; I updated commit sha1. New commits:

33a8024Trac 17852: merge 6.7.beta0
d7e1e37Trac 17852: fix a failing doctest

comment:100 Changed 5 years ago by vdelecroix

  • Status changed from needs_work to positive_review

All test pass.

comment:101 Changed 5 years ago by vbraun

  • Branch changed from u/vdelecroix/17852 to d7e1e37f954184aa281d22c25ef9485e8b8f453c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.