Opened 10 years ago
Closed 7 years ago
#11628 closed defect (fixed)
GF() arithmetic slower than IntegerModRing()
Reported by: | zimmerma | Owned by: | AlexGhitza |
---|---|---|---|
Priority: | major | Milestone: | sage-5.13 |
Component: | basic arithmetic | Keywords: | |
Cc: | malb, was | Merged in: | sage-5.13.beta5 |
Authors: | Peter Bruin | Reviewers: | Jeroen Demeyer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Consider the following code:
# tries to find x^2+(y/2^delta)^2 + small = (2z+1)^2 # (2^delta*x)^2 + y^2 + err = (2^delta*(2z+1))^2 def table1_mod2(p,delta,err): l = [[0,0]] P = 1 # values in l are mod P q = 1 twop = 2^p twodelta = 2^delta while P<twop: q = next_prime(q) R = IntegerModRing(P*q) newl = [] for t in l: for hx in range(q): x = t[0]+hx*P if x>=twop: break u = R((twodelta*x)^2+err) for hz in range(q): z = t[1]+hz*P if z>=twop: break y2 = R((twodelta*(2*z+1))^2)-u if y2.is_square(): newl.append([x,z]) l = newl P = P * q return l, P
With Sage 4.7 I get:
sage: time l=table1_mod2(10,0,1) Time: CPU 2.61 s, Wall: 2.63 s sage: len(l[0]) 76940
If I change R = IntegerModRing(P*q)
by R=GF(q)
, which
does not change the algorithm (we are lifting modulo 2*3*5*...),
then strangely the program is slower:
sage: time l=table1_mod2(10,0,1) Time: CPU 19.28 s, Wall: 19.33 s sage: len(l[0]) 76940
Is that normal?
Attachments (1)
Change History (7)
comment:1 Changed 8 years ago by
comment:2 Changed 8 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:3 Changed 7 years ago by
It still happens in 5.12.beta2, with a similar factor. The difference seems to be in is_square()
:
sage: F=GF(1031) sage: R=IntegerModRing(1031) sage: a=F(27); b=R(27) sage: a.is_square() True sage: b.is_square() True sage: %timeit a.is_square() 10000 loops, best of 3: 79 us per loop sage: %timeit b.is_square() 100000 loops, best of 3: 2.25 us per loop
This is surprising since a and b are of the same type (IntegerMod_int
) and have the same value; only their parents differ. Now is_square()
calls the method factored_order()
of the parent; this is cached in IntegerModRing
but not in FiniteField_base
.
Indeed, the slowness of a.is_square()
is essentially explained by the slowness of constructing a Factorization
object:
sage: %timeit Factorization([(1031,1)]) 10000 loops, best of 3: 72.2 us per loop
I guess the solution is either to speed up construction of a Factorization
, or to use caching in FiniteField_base.factored_order()
.
comment:5 Changed 7 years ago by
- Status changed from new to needs_review
With the patch, the GF(q)
version is now slightly faster on my system.
The line that this patch removes in finite_field_prime_modn.py
was redundant because FiniteField_prime_modn
inherits factored_order()
from FiniteField_base
, not from IntegerModRing
.
comment:6 Changed 7 years ago by
- Merged in set to sage-5.13.beta5
- Resolution set to fixed
- Reviewers set to Jeroen Demeyer
- Status changed from needs_review to closed
still true with Sage 5.5: got CPU 2.16s with
R = IntegerModRing(P*q)
, CPU 12.52s withR=GF(q)
.Paul