Opened 8 years ago

Closed 8 years ago

#17852 closed enhancement (fixed)

Cleanup in rings.arith and rings.integer

Reported by: Vincent Delecroix 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, GitHub, GitLab) Commit: d7e1e37f954184aa281d22c25ef9485e8b8f453c
Dependencies: #16878 Stopgaps:

Status badges

Description (last modified by Vincent Delecroix)

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 8 years ago by Vincent Delecroix

Branch: u/vdelecroix/17852
Commit: 613ae23a399c16a03032e78e5483eaf90c42af15
Status: newneeds_review

New commits:

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

comment:2 Changed 8 years ago by Jeroen Demeyer

Conflicts with #17819

comment:3 Changed 8 years ago by Jeroen Demeyer

I suggest you revert all changes to Integer.divisors

comment:4 in reply to:  3 Changed 8 years ago by Vincent Delecroix

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 8 years ago by Vincent Delecroix (previous) (diff)

comment:5 Changed 8 years ago by git

Commit: 613ae23a399c16a03032e78e5483eaf90c42af157dcce3a9040cbb609bbc00432386c1d1dcbed945

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 8 years ago by Vincent Delecroix

No conflicts anymore...

comment:7 Changed 8 years ago by Jeroen Demeyer

Type: PLEASE CHANGEenhancement

comment:8 Changed 8 years ago by Jeroen Demeyer

Status: needs_reviewneeds_work

I don't like this:

cdef mpz_t g = <mpz_t> mm.value

Just use mm.value instead of g.

comment:9 Changed 8 years ago by Jeroen Demeyer

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

comment:10 Changed 8 years ago by Jeroen Demeyer

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

comment:11 Changed 8 years ago by Jeroen Demeyer

Remove this:

    TESTS::

        sage:

comment:12 Changed 8 years ago by Jeroen Demeyer

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

comment:13 Changed 8 years ago by Jeroen Demeyer

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

should be try/except AttributeError

comment:14 Changed 8 years ago by Jeroen Demeyer

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 8 years ago by Jeroen Demeyer

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 8 years ago by Jeroen Demeyer

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

should be ArithmeticError instead.

comment:17 Changed 8 years ago by Jeroen Demeyer

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

fits -> fit

comment:18 Changed 8 years ago by Jeroen Demeyer

I'm done for now :-)

comment:19 Changed 8 years ago by git

Commit: 7dcce3a9040cbb609bbc00432386c1d1dcbed945975c2a0a6563538377eca78590fd16ddf0342548

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

975c2a0trac #17852: reviewer comments

comment:20 in reply to:  10 Changed 8 years ago by Vincent Delecroix

Description: modified (diff)
Status: needs_workneeds_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 8 years ago by git

Commit: 975c2a0a6563538377eca78590fd16ddf0342548ad7d25a752db23ee3cae1a7d7b9fb2bbc7569bba

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

ad7d25atrac #17852: extra doctest in is_squarefree

comment:22 Changed 8 years ago by Volker Braun

Status: needs_reviewneeds_work

comment:23 Changed 8 years ago by Volker Braun

Status: needs_workneeds_review

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

comment:24 Changed 8 years ago by Jeroen Demeyer

Dependencies: #16878
Status: needs_reviewneeds_work

Needs to be rebased on #16878.

comment:25 Changed 8 years ago by git

Commit: ad7d25a752db23ee3cae1a7d7b9fb2bbc7569bbac7916a76b70e698c278fa1780da16e7d96df2fe9

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 8 years ago by Vincent Delecroix

Status: needs_workneeds_review

Rebased over #16878

comment:27 Changed 8 years ago by Frédéric Chapoton

This looks dubious to me:

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

comment:28 Changed 8 years ago by Jeroen Demeyer

Status: needs_reviewneeds_work

comment:29 in reply to:  27 Changed 8 years ago by Vincent Delecroix

Status: needs_workneeds_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 8 years ago by Vincent Delecroix (previous) (diff)

comment:30 Changed 8 years ago by git

Commit: c7916a76b70e698c278fa1780da16e7d96df2fe903d78d330b2693223c8cff3975206b38752174e8

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 8 years ago by Jeroen Demeyer

