speedup integer division

[robertwb]

remove _sig_on and _sig_off for small operands, specialize for int divisor

Component: basic arithmetic

Author: Robert Bradshaw

Reviewer: Craig Citro

Merged: sage-4.1.rc0

Issue created by migration from https://trac.sagemath.org/ticket/6083

[robertwb]

Attachment: 6083-integer-div.patch.gz

[fredrik-johansson]

comment:1

I now get one trivial test failure (changed exception message):

File "/home/fredrik/sage-4.0/devel/sage-mpmath/sage/rings/integer.pyx", line 2163:
    sage: z % 0
Expected:
    Traceback (most recent call last):
    ...
    ZeroDivisionError: Integer modulo by zero
Got:
    Traceback (most recent call last):
      File "/space/wstein/farm/sage-4.0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/space/wstein/farm/sage-4.0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/space/wstein/farm/sage-4.0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_46[4]>", line 1, in <module>
        z % Integer(0)###line 2163:
    sage: z % 0
      File "integer.pyx", line 2189, in sage.rings.integer.Integer.__mod__ (sage/rings/integer.c:15033)
    ZeroDivisionError: other must be nonzero

Otherwise, this patch has my approval.

[robertwb]

comment:2

Thanks for looking at these. I'll fix this (the original error seems better).

[craigcitro]

comment:3

This patch looks good. I've added a referee patch that makes a few really minor changes:

• removes the unused _floordiv function
• changes the error messages: they all now say either "Integer division by zero" or "Integer modulo by zero." I think these are more informative, and they also now mirror the Python ones (which all say "integer division or modulus by zero"). The old ones were of the form "other (=%s) must be nonzero"%other, and by definition always had other equal to 0, so that just seemed silly.

Unless Robert or Fredrik has any objections to the second patch, I'd say this is good to go.

[robertwb]

comment:4

Yep, looks good.

[ncalexan]

comment:5

Unfortunately, this causes a segfault with the 4.0.2.alpha0 singular:

----------------------------------------------------------------------

The following tests failed:

        sage -t -long devel/sage/sage/rings/polynomial/multi_polynomial_ideal.py # Segfault
----------------------------------------------------------------------
Total time for all tests: 524.4 seconds
Tests failed!

[craigcitro]

comment:6

Attachment: trac-6083-referee.patch.gz

It turns out the segfault was coming from an infinite loop in Cython. The issue was that after the first patch above, doing Integer % IntegerMod_gmp would call into the __mod__ on IntegerMod_gmp, which tried to check if something was zero by doing something of the form Integer % IntegerMod_gmp ... and repeat ad infinitum.

So the new patch adds a small snippet to fix this, and a doctest.

[JohnCremona]

comment:7

Although I have not been following all the details of this one, I applied all patches successfully to 4.1.alpha2 and ran -testall successfully, so I'm giving it a positive review.

[rlmill]

Author: Robert Bradshaw

[rlmill]

Merged: sage-4.1.rc0

[rlmill]

Reviewer: Craig Citro