Opened 9 years ago

Closed 9 years ago

#12777 closed enhancement (fixed)

Add signal handling to libecm.pyx

Reported by: jdemeyer Owned by: tbd
Priority: major Milestone: sage-5.1
Component: factorization Keywords:
Cc: zimmerma Merged in: sage-5.1.beta0
Authors: Jeroen Demeyer Reviewers: Paul Zimmermann
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12757, #12873 Stopgaps:

Description (last modified by jdemeyer)

Add sig_on()/sig_off() in libecm.pyx.

Also add documentation and examples.

Attachments (1)

12777_libecm_sig.patch (6.0 KB) - added by jdemeyer 9 years ago.

Download all attachments as: .zip

Change History (37)

comment:1 Changed 9 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Component changed from c_lib to factorization
  • Description modified (diff)
  • Owner changed from jdemeyer to tbd

comment:2 Changed 9 years ago by jdemeyer

  • Status changed from new to needs_review

comment:3 Changed 9 years ago by zimmerma

  • Cc zimmerma added

comment:4 Changed 9 years ago by jdemeyer

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

comment:5 Changed 9 years ago by zimmerma

Jeroen, you changed to "needs work" but did not mention what are the work issues.

Paul

comment:6 Changed 9 years ago by jdemeyer

  • Status changed from needs_work to needs_review

I rebased it on top of #12757 (which has positive review).

comment:7 follow-ups: Changed 9 years ago by zimmerma

when recompiling Sage with this patch, I got a warning that variables f and n were referenced before assignment. Maybe it happened before this patch.

Some comments on the patch itself:

"The Elliptic Curve Method for Integer Factorization (GMP-ECM)": please replace GMP-ECM by ECM, since GMP-ECM is only one implementation of the ECM algorithm.

"Try to find a factor of a number": it would be better to say "integer", or even "positive integer".

"number to be factored": replace by "integer to be factored"

About the example with the factor from 2167-1: the B1 bound 1e5 is not enough to ensure the factor 2349023 will always be found. By Hasse theorem, the group order can be as large as 2352089, and since GMP-ECM only guarantees a torsion of 12, B1=196003 is needed to ensure the factor 2349023 is always found, whatever the curve (unfortunately, the current interface does not allow to specify the chosen curve).

"The following number is a Mersenne prime, so we will not find any factors": this is not entirely true, it might be that we find the input number itself if we are lucky.

For the example with the two prime factors of 2179-1, in fact B1=1e4 ensures we will find always both of them, as any value B1 >= 113. I suggest using B1=10 instead.

ecmfactor(N/11, 100, verbose=True): please replace N/11 by N//11.

Paul

comment:8 Changed 9 years ago by zimmerma

  • Reviewers set to Paul Zimmermann
  • Status changed from needs_review to needs_work
  • Work issues set to cf issues in comment 7

comment:9 in reply to: ↑ 7 Changed 9 years ago by jdemeyer

Replying to zimmerma:

when recompiling Sage with this patch, I got a warning that variables f and n were referenced before assignment. Maybe it happened before this patch.

It's a spurious warning, the code is obviously fine.

comment:10 in reply to: ↑ 7 Changed 9 years ago by jdemeyer

Replying to zimmerma:

ecmfactor(N/11, 100, verbose=True): please replace N/11 by N//11.

Actually, I did this on purpose as a mild test that the function works with things that aren't Integers but can be converted to Integers.

comment:11 in reply to: ↑ 7 Changed 9 years ago by jdemeyer

Replying to zimmerma:

For the example with the two prime factors of 2179-1, in fact B1=1e4 ensures we will find always both of them, as any value B1 >= 113.

Depends what you mean. If the ecm_factor() algorithm would be run to the end, then yes. But it's possible the algorithm stops after step 1 when only one factor is found. So you don't always get 359 * 1433 as factor.

comment:12 in reply to: ↑ 7 ; follow-up: Changed 9 years ago by jdemeyer

Replying to zimmerma:

About the example with the factor from 2167-1: the B1 bound 1e5 is not enough to ensure the factor 2349023 will always be found. By Hasse theorem, the group order can be as large as 2352089

Isn't it sufficient that 2352089 is below the B2 bound (which is the case)?

comment:13 Changed 9 years ago by zimmerma

about comment 11: I only considered Step 1 in my analysis, since B1 controls Step 1 only. Thus B1=113 is enough to find both 359 and 1433 in Step 1.

But in some rare cases it can happen that some factor is found during the initial computation before Step 1 is started. In such a case indeed only 359 or 1433 can be returned. Experimentally this seems to happen in only 1% of the cases.

Paul

comment:14 in reply to: ↑ 12 Changed 9 years ago by zimmerma

Replying to jdemeyer:

Isn't it sufficient that 2352089 is below the B2 bound (which is the case)?

you are right, but it might be that a future version of GMP-ECM changes the default B2 value for B1=1e5.

Paul

comment:15 Changed 9 years ago by jdemeyer

  • Status changed from needs_work to needs_review

Okay, I made the changes you suggested.

I also added a check that the given number is positive.

Changed 9 years ago by jdemeyer

comment:16 Changed 9 years ago by zimmerma

the new patch seems ok to me. I will run the doctests with #12757 and this patch, and I will give a "positive review" if all doctests pass. If the patchbot is faster, feel free to tick "positive review" for me.

Paul

comment:17 follow-up: Changed 9 years ago by zimmerma

  • Status changed from needs_review to positive_review
  • Work issues cf issues in comment 7 deleted

one doctest fails:

