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