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:

Status badges

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)

11628-FiniteField_base-cache-factored_order.patch (1.4 KB) - added by pbruin 7 years ago.
cache factored order in FiniteField_base

Download all attachments as: .zip

Change History (7)

comment:1 Changed 8 years ago by zimmerma

still true with Sage 5.5: got CPU 2.16s with R = IntegerModRing(P*q), CPU 12.52s with R=GF(q).

Paul

comment:2 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:3 Changed 7 years ago by pbruin

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:4 Changed 7 years ago by pbruin

  • Authors set to Peter Bruin

Here is a patch; now testing...

Changed 7 years ago by pbruin

cache factored order in FiniteField_base

comment:5 Changed 7 years ago by pbruin

  • 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 jdemeyer

  • Merged in set to sage-5.13.beta5
  • Resolution set to fixed
  • Reviewers set to Jeroen Demeyer
  • Status changed from needs_review to closed
Note: See TracTickets for help on using tickets.