Opened 8 years ago
Last modified 8 years ago
#10975 closed enhancement
creation of certain prime finite fields is double dog slow (compared to Magma) — at Version 11
Reported by: | was | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | critical | Milestone: | sage-4.7.2 |
Component: | basic arithmetic | Keywords: | sd32 |
Cc: | Merged in: | ||
Authors: | William Stein | Reviewers: | David Roe, Tom Boothby |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
sage: time FiniteField(10^310+733) # approx 30 CPU seconds magma: time FiniteField(10^310+733) // approx 0.01 CPU seconds
This is a prime field.
Apply only trac_10975.2.patch to the Sage library.
Change History (13)
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
Also:
sage: time k = FiniteField(10^310+733) CPU times: user 34.35 s, sys: 0.04 s, total: 34.40 s sage: time k = FiniteField(10^310+733) CPU times: user 17.14 s, sys: 0.02 s, total: 17.16 s Wall time: 17.17 s
comment:3 Changed 8 years ago by
And here is more:
156 function calls (155 primitive calls) in 33.016 CPU seconds Ordered by: internal time ncalls tottime percall cumtime percall filename:lineno(function) 3 24.749 8.250 24.749 8.250 {method 'is_prime' of 'sage.rings.integer.Integer' objects} 1 8.266 8.266 8.266 8.266 {method 'is_prime_power' of 'sage.rings.integer.Integer' objects} 1 0.000 0.000 8.258 8.258 finite_field_prime_modn.py:42(__init__) 3 0.000 0.000 24.749 8.250 arith.py:404(is_prime) 1 0.000 0.000 33.016 33.016 <string>:1(<module>) 1 0.000 0.000 0.000 0.000 integer_mod_ring.py:172(__init__)
the difference probably comes from proven prime vs pseudo prime...
(and also:
magma: time IsPrime(10^310 + 733) --> true Time: 28.130
)
comment:4 Changed 8 years ago by
- Status changed from new to needs_review
Changed 8 years ago by
comment:5 Changed 8 years ago by
- Status changed from needs_review to positive_review
Positive review assuming that the doctests pass...
comment:6 Changed 8 years ago by
- Reviewers set to David Roe
comment:7 Changed 8 years ago by
- Status changed from positive_review to needs_work
sage -t -long -force_lib devel/sage/sage/structure/sage_object.pyx ********************************************************************** File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.7.alpha3/devel/sage-main/sage/structure/sage_object.pyx", line 1053: sage: print "x"; sage.structure.sage_object.unpickle_all() # long time (4s on sage.math, 2011) Expected: x... Successfully unpickled ... objects. Failed to unpickle 0 objects. Got: x * unpickle failure: load('/scratch/jdemeyer/merger/sage-4.7.alpha3/home/.sage/temp/sage.math.washington.edu/27992/dir_2/pickle_jar/_class__sage_coding_linear_code_LinearCode__.sobj') [...] Failed: _class__sage_coding_linear_code_LinearCode__.sobj _class__sage_crypto_mq_sbox_SBox__.sobj _class__sage_crypto_mq_sr_SR_gf2__.sobj _class__sage_crypto_stream_LFSRCryptosystem__.sobj _class__sage_groups_matrix_gps_general_linear_GeneralLinearGroup_finite_field__.sobj _class__sage_groups_matrix_gps_matrix_group_element_MatrixGroupElement__.sobj _class__sage_homology_chain_complex_ChainComplex__.sobj _class__sage_modular_abvar_homology_Homology_over_base__.sobj _class__sage_modular_modform_ambient_R_ModularFormsAmbient_R__.sobj _class__sage_modular_ssmod_ssmod_SupersingularModule__.sobj _class__sage_rings_finite_field_ext_pari_FiniteField_ext_pari__.sobj _class__sage_rings_finite_field_morphism_FiniteFieldHomset__.sobj _class__sage_rings_finite_field_prime_modn_FiniteField_prime_modn__.sobj _class__sage_rings_polynomial_polynomial_ring_PolynomialRing_dense_mod_p__.sobj _type__sage_matrix_matrix_modn_sparse_Matrix_modn_sparse__.sobj _type__sage_rings_finite_field_givaro_FiniteField_givaroElement__.sobj _type__sage_rings_finite_field_givaro_FiniteField_givaro__.sobj _type__sage_rings_finite_field_ntl_gf2e_FiniteField_ntl_gf2eElement__.sobj _type__sage_rings_finite_field_ntl_gf2e_FiniteField_ntl_gf2e__.sobj _type__sage_rings_morphism_RingHomomorphism_im_gens__.sobj _type__sage_rings_polynomial_polynomial_gf2x_Polynomial_GF2X__.sobj Successfully unpickled 565 objects. Failed to unpickle 21 objects. **********************************************************************
comment:8 Changed 8 years ago by
- Status changed from needs_work to needs_review
comment:9 Changed 8 years ago by
- Status changed from needs_review to positive_review
New patch fixes the pickling issue in a sensible way.
comment:10 Changed 8 years ago by
- Keywords sd32 added
comment:11 Changed 8 years ago by
- Description modified (diff)
- Reviewers changed from David Roe to David Roe, Tom Boothby
Note: See
TracTickets for help on using
tickets.
More output: