On Aug 14, 2007, at 4:19 PM, Alex Ghitza wrote:
> Hi, > > I've looked at ticket #59, in which David Kohel says: > > > 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. > > > It turns out that n*P is inherited from multiplication in > AdditiveGroupElement, which itself goes all the way to ModuleElement. > But at that point, it is implemented efficiently (by repeated > doubling). > It seems to me that the loss of efficiency in comparison with P+P > +...+P > is all in the overhead. > > I experimented with this and noticed that P+...+P is faster than > n*P as > long as n is smaller than 10, then the repeated doubling starts to > bear > fruit. So inside ell_point.py, I overloaded the multiplication > operator, simply making it return P+...+P if n is less than 10, and > return n*P if n is larger than 10 (see below). > > This is not a very elegant solution. For one thing, the magic > number 10 > that works on my architecture (Intel Core Duo running Gentoo) might > not > be right for a completely different machine. Is there a way to > automatically generate this number when the user compiles sage from > source (by starting with a value like 100, say, and then doing a > "binary > search" until it hits the optimal number)? Even on a single architecture, the correct crossover point will vary between different base fields. For example if the base field is Q, the best crossover will depend on the size of the coordinates. If the coordinates are enormous, it's probably best to do repeated doubling as much as possible. Similarly if you are working over GF(p) for some very large p, you'll find a different crossover from GF(101). This is going to be a difficult problem in general. I think a better approach is to try to reduce the overhead, i.e. to get the n*P pathway working faster, and/or to reduce the overhead in the addition law itself. david --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
