#7262: Have multiplcation_by_m() return an EllipticCurveIsogeny object
-------------------------------+--------------------------------------------
Reporter: wuthrich | Owner: davidloeffler
Type: defect | Status: needs_review
Priority: minor | Milestone: sage-4.3.1
Component: elliptic curves | Keywords: elliptic curves, isogeny,
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-------------------------------+--------------------------------------------
Changes (by craigcitro):
* cc: was, robertwb (added)
* status: new => needs_review
* upstream: => N/A
Comment:
I've got a prototype patch ready that I'm going to post now, but I'd like
some opinions before I finish it off.
First, here's what I did: it'd be nice if we could make
`multiplication_by_m` return an `EllipticCurveIsogeny` object without
breaking any old code. This is no problem: I added a `__getitem__` and
`__iter__` method to `EllipticCurveIsogeny` objects, so that statements
like {{{ x, y = E.multiplication_by_m(7) }}} still work just as before.
However, it's not all sunshine and roses ...
Here are some questions:
* It's '''significantly''' slower to do it this way. This is because
isogeny objects compute a whole bunch of other information about
themselves, which has to happen to create one. (We could do a lot more
work to make all those attributes lazy, which would possibly alleviate
some of the issue.) This isn't just "oh, it's a few percent slower" --
here's an example with the old code:
{{{
sage: E = EllipticCurve('11a1')
sage: %time x,y = E.multiplication_by_m(17)
CPU times: user 0.73 s, sys: 0.02 s, total: 0.75 s
Wall time: 0.87 s
}}}
I ran the new version of the code on the same example when I
'''started''' this ticket, and it's still running. And no, I don't type at
4000 WPM. `:)` So that's definitely a huge speed penalty. A _very_ cursory
glance suggests that at least part of this time is getting lost in some
polynomial arithmetic; I'm happy to look into that if no one beats me to
it.
* The `x_only` argument also creates an issue. Before, the function would
return either a rational function or a tuple of two of them, which is
unfortunate -- in general, the rule of thumb is that we prefer for
functions to have a single return type, no matter what flags are passed.
So we could still do the same thing, but it somehow feels even more
egregious to have the function return either a rational function or an
isogeny object.
I'm not sure what the best plan is -- I'm guessing people aren't willing
to accept that speed hit in general. We could also have a separate
function, maybe `multiplication_by_m_isogeny` or somesuch?
I'm attaching a patch anyway, in case people want to play around with it.
Don't be frightened by the size of the patch file -- I got a little
carried away using `\C-t` in emacs, and reformatted all the documentation
to be at most 80 characters wide. I also changed some statements of the
form `x == None` to `x is None,` mostly out of habit. (It's faster, and
arguably more sensible -- after all, `None` is a unique object.) So even
if we decide on a completely different plan for this ticket, I'd still
like to extract the doc cleanup changes and submit those.
Since I'm mostly looking for comments, I'm adding one or two people on the
cc list ...
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7262#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
