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 )
Add sig_on()
/sig_off()
in libecm.pyx
.
Also add documentation and examples.
Attachments (1)
Change History (37)
comment:1 Changed 9 years ago by
- Component changed from c_lib to factorization
- Description modified (diff)
- Owner changed from jdemeyer to tbd
comment:2 Changed 9 years ago by
- Status changed from new to needs_review
comment:3 Changed 9 years ago by
- Cc zimmerma added
comment:4 Changed 9 years ago by
- Dependencies set to #12757
- Status changed from needs_review to needs_work
comment:5 Changed 9 years ago by
comment:6 Changed 9 years ago by
- Status changed from needs_work to needs_review
I rebased it on top of #12757 (which has positive review).
comment:7 follow-ups: ↓ 9 ↓ 10 ↓ 11 ↓ 12 Changed 9 years ago by
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 2^{167}-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 2^{179}-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
- 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
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
Replying to zimmerma:
ecmfactor(N/11, 100, verbose=True)
: please replaceN/11
byN//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
Replying to zimmerma:
For the example with the two prime factors of 2^{179}-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: ↓ 14 Changed 9 years ago by
Replying to zimmerma:
About the example with the factor from 2^{167}-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
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
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
- 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
comment:16 Changed 9 years ago by
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: ↓ 18 Changed 9 years ago by
- 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
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: ↓ 20 Changed 9 years ago by
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
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
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
- 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
- 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: ↓ 25 Changed 9 years ago by
Jeroen, did you get this error before the patch too?
Paul
comment:25 in reply to: ↑ 24 Changed 9 years ago by
The problem is really with the interrupt test. Disabling that test makes everything pass.
comment:26 follow-up: ↓ 27 Changed 9 years ago by
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
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
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
My current guess is that OpenSolaris?'s longjmp()
doesn't completely restore the x87 FPU state.
comment:30 Changed 9 years ago by
Confirmed, it's a bug in longjmp()
. The FPU tag word isn't restored properly.
comment:31 Changed 9 years ago by
- 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
- Status changed from needs_review to positive_review
comment:33 Changed 9 years ago by
- Milestone changed from sage-5.0 to sage-pending
comment:34 Changed 9 years ago by
Jeroen, why reschedule to sage-pending and not sage-5.1?
Paul
comment:35 Changed 9 years ago by
- Milestone changed from sage-pending to sage-5.1
comment:36 Changed 9 years ago by
- Merged in set to sage-5.1.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
Jeroen, you changed to "needs work" but did not mention what are the work issues.
Paul