On Nov 3, 2008, at 6:20 AM, eduardo wrote:
> Hi there!
>
> I attended the SAGE DAYS 10 in Nancy (Thanks the people there for
> everything!). As other colleague and me are interested in crypto
> interesting Elliptic Curves, we noticed that the SAGE function that
> calculates the Hilbert class polynomial needs magma, so we proposed at
> the
> Coding Sprint the implementation of this function, for instance with
> CM
> Methods or/and the CRT Methods. After some time spending on it we got
> some issues that surely can be corrected with some help/discussion:
>
> We implemented the CM-version of it in purely sage-python code.
> Comparing timings with Magma our implementation was almost (here)-
> times
> slower. So we can emphasize 3 bottlenecks apart from computation of a
> j-Invariant: the computation of the appropriate precision, generating
> of all
> different reduced primitive quadratic forms and the using of Python.
>
> 1. An idea of the computation of the appropriate precision we
> gathered
> from Andreas Enge's article [http://hal.inria.fr/inria-00001040]. He
> gives
> an upper bound for the size of the largest coefficient of the
> polynomial.
>
> 2. To generate all reduced primitive quadratic forms we used first the
> function
> called BinaryQF_reduced_representatives() from quadratic forms
> library. After
> that we implemented our version of this function and got about 50%
> speed up,
> and the present code doesn't generate primitive forms if the
> discriminant is
> non-fundamental.
>
> 3. But anyway our implementation was a snail comparing to magma's one.
> And then
> we tried to use Cython to implement the same function. As a result
> our
> implementation was a bit faster than magma's at least in experiments
> we ran.
> The only thing worried us was the using of type long long for
> discriminant of
> quadratic field. It means the input parameter is bounded by 2^63. It
> is
> O.K. for D around -2^63; even magma will break down since the
> complexity
> of the algorithm is O(|D|).
>
> Now I would like to ask some questions:
> * Shall we consider the bigger value of D then values fit in long
> long?
No idea what your constants are like, but 2^63 nanoseconds is
something like 290 years, so on face value that seems prohibitively
expensive without some massive parallelization of some sort (which
would probably require a complete rewrite of your algorithm.)
However, if I remember correctly the runtime depended on the
factorization of D, not just the size of D itself.
What I would suggest is keeping the long-long version, as that is
probably the most useful useful case, and the speed improvements are
huge. One could also have the mpz version as well, only called when
needed.
> * Is it safe to use long long? Is it 64-bit on all platforms? Does
> Cython care about that?
long long always has at least 64 bits, and is required on all
platforms we target for Sage, so it is safe to use that.
> * We can perhaps use mpz_t (from GMP) instead of long long. Then we
> need to know how can we input/ouput a variable of this type in
> Cython. Is there some documentation about that?
Here is how you would do it (the easy way):
from sage.rings.integer cimport Integer
def add_via_gmp(Integer a, Integer b):
cdef Integer z = PY_NEW(Integer)
mpz_add(z.value, a.value, b.value)
return z
There is also the issue of memory management (if one needs temporary
mpz_t values) and the code is much harder to read/debug. Of course,
99% of the savings would be accomplished by just moving the inner
loop or two to use the mpz_* functions directly, so writing the whole
function this way would be overkill. The speed of this implementation
would almost certainly be closer to the speed of the Python version
than to the speed of the long-long version, as mpz_t arithmetic is
many, many times slower than manipulating long-longs.
- 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://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
