On Aug 23, 2007, at 11:52 PM, mabshoff wrote: > On Aug 24, 8:36 am, David Kohel <[EMAIL PROTECTED]> wrote: >> 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 > > Reopened. The description was changed to "optimize elliptic curve > arithmetic: 2*P much slower than P+P" in order to avoid the snafu we > just had. > > Cheers, > > Michael
FYI, 2*P goes down a different pathway than P*2 (one that requires a dictionary lookup among other things). I have written a custom special-purpose dictionary for use in the coercion model that is much faster. Optimizing the generic code for small m might be worth looking into as well. I think we can get the time of 4*P to less than P+P+P+P, and 2*P and 3*P should be close. I'd be happy to tackle this one next bug- squashing day (if I don't get to it before then). - Robert --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
