I've started a new thread for this topic with a long discussion of
where we are up to. I don't want to hijack the totally real fields
thread too much because it is extremely important, even though
ultimately some of these issues are tied up together.
Bill.
--~--~-~--~~~-
On 9/14/07, Joel B. Mohler <[EMAIL PROTECTED]> wrote:
> > FLINT?
>
> Yes, of course, I didn't mean to forget FLINT and actually that feels like a
> much better choice for a back-end to a C QQ[x] library. While I'm a native
> C++ speaker, I'm coming to appreciate the viewpoint that such things shou
On Friday 14 September 2007 16:53, William Stein wrote:
> > I'm really thinking that there should be C library that does ZZ[x] with a
> > denominator so we wouldn't have to put that logic in cython. That
> > library might build on NTL. I'm uncomfortable with code like that in
> > cython (but tha
On 9/14/07, Joel B. Mohler <[EMAIL PROTECTED]> wrote:
> On Friday 14 September 2007 15:31, Robert Bradshaw wrote:
> > Currently, ZZ[x] -> QQ[x] does
> >
> > ntl_ZZ -> str -> list -> list of rationals -> str -> pari
> >
> > Perhaps QQ[x] should be implemented as ZZ[x] + denominator?
>
> Well, this
On Friday 14 September 2007 15:31, Robert Bradshaw wrote:
> Currently, ZZ[x] -> QQ[x] does
>
> ntl_ZZ -> str -> list -> list of rationals -> str -> pari
>
> Perhaps QQ[x] should be implemented as ZZ[x] + denominator?
Well, this will probably be more efficient with-in the week.
More generally, I
On Sep 13, 2007, at 9:07 PM, William Stein wrote:
> On 9/13/07, John Voight <[EMAIL PROTECTED]> wrote:
[...]
>> So there's no hope: there's just overhead in the coercion here?
>
> Nobody has ever spent any effort on optimizing the following in SAGE:
>- number field construction
>- If f
On 9/13/07, John Voight <[EMAIL PROTECTED]> wrote:
>
> Hi Will,
>
> > > (2) I have my Cython code in a tr_data.spyx file and my Python code in
> > > a totallyreal.py file. How do I include the former into the latter--
> > > or do I have to include both at the prompt?
> >
> > You can't trivially g
It takes Pari 2s to do a test of 10^5 polynomials of the form you
give, for irreducibility. It also takes it 2s to check if 10^5 pairs
give you isomorphic number fields. It takes 3s to compute all the
discriminants using nfdisc.
If it is taking 57s it's off its head. Coercion should be just about
Hi Will,
> > (2) I have my Cython code in a tr_data.spyx file and my Python code in
> > a totallyreal.py file. How do I include the former into the latter--
> > or do I have to include both at the prompt?
>
> You can't trivially get at tr_data.spyx from totallyreal.py, but you can
> from a .sage
Hi John,
Yes those are tiny polynomials. The way NTL works is to compute the
content of both polynomials and divide out by that, compute the gcd of
the contents, break up one prime at a time and compute the gcd mod p.
After each recombination (it's all done "in place") it checks to see
if the gcd
Hi Bill,
Thanks for your messages--it certainly is an interesting problem when
viewed in context.
For me, my polynomials are tiny: small degree (<=11) and very small
coefficients. Moreover, I already have computed the roots to some
numerical precision and only call this when there appears to be
Having said all that, Magma uses the GCDHEU algorithm and a modular
algorithm. Note that m in the above is the size in bits of the
coefficients of the resultant, which you don't know an a priori bound
for. You can figure out a bound however, but as in both algorithms,
you need to know the roots of
OK, I've looked into this more carefully and the reason why I don't
know which is the best algorithm for polynomial gcd over Z is that
most people when writing papers don't consider this case carefully
when they come to do asymptotic or runtime analysis. That is
presumably because it is hard to do
Hi John,
Despite having looked into the problem of computing gcd's efficiently,
I don't know which algorithms are in practice faster for checking
squarefreeness. In fact, to date, I am unable to tell you which
algorithm is even asymptotically fastest for computing polynomial gcd.
For integer gcd
On 9/12/07, John Voight <[EMAIL PROTECTED]> wrote:
> So I took the plunge and started trying to write optimized code in
> Cython for my enumeration problem. The code can be found at
> http://www.cems.uvm.edu/~voight/tr_data.spyx
> http://www.cems.uvm.edu/~voight/totallyreal.py
> and for the e
some partial answers to a subset of those questions:
On Sep 12, 2007, at 7:26 PM, John Voight wrote:
> (1) At a certain moment in the algorithm, I need to test if a
> polynomial with integer coefficients is squarefree (using exact
> arithmetic). Is it acceptable practice to do this in a brutal
16 matches
Mail list logo