tarte% ./sage -t  devel/sage-12777/sage/misc/sagedoc.py
sage -t  "devel/sage-12777/sage/misc/sagedoc.py"            
**********************************************************************
File "/localdisk/tmp/sage-5.0.beta11/devel/sage-12777/sage/misc/sagedoc.py", line 566:
    sage: 'abvar/homology' in _search_src_or_doc('doc', 'homology', 'variety', interact=False)
Expected:
    True
Got:
    Warning, the following Sage documentation hasn't been built,
    so documentation search results may be incomplete:
    <BLANKLINE>
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/de/tutorial
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/faq
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/constructions
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/bordeaux_2008
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/a_tour_of_sage
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/reference
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/developer
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/installation
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/tutorial
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/numerical_sage
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/website
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/en/thematic_tutorials
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/fr/a_tour_of_sage
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/fr/tutorial
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/ru/tutorial
    /localdisk/tmp/sage-5.0.beta11/devel/sage/doc/output/html/tr/a_tour_of_sage
    <BLANKLINE>
    You can build these with 'sage -docbuild DOCUMENT html',
    where DOCUMENT is one of 'de/tutorial', 'faq', 'constructions', 'bordeaux_2008', 'a_tour_of_sage', 'reference', 'developer', 'installation', 'tutorial', 'numerical_sage', 'website', 'thematic_tutorials', 'fr/a_tour_of_sage', 'fr/tutorial', 'ru/tutorial', 'tr/a_tour_of_sage', 
    or you can use 'sage -docbuild all html' to build all of the missing documentation.
    False
**********************************************************************
1 items had failures:
   1 of   7 in __main__.example_8
***Test Failed*** 1 failures.
For whitespace errors, see the file /users/caramel/zimmerma/.sage//tmp/sagedoc_29685.py
         [20.6 s]

but it fails without the two patches, thus I give a positive review.

Paul

comment:18 in reply to: ↑ 17 Changed 9 years ago by jdemeyer

Replying to zimmerma:

one doctest fails:

This is the failure you get when the documentation hasn't been built (or built partially).

comment:19 follow-up: Changed 9 years ago by zimmerma

is there any reason the documentation is not built (or only partially) with sage-5.0.beta11?

Paul

comment:20 in reply to: ↑ 19 Changed 9 years ago by jdemeyer

Replying to zimmerma:

is there any reason the documentation is not built (or only partially) with sage-5.0.beta11?

No, I'm guessing something went wrong with your setup. Did you apply any other patches which might have broken the documentation? And what happens when you do make doc from $SAGE_ROOT?

comment:21 Changed 9 years ago by zimmerma

after make doc the doctest sagedoc.py passes. I have no idea why it was not done by make.

Paul

comment:22 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.0.beta14
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:23 Changed 9 years ago by jdemeyer

  • Merged in sage-5.0.beta14 deleted
  • Resolution fixed deleted
  • Status changed from closed to new

On hawk (OpenSolaris 06.2009-32), I regularly get:

sage -t  --long -force_lib devel/sage/sage/libs/libecm.pyx
**********************************************************************
File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta14/devel/sage-main/sage/libs/libecm.pyx", line 132:
    sage: ecmfactor(1, 100)
Exception raised:
    Traceback (most recent call last):
      File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta14/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta14/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta14/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_1[19]>", line 1, in <module>
        ecmfactor(Integer(1), Integer(100))###line 132:
    sage: ecmfactor(1, 100)
      File "libecm.pyx", line 152, in sage.libs.libecm.ecmfactor (sage/libs/libecm.c:1899)
        sig_on()
    RuntimeError: Floating point exception
**********************************************************************

I have not yet investigated what causes this.

comment:24 follow-up: Changed 9 years ago by zimmerma

Jeroen, did you get this error before the patch too?

Paul

comment:25 in reply to: ↑ 24 Changed 9 years ago by jdemeyer

The problem is really with the interrupt test. Disabling that test makes everything pass.

comment:26 follow-up: Changed 9 years ago by zimmerma

do you mean the problem might be related to sage.tests.interrupt.interrupt_after_delay? If you disable the test, and try to interrupt ecmfactor by hand, does it work ok?

Paul

comment:27 in reply to: ↑ 26 Changed 9 years ago by jdemeyer

It looks like a bug in Cython. ecmfactor() gets called with B1 = -NaN. This is certainly not the fault of ECM.

comment:28 Changed 9 years ago by jdemeyer

After the interrupt test, the following doctest:

        sage: n = 100
        sage: float(n)
        100.0

fails with:

**********************************************************************
File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta14/devel/sage/sage/libs/libecm.pyx", line 73:
    sage: float(n)
Expected:
    100.0
Got:
    nan
**********************************************************************

comment:29 Changed 9 years ago by jdemeyer

My current guess is that OpenSolaris?'s longjmp() doesn't completely restore the x87 FPU state.

comment:30 Changed 9 years ago by jdemeyer

Confirmed, it's a bug in longjmp(). The FPU tag word isn't restored properly.

comment:31 Changed 9 years ago by jdemeyer

  • Dependencies changed from #12757 to #12757, #12873
  • Status changed from new to needs_review

I opened #12873 for the Solaris issue. Restoring positive_review here, since the bug is unrelated to this ticket.

comment:32 Changed 9 years ago by jdemeyer

  • Status changed from needs_review to positive_review

comment:33 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.0 to sage-pending

comment:34 Changed 9 years ago by zimmerma

Jeroen, why reschedule to sage-pending and not sage-5.1?

Paul

comment:35 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-pending to sage-5.1

comment:36 Changed 9 years ago by jdemeyer

  • Merged in set to sage-5.1.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.