Status: needs_reviewneeds_work

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

comment:32 Changed 8 years ago by Frédéric Chapoton

please replace the first :: by : in

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

comment:33 Changed 8 years ago by git

Commit: 03d78d330b2693223c8cff3975206b38752174e8101f5a0feaf66f5f5e3a7cb0e4d706220ee3ff71

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

101f5a0trac #17852: documentation

comment:34 Changed 8 years ago by Vincent Delecroix

Status: needs_workneeds_review

comment:35 Changed 8 years ago by Jeroen Demeyer

Description: modified (diff)

comment:36 Changed 8 years ago by Jeroen Demeyer

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

prime_powers(95,1234)

comment:37 Changed 8 years ago by Jeroen Demeyer

Status: needs_reviewneeds_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 8 years ago by Jeroen Demeyer (previous) (diff)

comment:38 Changed 8 years ago by Jeroen Demeyer

Replace

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

by

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

comment:39 Changed 8 years ago by Jeroen Demeyer

Why

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

and not

x.binomial(m, **kwds)

or

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

comment:40 Changed 8 years ago by Jeroen Demeyer

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 8 years ago by Jeroen Demeyer (previous) (diff)

comment:41 Changed 8 years ago by Jeroen Demeyer

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

comment:42 Changed 8 years ago by Jeroen Demeyer

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 8 years ago by git

Commit: 101f5a0feaf66f5f5e3a7cb0e4d706220ee3ff71cbbb06fa27b0b9178ad3f9d0de3dc3235c5ec1c3

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 8 years ago by Vincent Delecroix

Status: needs_workneeds_review

comment:45 in reply to:  41 Changed 8 years ago by Vincent Delecroix

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 8 years ago by Vincent Delecroix

Replying to jdemeyer:

Why

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

and not

x.binomial(m, **kwds)

Done

Last edited 8 years ago by Vincent Delecroix (previous) (diff)

comment:47 in reply to:  42 ; Changed 8 years ago by Vincent Delecroix

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 Changed 8 years ago by Jeroen Demeyer

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 ; Changed 8 years ago by Jeroen Demeyer

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 8 years ago by Vincent Delecroix

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 8 years ago by Vincent Delecroix

Status: needs_reviewneeds_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 8 years ago by Vincent Delecroix

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 Changed 8 years ago by Jeroen Demeyer

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

comment:54 in reply to:  53 Changed 8 years ago by Vincent Delecroix

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 8 years ago by git

Commit: cbbb06fa27b0b9178ad3f9d0de3dc3235c5ec1c3d40126995abbc7dcb7e484b3d628a5196ea026d0

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 8 years ago by Jeroen Demeyer

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

comment:57 Changed 8 years ago by git

Commit: d40126995abbc7dcb7e484b3d628a5196ea026d08fc6b3da7c26d5ff4695991c26d67e38b3c1f103

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

8fc6b3dtrac #17852: type -> parent

comment:58 Changed 8 years ago by Vincent Delecroix

Description: modified (diff)

comment:59 Changed 8 years ago by git

Commit: 8fc6b3da7c26d5ff4695991c26d67e38b3c1f10361b94c202141bf164d87bae24912c687553b7869

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

61b94c2trac #17852: fix curious failing doctest in multi_polynomial_ideal

comment:60 Changed 8 years ago by Vincent Delecroix

Status: needs_workneeds_review

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

comment:61 Changed 8 years ago by Ralf Stephan

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 8 years ago by Vincent Delecroix

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 8 years ago by git

Commit: 61b94c202141bf164d87bae24912c687553b78696697e686ab123c65b147e03c8df1b3969ea548fa

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

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

comment:64 Changed 8 years ago by Vincent Delecroix

An additional commit to take care of #12179.

comment:65 Changed 8 years ago by git

Commit: 6697e686ab123c65b147e03c8df1b3969ea548fa2260680a81f19b47202401109a7ec10f59e32d50

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

2260680trac #17852: merge beta-6.6

comment:66 Changed 8 years ago by Vincent Delecroix

All test pass on 6.6-beta6!

Vincent

Last edited 8 years ago by Vincent Delecroix (previous) (diff)

comment:67 Changed 8 years ago by Jeroen Demeyer

