Just one comment, about your use of BinaryQF_reduced_representatives() . There are patches undergoing review now relevant to this (at #4120). That function was made a lot more efficient in #3857 (now merged) but that function returns a list of the representative forms, while you only need the number. The patch at #4120 has a function to give the number but unfortunately does not use the speedups implemented (by be and then Nils Skoruppa) in #3857. For such a critical function I am sure that it should be implemented in cython anyway.
John 2008/11/3 eduardo <[EMAIL PROTECTED]>: > > 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? > * Is it safe to use long long? Is it 64-bit on all platforms? > Does Cython care about 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? > > thanks in Advance! > > cheers > Ed > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
