flint-devel — Development list for the FLINT project

Re: [flint-devel] fmpz_montgomery

[Bill H. <goo...@go...>]

FLINT's trac system has been down for a long time. It relies on a
server working, and every time it stops people "forget" how to restart
it. I've tried and failed.

However, if you post to the flint development list (in CC) that will
suffice to let people know you are planning on working on this.

Bill.

2009/5/12 David Roe <ro...@ma...>:
> I will check with him.
>
> Do I get a login for Flint's trac from you or William?  I may write an
> analogue of mpz_remove for fmpz_t's (that's the main function that I use for
> p-adics).
> David
>
> On Tue, May 12, 2009 at 5:36 PM, Bill Hart <goo...@go...>
> wrote:
>>
>> Hi David,
>>
>> Actually Gonzalo Tornaria wrote the montgomery code. I would imagine
>> that there is always a gain. However maybe Gonzalo knows better.
>>
>> Benchmarking it would be the only way to be sure.
>>
>> Bill.
>>
>> 2009/5/12 David Roe <ro...@ma...>:
>> > Hey Bill,
>> > I'm writing code for p-adic polynomials in Sage right now, using
>> > fmpz_poly_t's as the underlying data type.  I'm wondering how
>> > extensively to
>> > use the fmpz_montgomery code in flint.  I realize that I'm going to have
>> > to
>> > special case p=2 if I do.
>> >
>> > If I have an fmpz_montgomery_t around already, is fmpz_montgomery_mulmod
>> > always at least as fast as fmpz_mulmod?  For reasonably small moduli, is
>> > there much of a gain?
>> >
>> > If I have to call fmpz_montgomery_init, do you have an idea of how many
>> > mulmods or mods I need in order to make it worthwhile?
>> > David
>> >
>
>

[flint-devel] FLINT 1.2.5

[Bill H. <goo...@go...>]

I've release FLINT 1.2.5. This fixes a serious error that existed in
zn_poly-0.8. Unbeknownst to me, David Harvey had already fixed this
issue in zn_poly-0.9 but I had not realised that had been released,
due to him changing institutions and me not updating my link to his
webpage in my frequently visited tabs list. FLINT now uses zn_poly-0.9
by default for polynomial arithmetic over Z/nZ in zmod_poly.

There is still an issue with z_factor which fails to factor some
numbers very rarely (it prints a message to say it has failed). Tom
Boothby is working on a fix, and this should also speed up the
factorisation function noticeably.

Bill.

Re: [flint-devel] fmpz_poly_evaluate bug in 1.2.2

[Michael A. <mab...@go...>]

On Tue, Mar 31, 2009 at 2:10 PM, William Hart <ha...@ya...> wrote:
>
> I've just issued FLINT 1.2.3 which addresses this issue. Thanks Burcin.
>
> Amazingly I had made the same mistake in three separate implementations of the same function using different algorithms. They weren't even cut and pastes of each other, but this explains why the doctest wasn't failing. Roughly speaking, the reference implementation was broken!!
>
> Bill.

Hi Bill,

I told you in person, but for the record:

(a) FLINT 1.2.3 cannot compile its test suite on Solaris 10 due to

gcc -std=c99 -I/home/mabshoff/build-3.3/sage-3.3-fulvia/local/include/
-I/home/mabshoff/build-3.3/sage-3.3-fulvia/local/include  -fPIC
-funroll-loops   -O3 -c mpn_extras-test.c -o mpn_extras-test.o
In file included from /usr/include/sys/time.h:99,
                 from profiler.h:30,
                 from test-support.h:36,
                 from mpn_extras-test.c:35:
/usr/include/sys/types.h:536: error: duplicate ‘unsigned’
make: *** [mpn_extras-test.o] Error 1
Error building the test suite for FLINT

The "fix" in this case is to undef ulong in profile.h right before
including time.h and its two friends. I am still waiting on the test
to finish, but so far no failures until Testing
zmod_poly_factor_square_free(). :)

(b) __thread is unsupported on OSX. Removing them (since Sage does not
use a threaded FLINT) does make the library compile and also makes the
test suite pass (I had to swap out CC for CPP for all the test suite
files, but that might be a Sage specific problem). Oddly enough the
wall vs. CPU time seems to often disagree on that OSX box. For example
here a small snippet from the test log where CPU time >> WALL time,
CPU time == Wall time and CPU TIME << WALL time.

Testing zmod_poly_mul_precache()... Cpu = 5666 ms  Wall = 9981 ms ... ok
Testing zmod_poly_mul_trunc_n_precache()... Cpu = 6070 ms  Wall =
10446 ms ... ok
Testing zmod_poly_scalar_mul()... Cpu = 284 ms  Wall = 310 ms ... ok
Testing zmod_poly_make_monic()... Cpu = 4868 ms  Wall = 577 ms ... ok

With the various fixes mentioned above FLINT 1.2.3 passes its test
suite on OSX 10.5/Intel in 32 bit mode.

Cheers,

Michael

Re: [flint-devel] fmpz_poly_evaluate bug in 1.2.2

[William H. <ha...@ya...>]

I've just issued FLINT 1.2.3 which addresses this issue. Thanks Burcin.

Amazingly I had made the same mistake in three separate implementations of the same function using different algorithms. They weren't even cut and pastes of each other, but this explains why the doctest wasn't failing. Roughly speaking, the reference implementation was broken!!

Bill.


--- On Wed, 4/1/09, Burcin Erocal <bu...@er...> wrote:

