-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
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)?
Best,
Alex
this is the function I added to ell_point.py:
+ def _rmul_(self, n):
+ """
+ Return n times the point, with respect to the group law on the
+ elliptic curve.
+
+ INPUT:
+ self -- a point on an elliptic curve
+ n -- an integer
+
+ OUTPUT:
+ the n-th multiple of the point
+
+ EXAMPLES:
+ sage: E = EllipticCurve('389a')
+ sage: P = E([-1,1])
+ sage: 3*P
+ (26/361 : -5720/6859 : 1)
+ sage: -2*P
+ (10/9 : 8/27 : 1)
+ """
+ # for small values of n, return self+...+self
+ # for larger values, the generic multiplication is more efficient
+ if n<0:
+ result = (-n)*(-self)
+ elif n==0:
+ E = self.curve()
+ result = E(0)
+ elif n==1:
+ result = self
+ elif n==2:
+ result = self+self
+ elif n==3:
+ result = self+self+self
+ elif n==4:
+ result = self+self+self+self
+ elif n==5:
+ result = self+self+self+self+self
+ elif n==6:
+ result = self+self+self+self+self+self
+ elif n==7:
+ result = self+self+self+self+self+self+self
+ elif n==8:
+ result = self+self+self+self+self+self+self+self
+ elif n==9:
+ result = self+self+self+self+self+self+self+self+self
+ else:
+ result = AdditiveGroupElement._rmul_(self,n)
+ return result
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFGwg5YdZTaNFFPILgRApFZAJ4voxanbGm9+DYnqRtVd9nHWLEUswCeNRJM
AFdHE0B/Te/YWJXxtK0xI7I=
=+Pn5
-----END PGP SIGNATURE-----
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
