Opened 9 years ago

Closed 8 years ago

Last modified 8 years ago

#11036 closed enhancement (fixed)

improve solve_mod performance

Reported by: dsm Owned by: burcin
Priority: minor Milestone: sage-4.7.2
Component: symbolics Keywords: modular arithmetic, sd32
Cc: kcrisman Merged in: sage-4.7.2.alpha3
Authors: Douglas McNeil, Maarten Derickx Reviewers: John Cremona, Simon Spicer
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by leif)

Currently solve_mod(x^2==41, 100) breaks this down into solving modulus 2^2 and 5^2, but it doesn't do further reductions, so it actually loops over 4 and 25 possibilities directly. This works well for small exponents:

sage: time solve_mod(x^2 == 41, 10^2) 
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s Wall time: 0.01 s 
[(29,), (21,), (79,), (71,)] 

but performs poorly on larger ones, even if the primes involved are small:

sage: time solve_mod(x^2 == 41, 10^6)
CPU times: user 0.86 s, sys: 0.01 s, total: 0.87 s Wall time: 0.99 s 
[(703821,), (452429,), (47571,), (796179,), (203821,), (952429,), (547571,), (296179,)]

Apply only trac_11036-solve-mod.patch to the Sage library.

Attachments (2)

trac_11036_improve_solve_mod_perf.patch (9.4 KB) - added by dsm 9 years ago.
trac_11036-solve-mod.patch (9.1 KB) - added by mderickx 8 years ago.
removed a lot of bugs and refactored the patch

Download all attachments as: .zip

Change History (14)

comment:1 Changed 9 years ago by kcrisman

  • Cc kcrisman added

Agreed that this is a place we need better work. It's been fairly low priority, as you can see. Ideas? Hensel's Lemma?

comment:2 Changed 9 years ago by dsm

This patch doesn't attempt to do anything sophisticated, it simply reaches for the low-hanging fruit:

(1) It modifies solve_mod_enumerate so that if the modulus is 5^100, instead of iterating over 5^100 possibilities, it finds solutions mod 5, then uses those to find solutions mod 5^2, etc.

(2) It modifies solve_mod to short-circuit in some cases.

(3) It also makes an unrelated change: currently solve_mod(x==1, 1) returns [()], but should probably return [(0,)].

The change has little effect for small moduli but wins easily on anything nontrivial:

#OLD 
sage: time solve_mod(x^2==41, 10^7)
CPU times: user 4.21 s, sys: 0.05 s, total: 4.27 s
Wall time: 4.33 s
[(3703821,), (1452429,), (3547571,), (1296179,), (8703821,), (6452429,), (8547571,), (6296179,)]
# NEW 
sage: time solve_mod(x^2==41, 10^7)
CPU times: user 0.04 s, sys: 0.00 s, total: 0.04 s
Wall time: 0.04 s
[(3703821,), (1452429,), (3547571,), (1296179,), (8703821,), (6452429,), (8547571,), (6296179,)]

It still behaves very badly for large primes, but a lot better than the current approach on powers of small primes. This includes my use case of powers of 10-- there was an OEIS sequence I was extending which I had to do manually because solve_mod was too slow, and it irritated me that Mma could do it quickly..

Beyond the doctests I've tested it for small-coefficient univariate polynomials of order <= 5 with modulus <= 12, and for lots of random multivariate polynomials. Tests were against a four-line brute force solver. Probably I've missed something, though, so more tests would be appreciated!

comment:3 Changed 9 years ago by dsm

  • Status changed from new to needs_review

comment:4 Changed 8 years ago by mariah

  • Status changed from needs_review to needs_work

trac_11036_improve_solve_mod_perf.patch does not apply to sage-4.7.1.alpha2 on sknet/taurus (x86_64-Linux-nehalem-fc):

taurus% ./sage
----------------------------------------------------------------------
| Sage Version 4.7.1.alpha2, Release Date: 2011-06-07                |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
**********************************************************************
*                                                                    *
* Warning: this is a prerelease version, and it may be unstable.     *
*                                                                    *
**********************************************************************
sage: hg_sage.apply("/home/mariah/trac_11036_improve_solve_mod_perf.patch")
cd "/home/mariah/sage/sage-4.7.1.alpha2-x86_64-Linux-nehalem-fc-review-11036/devel/sage" && hg status
cd "/home/mariah/sage/sage-4.7.1.alpha2-x86_64-Linux-nehalem-fc-review-11036/devel/sage" && hg status
cd "/home/mariah/sage/sage-4.7.1.alpha2-x86_64-Linux-nehalem-fc-review-11036/devel/sage" && hg import   "/home/mariah/trac_11036_improve_solve_mod_perf.patch"
applying /home/mariah/trac_11036_improve_solve_mod_perf.patch
patching file sage/symbolic/relation.py
Hunk #3 FAILED at 735
Hunk #4 succeeded at 810 with fuzz 2 (offset 44 lines).
Hunk #5 FAILED at 821
Hunk #6 FAILED at 830
3 out of 6 hunks FAILED -- saving rejects to file sage/symbolic/relation.py.rej
abort: patch failed to apply
sage:

Perhaps it needs to be rebased?

comment:5 Changed 8 years ago by cremona

  • Keywords modular arithmetic added
  • Milestone set to sage-4.7.2
  • Reviewers set to John Cremona
  • Status changed from needs_work to needs_review

I did a rebase but also have managed to mess up my 4.7.1.rc[01] builds while testing other tickets, so no guarantees...

The code seems to assume that the expressions is a polynomial (in one or more variables), so there should definitely be a more efficient way to do the enumeration of solutions modulo prime powers -- this should be a linear (algebra mod p) problem once the solutions mod p are known, right?

Changed 8 years ago by mderickx

removed a lot of bugs and refactored the patch

comment:6 Changed 8 years ago by spice

  • Authors set to Douglas McNiel, Maarten Derickx
  • Reviewers changed from John Cremona to John Cremona, Simon Spicer
  • Status changed from needs_review to positive_review

Looks fine; can't find any bugs, tests work, speedups as advertised. Revised patch works with 4.7.2alpha2.

comment:7 Changed 8 years ago by dsm

If there were things I missed -- either preexisting bugs I didn't notice or bugs I introduced -- then we should probably add doctests to make sure they stay fixed.

comment:8 Changed 8 years ago by mderickx

the bugs I fixed where all in the existing doctests, I don't know how you got the timings because the code wasn't working at all

comment:9 Changed 8 years ago by was

  • Keywords sd32 added

comment:10 Changed 8 years ago by leif

  • Description modified (diff)

comment:11 Changed 8 years ago by leif

  • Merged in set to sage-4.7.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:12 Changed 8 years ago by leif

  • Authors changed from Douglas McNiel, Maarten Derickx to Douglas McNeil, Maarten Derickx
Note: See TracTickets for help on using tickets.