> From: Burcin Erocal <bu...@er...>
> Subject: [flint-devel] fmpz_poly_evaluate bug in 1.2.2
> To: "Development list for FLINT" <fli...@li...>
> Date: Wednesday, April 1, 2009, 4:20 AM
> Hi,
> 
> While looking through fmpz_poly.c in 1.2.2, I noticed that
> the first
> lines of fmpz_poly_evaluate are as follows:
> 
> void fmpz_poly_evaluate(fmpz_t output, fmpz_poly_t poly,
> fmpz_t value)
> {
>    fmpz_t val;
> 	
> 	if ((poly->length == 0) || (value[0] == 0)) 
> 	{
>       output[0] = 0L;
> 		return;
> 	}
> 
> This seems to be a bug, since it always returns 0 if value
> is 0, when
> it should return the constant coefficient of poly.
> 
> I didn't produce a fix, since I wasn't sure if just
> using
> fmpz_set(output,value) was enough when poly->length == 1
> or value == 0.
> 
> 
> If you wonder why I was reading that file, I need to
> evaluate
> polynomials in ZZ[x] modulo p as part of some linear
> algebra routines
> I'm working on. I attached a patch for a function which
> implements
> evaluation modulo p. Is it possible to include some
> approximation of
> that in future versions of FLINT?
> 
> 
> I also need functions to translate (compose with
> polynomials of degree
> 1) zmod_poly_t's, and fmpz_poly_t's modulo some p.
> I implemented
> Horner's method in cython to have a reasonably quick
> way of doing this.
> Do you think it's worth putting these in FLINT?
> 
> BTW, in the first part of this article
> 
> http://doi.acm.org/10.1145/258726.258745
> 
> von zur Gathen and Gerhard measure the performance of
> different
> algorithms for this task. It might be of interest if we
> consider making
> this fast in FLINT.
> 
> 
> Cheers,
> Burcin------------------------------------------------------------------------------
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel


      

Re: [flint-devel] fmpz_poly_evaluate bug in 1.2.2

[Bill H. <goo...@go...>]

Thanks Burcin,

I'll issue a fix for the eval bug as soon as I can. The rest I'll get
back to you about when I find some spare moments. In short, yes, I
think it would be good to include fast versions of these things in
FLINT.

Bill.

2009/3/31 Burcin Erocal <bu...@er...>:
> Hi,
>
> While looking through fmpz_poly.c in 1.2.2, I noticed that the first
> lines of fmpz_poly_evaluate are as follows:
>
> void fmpz_poly_evaluate(fmpz_t output, fmpz_poly_t poly, fmpz_t value)
> {
>   fmpz_t val;
>
>        if ((poly->length == 0) || (value[0] == 0))
>        {
>      output[0] = 0L;
>                return;
>        }
>
> This seems to be a bug, since it always returns 0 if value is 0, when
> it should return the constant coefficient of poly.
>
> I didn't produce a fix, since I wasn't sure if just using
> fmpz_set(output,value) was enough when poly->length == 1 or value == 0.
>
>
> If you wonder why I was reading that file, I need to evaluate
> polynomials in ZZ[x] modulo p as part of some linear algebra routines
> I'm working on. I attached a patch for a function which implements
> evaluation modulo p. Is it possible to include some approximation of
> that in future versions of FLINT?
>
>
> I also need functions to translate (compose with polynomials of degree
> 1) zmod_poly_t's, and fmpz_poly_t's modulo some p. I implemented
> Horner's method in cython to have a reasonably quick way of doing this.
> Do you think it's worth putting these in FLINT?
>
> BTW, in the first part of this article
>
> http://doi.acm.org/10.1145/258726.258745
>
> von zur Gathen and Gerhard measure the performance of different
> algorithms for this task. It might be of interest if we consider making
> this fast in FLINT.
>
>
> Cheers,
> Burcin
> ------------------------------------------------------------------------------
>
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel
>
>

[flint-devel] fmpz_poly_evaluate bug in 1.2.2

[Burcin E. <bu...@er...>]

Hi,

While looking through fmpz_poly.c in 1.2.2, I noticed that the first
lines of fmpz_poly_evaluate are as follows:

void fmpz_poly_evaluate(fmpz_t output, fmpz_poly_t poly, fmpz_t value)
{
   fmpz_t val;
	
	if ((poly->length == 0) || (value[0] == 0)) 
	{
      output[0] = 0L;
		return;
	}

This seems to be a bug, since it always returns 0 if value is 0, when
it should return the constant coefficient of poly.

I didn't produce a fix, since I wasn't sure if just using
fmpz_set(output,value) was enough when poly->length == 1 or value == 0.


If you wonder why I was reading that file, I need to evaluate
polynomials in ZZ[x] modulo p as part of some linear algebra routines
I'm working on. I attached a patch for a function which implements
evaluation modulo p. Is it possible to include some approximation of
that in future versions of FLINT?


I also need functions to translate (compose with polynomials of degree
1) zmod_poly_t's, and fmpz_poly_t's modulo some p. I implemented
Horner's method in cython to have a reasonably quick way of doing this.
Do you think it's worth putting these in FLINT?

BTW, in the first part of this article

http://doi.acm.org/10.1145/258726.258745

von zur Gathen and Gerhard measure the performance of different
algorithms for this task. It might be of interest if we consider making
this fast in FLINT.


Cheers,
Burcin

Re: [flint-devel] Poly division over Z

[Bill H. <goo...@go...>]

I coded up a simple fmpz_poly_divexact to match Magma's Exact
Quotient. It uses the modular algorithm for polys with small
coefficients.

Here is the new graph:

http://sage.math.washington.edu/home/wbhart/div2.png

I've no idea what the remaining red patch is. It is right into the
modular region, which relies on division in Z/pZ[x], which we know
runs as fast or faster than Magma. So who knows. Perhaps their
crossover from the usual algorithm to the modular algorithm (if that
is what they use) is higher and their usual algorithm faster than
FLINT's at that point.

I guess I'll figure it out eventually.

Bill.

2009/3/21 Bill Hart <goo...@go...>:
> Here is a profile for polynomial division over Z:
>
> http://sage.math.washington.edu/home/wbhart/div.png
>
> I'm guessing Magma uses either a modular algorithm or some kind of
> Kronecker-Segmentation type algorithm in the red region. I'll
> eventually get around to implementing this.
>
> Note I used Magma's ExactQuotient function. Here Magma definitely has
> an advantage.
>
> Bill.
>

[flint-devel] Poly GCD over Z

[Bill H. <goo...@go...>]

Here is polynomial GCD over Z:

http://sage.math.washington.edu/home/wbhart/gcd.png

I haven't yet tried the subresultant algorithm in that region at the
bottom left where it is red since removing the bug from pseudo
division.

However other red regions have now disappeared due to the
asymptotically fast integer GCD.

Bill.

[flint-devel] Poly division over Z

[Bill H. <goo...@go...>]

Here is a profile for polynomial division over Z:

http://sage.math.washington.edu/home/wbhart/div.png

I'm guessing Magma uses either a modular algorithm or some kind of
Kronecker-Segmentation type algorithm in the red region. I'll
eventually get around to implementing this.

Note I used Magma's ExactQuotient function. Here Magma definitely has
an advantage.

Bill.

Re: [flint-devel] Z/pZ[x] factoring

[Bill H. <goo...@go...>]

Here is the gcd graph. It isn't too bad, and clearly isn't the source
of the issues with the factoring timings:

http://sage.math.washington.edu/home/wbhart/zpgcd.png

Magma seems to have a faster basecase, though I don't know how that is possible.

I also don't know how it is possible that they are faster for moduli
of <= 8 bits. Nothing shows up in the timings for multiplication and
division, and that's about all GCD uses. So I'm a bit mystified by
that, especially in the basecase region.

Bill.

2009/3/20 Bill Hart <goo...@go...>:
> I wonder if it is worthwhile trying to patch fflas-ffpack into FLINT
> to see if it can speed up the existing Berlekamp.
>
> Maybe the entire complexity and speed of the algorithm is being
> dominated by the Gaussian elimination step in FLINT.
>
> Probably fflas-ffpack has a function for doing this. So it might be
> easy to patch it in, replacing the function
> zmod_mat_row_reduce_gauss_jordan(zmod_mat_t mat) in zmod_mat.c in
> FLINT.
>
> Maybe that is all that is required. Everything else in that algorithm
> should be _super_ fast it seems (I'm just about to check the GCD by
> comparing it to Magma to make sure).
>
> Bill.
>
> 2009/3/20 Bill Hart <goo...@go...>:
>> I reckon you could get a 5 times speedup if you implemented the other
>> algorithm from Sage, if you had linear algebra as fast as Magma. But
>> last I checked, fflas-ffpack was not there speedwise yet. I had code
>> running about twice that speed in FLINT and within 30% of what Magma
>> had. Obviously I didn't implement the other versions of Berlekamp
>> using it though.
>>
>> So, maybe you could get a 2 times speedup with fflas-ffpack and
>> implementing the other Berlekamp algorithms in Sage.
>>
>> Obviously 2 times is worth it from my point of view. I don't know how
>> long it will be before I have fast linear algebra. Depends what I get
>> done when visiting William in a couple of weeks time. But it is likely
>> to be at least 6 months before I get factoring over Z/pZ really fast.
>>
>> Bill.
>>
>> 2009/3/20 Burcin Erocal <bu...@er...>:
>>> On Thu, 19 Mar 2009 23:12:49 +0000
>>> Bill Hart <goo...@go...> wrote:
>>>
>>>> I have been producing some timings for factoring polynomials over
>>>> Z/pZ[x] against a recent version of Magma.
>>>>
>>>> Here is the graph:
>>>>
>>>> http://sage.math.washington.edu/home/wbhart/zpfactor.png
>>>>
>>>> It appears that Magma is thrashing us, even with all the recent
>>>> improvements to zmod_poly.
>>>>
>>>> I don't know if Magma has been sped up or if we just mistimed in the
>>>> past, but towards the left of that diagram we are 2-5 times slower
>>>> than Magma, and on the right hand side it's more like 12 times slower.
>>>>
>>>> The Berlekamp algorithm we use is a polynomial one, with a
>>>> Gauss-Jordan elimination somewhere along the way. But I think there is
>>>> a version of the algorithm which computes much more using matrix
>>>> algebra.
>>>>
>>>> As FLINT is a long way away from having fast matrices over Z/pZ I
>>>> think it will be some time before we can beat Magma (again) on this
>>>> benchmark. This is a little disappointing, but I'm sure it can be
>>>> fixed in time.
>>>
>>> Even if it's not an option for the main FLINT relase, we could patch
>>> FLINT in Sage to use fflas-ffpack from linbox to get fast linear
>>> algebra over Z/pZ.
>>>
>>> Do you think it's worth the time to try implementing this other version
>>> you mention? What do the factorization experts say? Andy?
>>>
>>> Cheers,
>>> Burcin
>>>
>>> ------------------------------------------------------------------------------
>>> Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are
>>> powering Web 2.0 with engaging, cross-platform capabilities. Quickly and
>>> easily build your RIAs with Flex Builder, the Eclipse(TM)based development
>>> software that enables intelligent coding and step-through debugging.
>>> Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com
>>> _______________________________________________
>>> flint-devel mailing list
>>> fli...@li...
>>> https://lists.sourceforge.net/lists/listinfo/flint-devel
>>>
>>
>

Re: [flint-devel] Z/pZ[x] factoring

[Bill H. <goo...@go...>]

I wonder if it is worthwhile trying to patch fflas-ffpack into FLINT
to see if it can speed up the existing Berlekamp.

Maybe the entire complexity and speed of the algorithm is being
dominated by the Gaussian elimination step in FLINT.

Probably fflas-ffpack has a function for doing this. So it might be
easy to patch it in, replacing the function
zmod_mat_row_reduce_gauss_jordan(zmod_mat_t mat) in zmod_mat.c in
FLINT.

Maybe that is all that is required. Everything else in that algorithm
should be _super_ fast it seems (I'm just about to check the GCD by
comparing it to Magma to make sure).

Bill.

2009/3/20 Bill Hart <goo...@go...>:
> I reckon you could get a 5 times speedup if you implemented the other
> algorithm from Sage, if you had linear algebra as fast as Magma. But
> last I checked, fflas-ffpack was not there speedwise yet. I had code
> running about twice that speed in FLINT and within 30% of what Magma
> had. Obviously I didn't implement the other versions of Berlekamp
> using it though.
>
> So, maybe you could get a 2 times speedup with fflas-ffpack and
> implementing the other Berlekamp algorithms in Sage.
>
> Obviously 2 times is worth it from my point of view. I don't know how
> long it will be before I have fast linear algebra. Depends what I get
> done when visiting William in a couple of weeks time. But it is likely
> to be at least 6 months before I get factoring over Z/pZ really fast.
>
> Bill.
>
> 2009/3/20 Burcin Erocal <bu...@er...>:
>> On Thu, 19 Mar 2009 23:12:49 +0000
>> Bill Hart <goo...@go...> wrote:
>>
>>> I have been producing some timings for factoring polynomials over
>>> Z/pZ[x] against a recent version of Magma.
>>>
>>> Here is the graph:
>>>
>>> http://sage.math.washington.edu/home/wbhart/zpfactor.png
>>>
>>> It appears that Magma is thrashing us, even with all the recent
>>> improvements to zmod_poly.
>>>
>>> I don't know if Magma has been sped up or if we just mistimed in the
>>> past, but towards the left of that diagram we are 2-5 times slower
>>> than Magma, and on the right hand side it's more like 12 times slower.
>>>
>>> The Berlekamp algorithm we use is a polynomial one, with a
>>> Gauss-Jordan elimination somewhere along the way. But I think there is
>>> a version of the algorithm which computes much more using matrix
>>> algebra.
>>>
>>> As FLINT is a long way away from having fast matrices over Z/pZ I
>>> think it will be some time before we can beat Magma (again) on this
>>> benchmark. This is a little disappointing, but I'm sure it can be
>>> fixed in time.
>>
>> Even if it's not an option for the main FLINT relase, we could patch
>> FLINT in Sage to use fflas-ffpack from linbox to get fast linear
>> algebra over Z/pZ.
>>
>> Do you think it's worth the time to try implementing this other version
>> you mention? What do the factorization experts say? Andy?
>>
>> Cheers,
>> Burcin
>>
>> ------------------------------------------------------------------------------
>> Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are
>> powering Web 2.0 with engaging, cross-platform capabilities. Quickly and
>> easily build your RIAs with Flex Builder, the Eclipse(TM)based development
>> software that enables intelligent coding and step-through debugging.
>> Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com
>> _______________________________________________
>> flint-devel mailing list
>> fli...@li...
>> https://lists.sourceforge.net/lists/listinfo/flint-devel
>>
>

Re: [flint-devel] Division in Z/pZ[x]

[Bill H. <goo...@go...>]

I was unable to take the division graph any further as Magma crashed with:

driver(
)
prof2d_sample(
    x: 39130,
    y: 18
)
sampler(
    length: 39130,
    bits: 18,
    count: 4
)
In file "poly-ZpXdivexact.m", line 75, column 23:
>>     d := ExactQuotient(c, a);^M
                         ^
Runtime error in 'ExactQuotient': Argument 1 is not exactly divisible by
argument 2


The following lines from the Magma script should guarantee that this
is impossible (and therefore a bug):

p:=NextPrime(Random(2^bits-1));
S:=Integers(p);
....
a:=Polynomial([Random(S): x in [1..length]]);
b:=Polynomial([Random(S): x in [1..length]]);
if a eq 0 then
   a := 1;
end if;
....
c:=a*b;
....
d := ExactQuotient(c, a);

I'll try debugging the script.

Bill.

2009/3/20 Bill Hart <goo...@go...>:
> For those interested, here is a graph comparing FLINT and Magma for
> exact division of polynomials in Z/pZ[x].
>
> http://sage.math.washington.edu/home/wbhart/zpdiv.png
>
> Magma has a function for exact division, which I use. FLINT has no
> such function, but I use zmod_poly_div which does not try to compute
> the (zero) remainder. I don't think exact division is any faster in
> this ring anyhow, so Magma probably doesn't get any advantage here.
>
> Incidentally, I ran sloccount on FLINT. Here are the statistics:
>
> Total Physical Source Lines of Code (SLOC)                = 81,285
> Development Effort Estimate, Person-Years (Person-Months) = 20.26 (243.06)
>  (Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
> Schedule Estimate, Years (Months)                         = 1.68 (20.16)
>  (Basic COCOMO model, Months = 2.5 * (person-months**0.38))
> Estimated Average Number of Developers (Effort/Schedule)  = 12.06
> Total Estimated Cost to Develop                           = $ 2,736,230
>  (average salary = $56,286/year, overhead = 2.40).
> SLOCCount, Copyright (C) 2001-2004 David A. Wheeler
> SLOCCount is Open Source Software/Free Software, licensed under the GNU GPL.
> SLOCCount comes with ABSOLUTELY NO WARRANTY, and you are welcome to
> redistribute it under certain conditions as specified by the GNU GPL license;
> see the documentation for details.
> Please credit this data as "generated using David A. Wheeler's 'SLOCCount'."
>
> I like the estimate of 20 person years of development effort and total
> cost of development of $ 2,736,230. :-)
>
> Bill.
>

[flint-devel] Division in Z/pZ[x]

[Bill H. <goo...@go...>]

For those interested, here is a graph comparing FLINT and Magma for
exact division of polynomials in Z/pZ[x].

http://sage.math.washington.edu/home/wbhart/zpdiv.png

Magma has a function for exact division, which I use. FLINT has no
such function, but I use zmod_poly_div which does not try to compute
the (zero) remainder. I don't think exact division is any faster in
this ring anyhow, so Magma probably doesn't get any advantage here.

Incidentally, I ran sloccount on FLINT. Here are the statistics:

Total Physical Source Lines of Code (SLOC)                = 81,285
Development Effort Estimate, Person-Years (Person-Months) = 20.26 (243.06)
 (Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
Schedule Estimate, Years (Months)                         = 1.68 (20.16)
 (Basic COCOMO model, Months = 2.5 * (person-months**0.38))
Estimated Average Number of Developers (Effort/Schedule)  = 12.06
Total Estimated Cost to Develop                           = $ 2,736,230
 (average salary = $56,286/year, overhead = 2.40).
SLOCCount, Copyright (C) 2001-2004 David A. Wheeler
SLOCCount is Open Source Software/Free Software, licensed under the GNU GPL.
SLOCCount comes with ABSOLUTELY NO WARRANTY, and you are welcome to
redistribute it under certain conditions as specified by the GNU GPL license;
see the documentation for details.
Please credit this data as "generated using David A. Wheeler's 'SLOCCount'."

I like the estimate of 20 person years of development effort and total
cost of development of $ 2,736,230. :-)

Bill.

Re: [flint-devel] Z/pZ[x] factoring

[Bill H. <goo...@go...>]

I reckon you could get a 5 times speedup if you implemented the other
algorithm from Sage, if you had linear algebra as fast as Magma. But
last I checked, fflas-ffpack was not there speedwise yet. I had code
running about twice that speed in FLINT and within 30% of what Magma
had. Obviously I didn't implement the other versions of Berlekamp
using it though.

So, maybe you could get a 2 times speedup with fflas-ffpack and
implementing the other Berlekamp algorithms in Sage.

Obviously 2 times is worth it from my point of view. I don't know how
long it will be before I have fast linear algebra. Depends what I get
done when visiting William in a couple of weeks time. But it is likely
to be at least 6 months before I get factoring over Z/pZ really fast.

Bill.

2009/3/20 Burcin Erocal <bu...@er...>:
> On Thu, 19 Mar 2009 23:12:49 +0000
> Bill Hart <goo...@go...> wrote:
>
>> I have been producing some timings for factoring polynomials over
>> Z/pZ[x] against a recent version of Magma.
>>
>> Here is the graph:
>>
>> http://sage.math.washington.edu/home/wbhart/zpfactor.png
>>
>> It appears that Magma is thrashing us, even with all the recent
>> improvements to zmod_poly.
>>
>> I don't know if Magma has been sped up or if we just mistimed in the
>> past, but towards the left of that diagram we are 2-5 times slower
>> than Magma, and on the right hand side it's more like 12 times slower.
>>
>> The Berlekamp algorithm we use is a polynomial one, with a
>> Gauss-Jordan elimination somewhere along the way. But I think there is
>> a version of the algorithm which computes much more using matrix
>> algebra.
>>
>> As FLINT is a long way away from having fast matrices over Z/pZ I
>> think it will be some time before we can beat Magma (again) on this
>> benchmark. This is a little disappointing, but I'm sure it can be
>> fixed in time.
>
> Even if it's not an option for the main FLINT relase, we could patch
> FLINT in Sage to use fflas-ffpack from linbox to get fast linear
> algebra over Z/pZ.
>
> Do you think it's worth the time to try implementing this other version
> you mention? What do the factorization experts say? Andy?
>
> Cheers,
> Burcin
>
> ------------------------------------------------------------------------------
> Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are
> powering Web 2.0 with engaging, cross-platform capabilities. Quickly and
> easily build your RIAs with Flex Builder, the Eclipse(TM)based development
> software that enables intelligent coding and step-through debugging.
> Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel
>

Re: [flint-devel] Z/pZ[x] factoring

[Burcin E. <bu...@er...>]

On Thu, 19 Mar 2009 23:12:49 +0000
Bill Hart <goo...@go...> wrote:

> I have been producing some timings for factoring polynomials over
> Z/pZ[x] against a recent version of Magma.
> 
> Here is the graph:
> 
> http://sage.math.washington.edu/home/wbhart/zpfactor.png
> 
> It appears that Magma is thrashing us, even with all the recent
> improvements to zmod_poly.
> 
> I don't know if Magma has been sped up or if we just mistimed in the
> past, but towards the left of that diagram we are 2-5 times slower
> than Magma, and on the right hand side it's more like 12 times slower.
> 
> The Berlekamp algorithm we use is a polynomial one, with a
> Gauss-Jordan elimination somewhere along the way. But I think there is
> a version of the algorithm which computes much more using matrix
> algebra.
> 
> As FLINT is a long way away from having fast matrices over Z/pZ I
> think it will be some time before we can beat Magma (again) on this
> benchmark. This is a little disappointing, but I'm sure it can be
> fixed in time.

Even if it's not an option for the main FLINT relase, we could patch
FLINT in Sage to use fflas-ffpack from linbox to get fast linear
algebra over Z/pZ.

Do you think it's worth the time to try implementing this other version
you mention? What do the factorization experts say? Andy?

Cheers,
Burcin

[flint-devel] Multiplication in Z/pZ[x]

[Bill H. <goo...@go...>]

Now that we have switched to zn_poly for multiplication of polynomials
over Z/pZ things are really superbly fast.

Here is a graph comparing what we have now with Magma:

http://sage.math.washington.edu/home/wbhart/zpmul.png

The brightest points are where we are now TEN times faster than Magma.

Bill.

[flint-devel] Z/pZ[x] factoring

[Bill H. <goo...@go...>]

I have been producing some timings for factoring polynomials over
Z/pZ[x] against a recent version of Magma.

Here is the graph:

http://sage.math.washington.edu/home/wbhart/zpfactor.png

It appears that Magma is thrashing us, even with all the recent
improvements to zmod_poly.

I don't know if Magma has been sped up or if we just mistimed in the
past, but towards the left of that diagram we are 2-5 times slower
than Magma, and on the right hand side it's more like 12 times slower.

The Berlekamp algorithm we use is a polynomial one, with a
Gauss-Jordan elimination somewhere along the way. But I think there is
a version of the algorithm which computes much more using matrix
algebra.

As FLINT is a long way away from having fast matrices over Z/pZ I
think it will be some time before we can beat Magma (again) on this
benchmark. This is a little disappointing, but I'm sure it can be
fixed in time.

Bill.

[flint-devel] MPIR 1.0.0 release

[Bill H. <goo...@go...>]

We've just put up what will likely be the final release for MPIR 1.0.0. at:

http://www.mpir.org/

* MUCH faster AMD K8/K10 assembly support
* Significantly faster Core 2 assembly support
* Numerous fixes which mean faster code/build support for other x86_64 systems
* Lot's more...

We are now just waiting on a Sage spkg and the usual testing that goes
with that, and we will declare it the final 1.0.0 release.

Build test success/failure reports on any system are accepted gratefully at:

http://groups.google.com/group/mpir-devel/browse_thread/thread/ff67399304d03f5b

It helps if you can give the output of:

* gcc -v
* cat /proc/cpuinfo (if available)

Bill.

Re: [flint-devel] New version of FLINT (1.2.0) released

[Burcin E. <bu...@er...>]

On Sat, 14 Mar 2009 12:10:38 -0700 (PDT)
William Hart <ha...@ya...> wrote:

> 
> I've issued FLINT 1.2.1 which should fix all the issues you noted. It
> now builds fine for me. Please let me know if it does not for you.
> 
> Bill.

Thanks, it works. 

All (FLINT and sage) tests pass on my laptop and sage.math. The new
package is available here:

http://sage.math.washington.edu/home/burcin/flint/flint-1.2.1.spkg

and waiting for review here:

http://trac.sagemath.org/sage_trac/ticket/5240


Cheers,

Burcin

Re: [flint-devel] New version of FLINT (1.2.0) released

[William H. <ha...@ya...>]

I've issued FLINT 1.2.1 which should fix all the issues you noted. It now builds fine for me. Please let me know if it does not for you.

Bill.


--- On Sun, 3/15/09, Bill Hart <goo...@go...> wrote:

> From: Bill Hart <goo...@go...>
> Subject: Re: [flint-devel] New version of FLINT (1.2.0) released
> To: "Development list for FLINT" <fli...@li...>
> Date: Sunday, March 15, 2009, 1:58 AM
> Hi Burcin,
> 
> Omp.h can be removed. It's for openmp.
> 
> I forgot to test it with NTL, thus the missing files.
> I'm away from my
> computer ATM but if you want to repair it, remove those two
> #includes
> from NTL-interface.c and remove the functions that use them
> in
> NTL-interface.c and the relevant includes and test
> functions in
> NTL-interface-test.c.
> 
> All the F_mpz stuff is FLINT 2.0 and can be removed without
> affecting
> the rest of FLINT 1.2. I'll issue a fix as soon as I
> get computer
> access again.
> 
> Bill.
> On 14/03/2009, Burcin Erocal <bu...@er...>
> wrote:
> > Hi Bill,
> >
> > On Tue, 10 Mar 2009 20:05:31 +0000
> > Bill Hart <goo...@go...> wrote:
> >
> >> I have just released FLINT version 1.2.0. It is
> available at
> >> http://www.flintlib.org/
> >
> > While trying to make an spkg for Sage, I got the
> following:
> >
> > gcc -std=c99 -I   -O3 -c fmpz_poly.c -o fmpz_poly.o
> > fmpz_poly.c:32:17: error: omp.h: No such file or
> directory
> > make: *** [fmpz_poly.o] Error 1
> >
> > Is omp.h a typo for gmp.h? It is also included in
> fmpz_poly-test.c.
> >
> > It seems that the files F_mpz.h and F_mpz_mat.h
> mentioned in
> > NTL-interface.cpp are not a part of the tarball
> either. Continuing the build
> > after replacing omp.h with gmp.h still doesn't
> work, since g++ complains
> > about F_mpz_t and F_mpz_mat_t not being declared
> anywhere.
> >
> >
> > Cheers,
> > Burcin
> >
> >
> ------------------------------------------------------------------------------
> > Apps built with the Adobe(R) Flex(R) framework and
> Flex Builder(TM) are
> > powering Web 2.0 with engaging, cross-platform
> capabilities. Quickly and
> > easily build your RIAs with Flex Builder, the
> Eclipse(TM)based development
> > software that enables intelligent coding and
> step-through debugging.
> > Download the free 60 day trial.
> http://p.sf.net/sfu/www-adobe-com
> > _______________________________________________
> > flint-devel mailing list
> > fli...@li...
> >
> https://lists.sourceforge.net/lists/listinfo/flint-devel
> >
> 
> ------------------------------------------------------------------------------
> Apps built with the Adobe(R) Flex(R) framework and Flex
> Builder(TM) are
> powering Web 2.0 with engaging, cross-platform
> capabilities. Quickly and
> easily build your RIAs with Flex Builder, the
> Eclipse(TM)based development
> software that enables intelligent coding and step-through
> debugging.
> Download the free 60 day trial.
> http://p.sf.net/sfu/www-adobe-com
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel


      

Re: [flint-devel] New version of FLINT (1.2.0) released

[Bill H. <goo...@go...>]

Hi Burcin,

Omp.h can be removed. It's for openmp.

I forgot to test it with NTL, thus the missing files. I'm away from my
computer ATM but if you want to repair it, remove those two #includes
from NTL-interface.c and remove the functions that use them in
NTL-interface.c and the relevant includes and test functions in
NTL-interface-test.c.

All the F_mpz stuff is FLINT 2.0 and can be removed without affecting
the rest of FLINT 1.2. I'll issue a fix as soon as I get computer
access again.

Bill.
On 14/03/2009, Burcin Erocal <bu...@er...> wrote:
> Hi Bill,
>
> On Tue, 10 Mar 2009 20:05:31 +0000
> Bill Hart <goo...@go...> wrote:
>
>> I have just released FLINT version 1.2.0. It is available at
>> http://www.flintlib.org/
>
> While trying to make an spkg for Sage, I got the following:
>
> gcc -std=c99 -I   -O3 -c fmpz_poly.c -o fmpz_poly.o
> fmpz_poly.c:32:17: error: omp.h: No such file or directory
> make: *** [fmpz_poly.o] Error 1
>
> Is omp.h a typo for gmp.h? It is also included in fmpz_poly-test.c.
>
> It seems that the files F_mpz.h and F_mpz_mat.h mentioned in
> NTL-interface.cpp are not a part of the tarball either. Continuing the build
> after replacing omp.h with gmp.h still doesn't work, since g++ complains
> about F_mpz_t and F_mpz_mat_t not being declared anywhere.
>
>
> Cheers,
> Burcin
>
> ------------------------------------------------------------------------------
> Apps built with the Adobe(R) Flex(R) framework and Flex Builder(TM) are
> powering Web 2.0 with engaging, cross-platform capabilities. Quickly and
> easily build your RIAs with Flex Builder, the Eclipse(TM)based development
> software that enables intelligent coding and step-through debugging.
> Download the free 60 day trial. http://p.sf.net/sfu/www-adobe-com
> _______________________________________________
> flint-devel mailing list
> fli...@li...
> https://lists.sourceforge.net/lists/listinfo/flint-devel
>

Re: [flint-devel] New version of FLINT (1.2.0) released

[Burcin E. <bu...@er...>]

Hi Bill,

On Tue, 10 Mar 2009 20:05:31 +0000
Bill Hart <goo...@go...> wrote:

> I have just released FLINT version 1.2.0. It is available at
> http://www.flintlib.org/

While trying to make an spkg for Sage, I got the following:

gcc -std=c99 -I   -O3 -c fmpz_poly.c -o fmpz_poly.o
fmpz_poly.c:32:17: error: omp.h: No such file or directory
make: *** [fmpz_poly.o] Error 1

Is omp.h a typo for gmp.h? It is also included in fmpz_poly-test.c.

It seems that the files F_mpz.h and F_mpz_mat.h mentioned in NTL-interface.cpp are not a part of the tarball either. Continuing the build after replacing omp.h with gmp.h still doesn't work, since g++ complains about F_mpz_t and F_mpz_mat_t not being declared anywhere.


Cheers,
Burcin

[flint-devel] New version of FLINT (1.2.0) released

[Bill H. <goo...@go...>]

I have just released FLINT version 1.2.0. It is available at
http://www.flintlib.org/

This is a major new version, including the new features:

* Incorporation of David Harvey's zn_poly-0.8 (it is now used to speed
up the zmod_poly module - users should notice a significant speed
increase for all polynomials over Z/nZ and the modular fmpz_poly Z[x]
functions). zn_poly is now included with FLINT and builds
automatically as part of FLINT and is thus no longer a library
dependency of FLINT.

* New fmpz_poly_is_squarefree function.

* New fmpz_poly_pseudo_rem function.

* New fmpz_poly_signature function (thanks to William Stein for
prompting me to implement this).

* Thread safety of large parts of FLINT.

* Numerous speedups.

* Numerous bug fixes.

The full list of changes is available in the file CHANGES in the tarball.

Bill.

Re: [flint-devel] Inclusion of zn_poly in FLINT

[Bill H. <goo...@go...>]

David tells me that in fact zn_poly *does* reuse the FFT. I got mixed up there.

I tried some larger divisions and more of them to minimise the effect
of random generation. But it is basically inconclusive. There isn't a
lot of difference in speed between FLINT and zn_poly for this
algorithm now that everything else has been made faster. Sometime
FLINT appears to be a few seconds faster (in a 100 or 200 second test)
and sometimes zn_poly is faster.

This is not very scientific of me, and zn_poly probably does beat
FLINT for polynomials of certain sizes, so I'll just leave zn_poly in
for now for this algorithm.

As far as I am concerned, that brings the inclusion of zn_poly into
FLINT to a close. It makes a pretty impressive improvement.

Here are the best time improvements (some times - not listed - appear
to have gone up slightly, but that is surely to do with random seeds -
some of the times below are obviously decreased far too much to be to
do with randomness):

Testing zmod_poly_mul()... Cpu = 2660 ms  Wall = 2668 ms ... ok
Testing zmod_poly_mul()... Cpu = 2310 ms  Wall = 2318 ms ... ok

Testing zmod_poly_mul_trunc_left_n()... Cpu = 2600 ms  Wall = 2601 ms ... ok
Testing zmod_poly_mul_trunc_left_n()... Cpu = 2520 ms  Wall = 2511 ms ... ok

Testing zmod_poly_scalar_mul()... Cpu = 220 ms  Wall = 218 ms ... ok
Testing zmod_poly_scalar_mul()... Cpu = 170 ms  Wall = 167 ms ... ok

Testing zmod_poly_make_monic()... Cpu = 440 ms  Wall = 440 ms ... ok
Testing zmod_poly_make_monic()... Cpu = 330 ms  Wall = 331 ms ... ok

Testing zmod_poly_divrem_classical()... Cpu = 1640 ms  Wall = 1645 ms ... ok
Testing zmod_poly_divrem_classical()... Cpu = 1020 ms  Wall = 1028 ms ... ok

Testing zmod_poly_div_classical()... Cpu = 1870 ms  Wall = 1877 ms ... ok
Testing zmod_poly_div_classical()... Cpu = 1180 ms  Wall = 1186 ms ... ok

Testing zmod_poly_div()... Cpu = 5760 ms  Wall = 5759 ms ... ok
Testing zmod_poly_div()... Cpu = 5340 ms  Wall = 5337 ms ... ok

Testing zmod_poly_divrem_divconquer()... Cpu = 1720 ms  Wall = 1722 ms ... ok
Testing zmod_poly_divrem_divconquer()... Cpu = 1340 ms  Wall = 1338 ms ... ok

Testing zmod_poly_div_divconquer()... Cpu = 1950 ms  Wall = 1949 ms ... ok
Testing zmod_poly_div_divconquer()... Cpu = 1460 ms  Wall = 1461 ms ... ok

Testing zmod_poly_div_divconquer_recursive()... Cpu = 1940 ms  Wall =
1935 ms ... ok
Testing zmod_poly_div_divconquer_recursive()... Cpu = 1490 ms  Wall =
1489 ms ... ok

Testing zmod_poly_half_gcd_iter()... Cpu = 2310 ms  Wall = 2307 ms ... ok
Testing zmod_poly_half_gcd_iter()... Cpu = 1910 ms  Wall = 1913 ms ... ok

Testing zmod_poly_gcd_hgcd()... Cpu = 6670 ms  Wall = 6667 ms ... ok
Testing zmod_poly_gcd_hgcd()... Cpu = 5390 ms  Wall = 5390 ms ... ok

Testing zmod_poly_half_gcd()... Cpu = 1970 ms  Wall = 1974 ms ... ok
Testing zmod_poly_half_gcd()... Cpu = 1650 ms  Wall = 1645 ms ... ok

Testing zmod_poly_gcd()... Cpu = 3830 ms  Wall = 3835 ms ... ok
Testing zmod_poly_gcd()... Cpu = 3130 ms  Wall = 3137 ms ... ok

Testing zmod_poly_gcd_invert()... Cpu = 5190 ms  Wall = 5186 ms ... ok
Testing zmod_poly_gcd_invert()... Cpu = 4590 ms  Wall = 4585 ms ... ok

Testing zmod_poly_xgcd()... Cpu = 4410 ms  Wall = 4413 ms ... ok
Testing zmod_poly_xgcd()... Cpu = 3800 ms  Wall = 3797 ms ... ok

Testing zmod_poly_powmod()... Cpu = 4470 ms  Wall = 4470 ms ... ok
Testing zmod_poly_powmod()... Cpu = 4030 ms  Wall = 4032 ms ... ok

Testing zmod_poly_isirreducible()... Cpu = 4700 ms  Wall = 4704 ms ... ok
Testing zmod_poly_isirreducible()... Cpu = 3790 ms  Wall = 3791 ms ... ok

Testing zmod_poly_factor_berlekamp()... Cpu = 1720 ms  Wall = 1721 ms ... ok
Testing zmod_poly_factor_berlekamp()... Cpu = 1420 ms  Wall = 1412 ms ... ok

Testing zmod_poly_factor()... Cpu = 2910 ms  Wall = 2925 ms ... ok
Testing zmod_poly_factor()... Cpu = 2680 ms  Wall = 2681 ms ... ok

Testing zmod_poly_2x2_mat_mul_classical_strassen()... Cpu = 790 ms
Wall = 783 ms ... ok
Testing zmod_poly_2x2_mat_mul_classical_strassen()... Cpu = 450 ms
Wall = 453 ms ... ok

Testing zmod_poly_2x2_mat_mul()... Cpu = 2280 ms  Wall = 2285 ms ... ok
Testing zmod_poly_2x2_mat_mul()... Cpu = 1540 ms  Wall = 1535 ms ... ok

Bill.

2009/3/2 Bill Hart <goo...@go...>:
> I've tried some different cutoffs and the cutoff used seems OK.
>
> The test timings are somewhat dependent on the random seed, which
> changes when the code is recompiled. It might be that.
>
> Or it might be that FLINT uses a better algorithm for the inversion.
> It can use the same FFT for truncated multiply and middle product,
> which zn_poly can't. That may account for it.
>
> I'll experiment with some longer runs later tonight. Gotta go out now.
>
> Bill.
>
> 2009/3/2 Bill Hart <goo...@go...>:
>> I've now switched to zn_poly's newton inversion for polynomials of
>> length > 2000.
>>
>> Times:
>>
>>> BEFORE:
>>
>>> Testing zmod_poly_divrem_newton()... Cpu = 2480 ms  Wall = 2487 ms ... ok
>>> Testing zmod_poly_divrem()... Cpu = 8510 ms  Wall = 8506 ms ... ok
>>> Testing zmod_poly_div_classical()... Cpu = 1160 ms  Wall = 1166 ms ... ok
>>> Testing zmod_poly_div()... Cpu = 4560 ms  Wall = 4561 ms ... ok
>>> Testing zmod_poly_divrem_divconquer()... Cpu = 1300 ms  Wall = 1307 ms ... ok
>>> Testing zmod_poly_div_divconquer()... Cpu = 1430 ms  Wall = 1431 ms ... ok
>>> Testing zmod_poly_div_divconquer_recursive()... Cpu = 1420 ms  Wall =
>>> 1421 ms ... ok
>>> Testing zmod_poly_newton_invert_basecase()... Cpu = 470 ms  Wall = 468 ms ... ok
>>> Testing zmod_poly_newton_invert()... Cpu = 9700 ms  Wall = 9699 ms ... ok
>>> Testing zmod_poly_div_series()... Cpu = 1200 ms  Wall = 1202 ms ... ok
>>> Testing zmod_poly_div_newton()... Cpu = 1090 ms  Wall = 1088 ms ... ok
>>> Testing zmod_poly_gcd_euclidean()... Cpu = 6300 ms  Wall = 6300 ms ... ok
>>> Testing zmod_poly_half_gcd_iter()... Cpu = 1870 ms  Wall = 1868 ms ... ok
>>> Testing zmod_poly_gcd_hgcd()... Cpu = 5240 ms  Wall = 5243 ms ... ok
>>> Testing zmod_poly_half_gcd()... Cpu = 1630 ms  Wall = 1630 ms ... ok
>>> Testing zmod_poly_gcd()... Cpu = 3070 ms  Wall = 3068 ms ... ok
>>> Testing zmod_poly_gcd_invert()... Cpu = 4410 ms  Wall = 4410 ms ... ok
>>> Testing zmod_poly_xgcd()... Cpu = 3700 ms  Wall = 3704 ms ... ok
>>> Testing zmod_poly_resultant_euclidean()... Cpu = 840 ms  Wall = 839 ms ... ok
>>> Testing zmod_poly_mulmod()... Cpu = 2340 ms  Wall = 2339 ms ... ok
>>> Testing zmod_poly_powmod()... Cpu = 3630 ms  Wall = 3629 ms ... ok
>>> Testing zmod_poly_isirreducible()... Cpu = 3730 ms  Wall = 3731 ms ... ok
>>> Testing zmod_poly_factor_berlekamp()... Cpu = 1390 ms  Wall = 1390 ms ... ok
>>> Testing zmod_poly_factor_square_free()... Cpu = 2740 ms  Wall = 2734 ms ... ok
>>> Testing zmod_poly_factor()... Cpu = 2360 ms  Wall = 2359 ms ... ok
>>>
>>
>> AFTER:
>>
>> Testing zmod_poly_divrem_newton()... Cpu = 2970 ms  Wall = 2970 ms ... ok
>> Testing zmod_poly_divrem()... Cpu = 9650 ms  Wall = 9655 ms ... ok
>> Testing zmod_poly_div_classical()... Cpu = 1170 ms  Wall = 1164 ms ... ok
>> Testing zmod_poly_div()... Cpu = 5240 ms  Wall = 5242 ms ... ok
>> Testing zmod_poly_divrem_divconquer()... Cpu = 1310 ms  Wall = 1316 ms ... ok
>> Testing zmod_poly_div_divconquer()... Cpu = 1440 ms  Wall = 1438 ms ... ok
>> Testing zmod_poly_div_divconquer_recursive()... Cpu = 1430 ms  Wall =
>> 1430 ms ... ok
>> Testing zmod_poly_newton_invert_basecase()... Cpu = 470 ms  Wall = 469 ms ... ok
>> Testing zmod_poly_newton_invert()... Cpu = 8470 ms  Wall = 8466 ms ... ok
>> Testing zmod_poly_div_series()... Cpu = 1430 ms  Wall = 1430 ms ... ok
>> Testing zmod_poly_div_newton()... Cpu = 1400 ms  Wall = 1404 ms ... ok
>> Testing zmod_poly_gcd_euclidean()... Cpu = 6300 ms  Wall = 6297 ms ... ok
>> Testing zmod_poly_half_gcd_iter()... Cpu = 1860 ms  Wall = 1862 ms ... ok
>> Testing zmod_poly_gcd_hgcd()... Cpu = 5270 ms  Wall = 5272 ms ... ok
>> Testing zmod_poly_half_gcd()... Cpu = 1620 ms  Wall = 1621 ms ... ok
>> Testing zmod_poly_gcd()... Cpu = 3090 ms  Wall = 3090 ms ... ok
>> Testing zmod_poly_gcd_invert()... Cpu = 4520 ms  Wall = 4520 ms ... ok
>> Testing zmod_poly_xgcd()... Cpu = 3700 ms  Wall = 3693 ms ... ok
>> Testing zmod_poly_resultant_euclidean()... Cpu = 830 ms  Wall = 837 ms ... ok
>> Testing zmod_poly_mulmod()... Cpu = 2920 ms  Wall = 2915 ms ... ok
>> Testing zmod_poly_powmod()... Cpu = 3960 ms  Wall = 3966 ms ... ok
>> Testing zmod_poly_isirreducible()... Cpu = 3760 ms  Wall = 3754 ms ... ok
>> Testing zmod_poly_factor_berlekamp()... Cpu = 1400 ms  Wall = 1398 ms ... ok
>> Testing zmod_poly_factor_square_free()... Cpu = 3090 ms  Wall = 3091 ms ... ok
>> Testing zmod_poly_factor()... Cpu = 2640 ms  Wall = 2637 ms ... ok
>>
>> I guess the FLINT crossover is wrong for zn_poly. The newton_invert
>> time went down, but the time for everything else that relies on it
>> went up. I'll have to have a fiddle this evening.
>>
>> Bill.
>>
>

Re: [flint-devel] Inclusion of zn_poly in FLINT

[Bill H. <goo...@go...>]

I've tried some different cutoffs and the cutoff used seems OK.

The test timings are somewhat dependent on the random seed, which
changes when the code is recompiled. It might be that.

Or it might be that FLINT uses a better algorithm for the inversion.
It can use the same FFT for truncated multiply and middle product,
which zn_poly can't. That may account for it.

I'll experiment with some longer runs later tonight. Gotta go out now.

Bill.

2009/3/2 Bill Hart <goo...@go...>:
> I've now switched to zn_poly's newton inversion for polynomials of
> length > 2000.
>
> Times:
>
>> BEFORE:
>
>> Testing zmod_poly_divrem_newton()... Cpu = 2480 ms  Wall = 2487 ms ... ok
>> Testing zmod_poly_divrem()... Cpu = 8510 ms  Wall = 8506 ms ... ok
>> Testing zmod_poly_div_classical()... Cpu = 1160 ms  Wall = 1166 ms ... ok
>> Testing zmod_poly_div()... Cpu = 4560 ms  Wall = 4561 ms ... ok
>> Testing zmod_poly_divrem_divconquer()... Cpu = 1300 ms  Wall = 1307 ms ... ok
>> Testing zmod_poly_div_divconquer()... Cpu = 1430 ms  Wall = 1431 ms ... ok
>> Testing zmod_poly_div_divconquer_recursive()... Cpu = 1420 ms  Wall =
>> 1421 ms ... ok
>> Testing zmod_poly_newton_invert_basecase()... Cpu = 470 ms  Wall = 468 ms ... ok
>> Testing zmod_poly_newton_invert()... Cpu = 9700 ms  Wall = 9699 ms ... ok
>> Testing zmod_poly_div_series()... Cpu = 1200 ms  Wall = 1202 ms ... ok
>> Testing zmod_poly_div_newton()... Cpu = 1090 ms  Wall = 1088 ms ... ok
>> Testing zmod_poly_gcd_euclidean()... Cpu = 6300 ms  Wall = 6300 ms ... ok
>> Testing zmod_poly_half_gcd_iter()... Cpu = 1870 ms  Wall = 1868 ms ... ok
>> Testing zmod_poly_gcd_hgcd()... Cpu = 5240 ms  Wall = 5243 ms ... ok
>> Testing zmod_poly_half_gcd()... Cpu = 1630 ms  Wall = 1630 ms ... ok
>> Testing zmod_poly_gcd()... Cpu = 3070 ms  Wall = 3068 ms ... ok
>> Testing zmod_poly_gcd_invert()... Cpu = 4410 ms  Wall = 4410 ms ... ok
>> Testing zmod_poly_xgcd()... Cpu = 3700 ms  Wall = 3704 ms ... ok
>> Testing zmod_poly_resultant_euclidean()... Cpu = 840 ms  Wall = 839 ms ... ok
>> Testing zmod_poly_mulmod()... Cpu = 2340 ms  Wall = 2339 ms ... ok
>> Testing zmod_poly_powmod()... Cpu = 3630 ms  Wall = 3629 ms ... ok
>> Testing zmod_poly_isirreducible()... Cpu = 3730 ms  Wall = 3731 ms ... ok
>> Testing zmod_poly_factor_berlekamp()... Cpu = 1390 ms  Wall = 1390 ms ... ok
>> Testing zmod_poly_factor_square_free()... Cpu = 2740 ms  Wall = 2734 ms ... ok
>> Testing zmod_poly_factor()... Cpu = 2360 ms  Wall = 2359 ms ... ok
>>
>
> AFTER:
>
> Testing zmod_poly_divrem_newton()... Cpu = 2970 ms  Wall = 2970 ms ... ok
> Testing zmod_poly_divrem()... Cpu = 9650 ms  Wall = 9655 ms ... ok
> Testing zmod_poly_div_classical()... Cpu = 1170 ms  Wall = 1164 ms ... ok
> Testing zmod_poly_div()... Cpu = 5240 ms  Wall = 5242 ms ... ok
> Testing zmod_poly_divrem_divconquer()... Cpu = 1310 ms  Wall = 1316 ms ... ok
> Testing zmod_poly_div_divconquer()... Cpu = 1440 ms  Wall = 1438 ms ... ok
> Testing zmod_poly_div_divconquer_recursive()... Cpu = 1430 ms  Wall =
> 1430 ms ... ok
> Testing zmod_poly_newton_invert_basecase()... Cpu = 470 ms  Wall = 469 ms ... ok
> Testing zmod_poly_newton_invert()... Cpu = 8470 ms  Wall = 8466 ms ... ok
> Testing zmod_poly_div_series()... Cpu = 1430 ms  Wall = 1430 ms ... ok
> Testing zmod_poly_div_newton()... Cpu = 1400 ms  Wall = 1404 ms ... ok
> Testing zmod_poly_gcd_euclidean()... Cpu = 6300 ms  Wall = 6297 ms ... ok
> Testing zmod_poly_half_gcd_iter()... Cpu = 1860 ms  Wall = 1862 ms ... ok
> Testing zmod_poly_gcd_hgcd()... Cpu = 5270 ms  Wall = 5272 ms ... ok
> Testing zmod_poly_half_gcd()... Cpu = 1620 ms  Wall = 1621 ms ... ok
> Testing zmod_poly_gcd()... Cpu = 3090 ms  Wall = 3090 ms ... ok
> Testing zmod_poly_gcd_invert()... Cpu = 4520 ms  Wall = 4520 ms ... ok
> Testing zmod_poly_xgcd()... Cpu = 3700 ms  Wall = 3693 ms ... ok
> Testing zmod_poly_resultant_euclidean()... Cpu = 830 ms  Wall = 837 ms ... ok
> Testing zmod_poly_mulmod()... Cpu = 2920 ms  Wall = 2915 ms ... ok
> Testing zmod_poly_powmod()... Cpu = 3960 ms  Wall = 3966 ms ... ok
> Testing zmod_poly_isirreducible()... Cpu = 3760 ms  Wall = 3754 ms ... ok
> Testing zmod_poly_factor_berlekamp()... Cpu = 1400 ms  Wall = 1398 ms ... ok
> Testing zmod_poly_factor_square_free()... Cpu = 3090 ms  Wall = 3091 ms ... ok
> Testing zmod_poly_factor()... Cpu = 2640 ms  Wall = 2637 ms ... ok
>
> I guess the FLINT crossover is wrong for zn_poly. The newton_invert
> time went down, but the time for everything else that relies on it
> went up. I'll have to have a fiddle this evening.
>
> Bill.
>