Opened 16 years ago

Closed 15 years ago

#59 closed enhancement (fixed)

optimize elliptic curve arithmetic: 2*P much slower than P+P

Reported by: was Owned by: somebody
Priority: minor Milestone: sage-2.8.3
Component: basic arithmetic Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

William, my student noticed some slow performance with elliptic curves group law. I think there was a huge overhead in duplication: sage: E = EllipticCurve?([GF(101)(1),3]) sage: P = E([-1,1,1]) sage: timeit 2*P 100 loops, best of 3: 3.81 ms per loop sage: timeit P+P 1000 loops, best of 3: 1.81 ms per loop Basically n*P was passing through all sorts of high-level layers for group schemes, abelian groups, and the like. I've started teaching two courses here, and at the latest, will have to adapt to becoming a Dad next Tuesday (my wife Martine is overdue). But I may be able to add some code in the next three weeks.

Change History (5)

comment:1 Changed 16 years ago by was

This was from David Kohel. Here's a better formated version:

William, my student noticed some slow performance with elliptic curves group law. I think there was a huge overhead in duplication:

sage: E = EllipticCurve([GF(101)(1),3])
sage: P = E([-1,1,1])
sage: timeit 2*P
100 loops, best of 3: 3.81 ms per loop
sage: timeit P+P
1000 loops, best of 3: 1.81 ms per loop

Basically n*P was passing through all sorts of high-level layers for group schemes, abelian groups, and the like.

comment:2 Changed 15 years ago by mabshoff

  • Milestone set to sage-2.8.3

I guess this has been fixed. With Sage 2.8.2 I get:

sage: E = EllipticCurve([GF(101)(1),3])
sage: P = E([-1,1,1])
sage: timeit 2*P
1000 loops, best of 3: 317 µs per loop
sage: timeit P+P
10000 loops, best of 3: 92.7 µs per loop

Cheers,

Michael

comment:3 Changed 15 years ago by was

  • Resolution set to fixed
  • Status changed from new to closed

Fixed by Robert bradshaw.

comment:4 Changed 15 years ago by mabshoff

  • Resolution fixed deleted
  • Status changed from closed to reopened
  • Summary changed from optimize elliptic curve arithmetic to optimize elliptic curve arithmetic: 2*P much slower than P+P

Ok, reopened.

For details see http://groups.google.com/group/sage-devel/t/e884bb605728649a

To quote David Kohel:

I think the problem needs to be profiled.  The problem is likely NOT
in elliptic curves, but some
horrendous chain of calls to module operations before getting to the
(same) actual algorithms.
Note that P*2 is slightly faster since it calls directly the member
function of P rather than a
function on integers.

sage: E = EllipticCurve([GF(101)(1),3])
sage: P = E([-1,1,1])
sage: timeit 2*P
1000 loops, best of 3: 309 µs per loop
sage: timeit P+P
10000 loops, best of 3: 89.8 µs per loop
sage: timeit P*2
1000 loops, best of 3: 204 µs per loop

Yes, reopen it: these sorts of problems need to be looked at and
optimized.  The same problem
applies to points on Jacobians (compare 2*P, P*2, and P+P).

--David 

comment:5 Changed 15 years ago by was

  • Resolution set to fixed
  • Status changed from reopened to closed

As of SAGE-2.8.3 (probably due to Tom Boothby's work), this is now resolved:

sage: E = EllipticCurve([GF(101)(1),3])
sage: P = E([-1,1,1])
sage: import timeit
sage: t = timeit.Timer('2*P', 'from sage.all import EllipticCurve, GF; E = EllipticCurve([GF(101)(1),3]); P = E([-1,1,1])')
sage: t.timeit(10000)
1.0524919033050537
sage: s = timeit.Timer('P+P', 'from sage.all import EllipticCurve, GF; E = EllipticCurve([GF(101)(1),3]); P = E([-1,1,1])')
sage: s.timeit(10000)
1.067209005355835
Note: See TracTickets for help on using tickets.