Status: needs_reviewneeds_work

Comment 36 hasn't been addressed.

comment:68 Changed 8 years ago by git

Commit: 2260680a81f19b47202401109a7ec10f59e32d507f9847fb45b5fe5601a909155371c5ee024d19db

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

7f9847ftrac #17852: documentation of prime_powers

comment:69 Changed 8 years ago by Vincent Delecroix

Status: needs_workneeds_review

comment:70 Changed 8 years ago by Jeroen Demeyer

Now this test is duplicated:

sage: len(prime_powers(1000))

comment:71 Changed 8 years ago by git

Commit: 7f9847fb45b5fe5601a909155371c5ee024d19dbfaf206825e26344ae20fbe41363b00ba4e301c07

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

faf2068trac #17852: removed duplicate doctest

comment:72 Changed 8 years ago by Jeroen Demeyer

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 8 years ago by Jeroen Demeyer

Status: needs_reviewneeds_work

comment:74 Changed 8 years ago by Jeroen Demeyer

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 8 years ago by Jeroen Demeyer

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 8 years ago by Jeroen Demeyer

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

comment:77 Changed 8 years ago by Jeroen Demeyer

Reviewers: Jeroen Demeyer

comment:78 Changed 8 years ago by Vincent Delecroix

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 ; Changed 8 years ago by Vincent Delecroix

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 8 years ago by Jeroen Demeyer

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 8 years ago by Jeroen Demeyer

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 8 years ago by git

Commit: faf206825e26344ae20fbe41363b00ba4e301c07d70e2e8254b0da61792f6ddc4db8d430e4684bf0

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

d70e2e8Trac 17852: reviewer comments

comment:83 Changed 8 years ago by Vincent Delecroix

Status: needs_workneeds_review

comment:84 Changed 8 years ago by git

Commit: d70e2e8254b0da61792f6ddc4db8d430e4684bf04f0ca87b9f64858a22f3fcd23b63526ba7622f55

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

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

comment:85 Changed 8 years ago by Jeroen Demeyer

Status: needs_reviewneeds_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 8 years ago by Jeroen Demeyer (previous) (diff)

comment:86 Changed 8 years ago by git

Commit: 4f0ca87b9f64858a22f3fcd23b63526ba7622f55e24a437155ef6a95b6e413fd5717985fc05a48a1

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

e24a437Trac 17852: binomial, hadling finite characteristic

comment:87 Changed 8 years ago by Vincent Delecroix

Status: needs_workneeds_review

comment:88 Changed 8 years ago by Jeroen Demeyer

Status: needs_reviewpositive_review
Summary: Small cleanup in rings.arith and rings.integerCleanup in rings.arith and rings.integer

comment:89 Changed 8 years ago by Vincent Delecroix

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

Vincent

comment:90 Changed 8 years ago by Volker Braun

Status: positive_reviewneeds_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 8 years ago by git

Commit: e24a437155ef6a95b6e413fd5717985fc05a48a14f4cdad1ae7953971c1e21993f26ece509034377

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

4f4cdadTrac 17852: fix BaxterPermutations cardinality

comment:92 in reply to:  90 Changed 8 years ago by Vincent Delecroix

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 8 years ago by Vincent Delecroix

Status: needs_workpositive_review

comment:94 in reply to:  90 Changed 8 years ago by Vincent Delecroix

Replying to vbraun:

Really, cardinality should always return Sage integers.

See #18159

Vincent

comment:95 Changed 8 years ago by Volker Braun

Status: positive_reviewneeds_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 8 years ago by Vincent Delecroix

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

Vincent

comment:97 Changed 8 years ago by Vincent Delecroix

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

comment:98 Changed 8 years ago by Volker Braun

Well life is tough :-P

comment:99 Changed 8 years ago by git

Commit: 4f4cdad1ae7953971c1e21993f26ece509034377d7e1e37f954184aa281d22c25ef9485e8b8f453c

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 8 years ago by Vincent Delecroix

Status: needs_workpositive_review

All test pass.

comment:101 Changed 8 years ago by Volker Braun

Branch: u/vdelecroix/17852d7e1e37f954184aa281d22c25ef9485e8b8f453c
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.