pynac 0.2.6 is out

[Burcin Erocal]

Hi,

After fixing a couple of serious issues last week, I released 0.2.6
today. Here are the changes:

- Fix infinite loop in content normalization of add objects within
mul::eval [(Pynac issue
#12)](http://hg.pynac.org/pynac/issue/12/segfault-while-trying-to-normalize-leading)
[(Sage issue
#13609)](http://trac.sagemath.org/sage_trac/ticket/13609)
- Fix fallout from infinities rewrite where expairseq eagerly
simplified infinity objects in its contructor.
[(Pynac issue
#14)](http://hg.pynac.org/pynac/issue/14/expairseq-constructor-cancels-infinity)
[(Sage issue
#13587)](http://trac.sagemath.org/sage_trac/ticket/13587)
- Fix printing of parenthesis around exponents of power objects.
(Reported and fixed by Sebastien Gouezel.)


You can view the patches on bitbucket as usual:

http://hg.pynac.org/pynac/changesets

Note that after pynac.sagemath.org being down for quite a while, we
have a new website at

http://pynac.org/


The repository for the web pages is also available:

http://hg.pynac.org/www

Static html pages are generated from the content there using Jekyll:

https://github.com/mojombo/jekyll

Any help with web design would be much appreciated. As you can see, the
site really needs a makeover. :)


My plans for the next Pynac versions are...

- 0.3.0 with the order patches
- 0.4.0 with Titus' reimplementation of number classes


Cheers,
Burcin

[Jean-Pierre Flori]

On Tuesday, November 20, 2012 5:04:46 PM UTC+1, Burcin Erocal wrote:

Hi,

After fixing a couple of serious issues last week, I released 0.2.6
today. Here are the changes:

 - Fix infinite loop in content normalization of add objects within
   mul::eval [(Pynac issue
   #12)](http://hg.pynac.org/pynac/issue/12/segfault-while-trying-to-normalize-leading)
   [(Sage issue
   #13609)](http://trac.sagemath.org/sage_trac/ticket/13609)
 - Fix fallout from infinities rewrite where expairseq eagerly
   simplified infinity objects in its contructor.
   [(Pynac issue
   #14)](http://hg.pynac.org/pynac/issue/14/expairseq-constructor-cancels-infinity)
   [(Sage issue
   #13587)](http://trac.sagemath.org/sage_trac/ticket/13587)
 - Fix printing of parenthesis around exponents of power objects.
   (Reported and fixed by Sebastien Gouezel.)

 
Great news, did you open a Sage ticket for this?

My plans for the next Pynac versions are...

 - 0.3.0 with the order patches

 
Great to hear as well, don't hesitate to contact me again when you begin to work on this if you need help for testing.

[Burcin Erocal]

Hi Jean-Pierre,

On Tue, 20 Nov 2012 08:53:47 -0800 (PST)
Jean-Pierre Flori <jpf...@gmail.com> wrote:

> On Tuesday, November 20, 2012 5:04:46 PM UTC+1, Burcin Erocal wrote:
> >
> > After fixing a couple of serious issues last week, I released 0.2.6
> > today. Here are the changes:

<snip changelog>

>
> Great news, did you open a Sage ticket for this?

Yes, I should have mentioned that. I'm new in this release announcement
business.

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

> My plans for the next Pynac versions are...
> >
> > - 0.3.0 with the order patches
> >
>
> Great to hear as well, don't hesitate to contact me again when you
> begin to work on this if you need help for testing.

Thanks. I don't recall if there were any issues left actually. It will
take some time to get back into this problem.

I just rebased my patch queue to 0.2.6 without any trouble. So at least
all the patches for pynac are still good. The doctest patches for Sage
will be trouble. I will have a go at rebasing them on Sage 5.5.rc0 till
next week.


Cheers,
Burcin

[kcrisman]

Static html pages are generated from the content there using Jekyll:

https://github.com/mojombo/jekyll

Any help with web design would be much appreciated. As you can see, the
site really needs a makeover. :)

The link to "the GiNaC developers" needs an extra www to function properly for some reason. 

[Burcin Erocal]

On Tue, 20 Nov 2012 13:49:32 -0800 (PST)
kcrisman <kcri...@gmail.com> wrote:

> The link to "the GiNaC developers <http://ginac.de/People.html>"

> needs an extra www to function properly for some reason.

Fixed! Thanks for the report.

Cheers,
Burcin

[Jean-Pierre Flori]

On Tuesday, November 20, 2012 6:08:29 PM UTC+1, Burcin Erocal wrote:

Hi Jean-Pierre,

On Tue, 20 Nov 2012 08:53:47 -0800 (PST)
Jean-Pierre Flori <jpf...@gmail.com> wrote:

> On Tuesday, November 20, 2012 5:04:46 PM UTC+1, Burcin Erocal wrote:
> >
> > After fixing a couple of serious issues last week, I released 0.2.6
> > today. Here are the changes:
<snip changelog>
>  
> Great news, did you open a Sage ticket for this?

Yes, I should have mentioned that. I'm new in this release announcement
business.

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

I've posted an updated spkg waiting for review up there, positive reviewed one of the related ticket and slightly ranted in another one.
 

[Burcin Erocal]

On Wed, 21 Nov 2012 05:36:30 -0800 (PST)
Jean-Pierre Flori <jpf...@gmail.com> wrote:

> > I've posted an updated spkg waiting for review up there, positive
> > reviewed
> one of the related ticket and slightly ranted in another one.

Thanks!

Your rant led me to reconsider my fix for that ticket.

I am pasting my response on trac here for reference:


I uploaded a new patch with some text

http://trac.sagemath.org/sage_trac/attachment/ticket/13609/trac_13609-gf2_content.take2.patch

To demonstrate the content of the expressions involved, I wrapped
GiNaC's content() method in #13736. This ticket now depends on the
patch there.

Note that multiplying the numerator I give in the doctests by the
content gives

sage: -num.content(c1)*num
c1 + z*c2 + z

which changes the original leading coefficient -1 by coercing it to
GF(2^8).

This does not happen during normalization, since numeric::div_dyn()
is used directly to modify the coefficients. There is a shortcut in
that function to do nothing if we are dividing by 1. Perhaps I should
back out the current fix in Pynac and change numeric::div_dyn() to
disable the shortcut if the characteristic is not 0.

Comments?


Burcin

[Jean-Pierre Flori]

Argh, you just made me realize that you mix strange things in symbolic expressions, e.g.
r*a + t*b where a, b are symbolic, r is something living in a field of char p and t in a field of char q != p.

[Jean-Pierre Flori]

On Wednesday, November 21, 2012 5:20:06 PM UTC+1, Jean-Pierre Flori wrote:

Argh, you just made me realize that you mix strange things in symbolic expressions, e.g.
r*a + t*b where a, b are symbolic, r is something living in a field of char p and t in a field of char q != p.

By the way doing t*(r*a + t*b) yields an ArithmeticError, which is ok, but without further details.

Whereas doing ((r*a + t*b)**2).expand() yields a TypeError with a much more useful message.
And I am kinda scared by (r*a + t*b)**2 without expansion :)

[Burcin Erocal]

On Wed, 21 Nov 2012 08:25:45 -0800 (PST)
Jean-Pierre Flori <jpf...@gmail.com> wrote:

> On Wednesday, November 21, 2012 5:20:06 PM UTC+1, Jean-Pierre Flori
> wrote:
> >
> > Argh, you just made me realize that you mix strange things in
> > symbolic expressions, e.g.
> > r*a + t*b where a, b are symbolic, r is something living in a field
> > of char p and t in a field of char q != p.

We let people shoot themselves in the foot if they wish to. This
approach seems to be everywhere in Python.

> By the way doing t*(r*a + t*b) yields an ArithmeticError, which is
> ok, but without further details.

I fixed this one:

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

The doctests ended up right under those from #13609. So the patch
depends on those. Otherwise, it's a small independent change.

> Whereas doing ((r*a + t*b)**2).expand() yields a TypeError with a
> much more useful message.
> And I am kinda scared by (r*a + t*b)**2 without expansion :)

If you want to play with fire, you are welcome to. :)

The error message is quite informative now:

sage: t = GF(7)(3)
sage: u = GF(5)(4)
sage: var('y')
y
sage: e = t*x + u*y
sage: ee = e^2
sage: ee
(3*x + 4*y)^2
sage: ee.expand()
---------------------------------------------------------------------------
TypeError Traceback (most recent call
last)
...
TypeError: unsupported operand parent(s) for '*': 'Finite Field of size
5' and 'Finite Field of size 7'


Cheers,
Burcin

[Jean-Pierre Flori]

We let people shoot themselves in the foot if they wish to. This
approach seems to be everywhere in Python.

Of course :)

My point is rather of questioning the way things are normalized by Pynac.

When you get something foolish as I suggested, I guess that Sage says the different non-symbolic pieces can not be coerced into a common parent, and so pynac does nothing.

In the original problematic case, you have something in Z and other things in GF(q), so I guess what you do is to ask Sage to coerce all of these somewhere which happens to be GF(q) (or is it Z?) and compute the content there (not really clear how this is done either if we are working in GF(q)), and then multiply the original thing by -1/content (the opposite/inverse is computed in GF(q)) (the multiplication by this computed value is done where?).
In the original example, the problem is that -1 in Z becomes +1 in GF(2^k), and the content is 1 and -1/1 is still 1, and then you multiply the original -1 (in Z) coefficient by 1 (in ??? Z I guess, cause otherwise the result would live in GF(2^k) and be 1 and the original problem would not occur!).

Or do you only consider the "integer part" of things which is mysterious, but let's say you take a representative in 0..p-1 for each coeff of the polynomial representation of GF(q) over GF(p), and compute the gcd of that, and the gcd of the different gcd's and compute its inverse as a similar representative in GF(p), its opposite and multiply by the resulting integer, which would lead to the original bug.

Or content is just something different and specific to ginac?

I should really look at the code, or stop asking stupid questions :)

[Burcin Erocal]

On Wed, 21 Nov 2012 10:03:18 -0800 (PST)
Jean-Pierre Flori <jpf...@gmail.com> wrote:

> > We let people shoot themselves in the foot if they wish to. This
> > approach seems to be everywhere in Python.
> >
> > Of course :)
>
> My point is rather of questioning the way things are normalized by
> Pynac.
>
> When you get something foolish as I suggested, I guess that Sage says
> the different non-symbolic pieces can not be coerced into a common
> parent, and so pynac does nothing.
>
> In the original problematic case, you have something in Z and other
> things in GF(q), so I guess what you do is to ask Sage to coerce all
> of these somewhere which happens to be GF(q) (or is it Z?) and
> compute the content there (not really clear how this is done either
> if we are working in GF(q)), and then multiply the original thing by
> -1/content (the opposite/inverse is computed in GF(q)) (the
> multiplication by this computed value is done where?).
> In the original example, the problem is that -1 in Z becomes +1 in
> GF(2^k), and the content is 1 and -1/1 is still 1, and then you
> multiply the original -1 (in Z) coefficient by 1 (in ??? Z I guess,
> cause otherwise the result would live in GF(2^k) and be 1 and the
> original problem would not occur!).

Right. The arithmetic is done by Sage, so coercion applies as usual.
The result of -1 in ZZ (the coefficient) divided by 1 in GF(2^8)
(-content) is 1 in GF(2^8).

The problem is, numeric::{div,mul}_dyn() choses to ignore multiplication
by anything which is equal to 1 in ZZ. So this normalization is skipped
altogether.

Here is the normalization code:

http://hg.pynac.org/pynac/src/5f14c0386822d8c7448bae2577f3966d3dd35902/ginac/mul.cpp?at=default#cl-730

Here is mul_dyn and div_dyn:

http://hg.pynac.org/pynac/src/5f14c0386822d8c7448bae2577f3966d3dd35902/ginac/numeric.cpp?at=default#cl-1836

> Or do you only consider the "integer part" of things which is
> mysterious, but let's say you take a representative in 0..p-1 for
> each coeff of the polynomial representation of GF(q) over GF(p), and
> compute the gcd of that, and the gcd of the different gcd's and
> compute its inverse as a similar representative in GF(p), its
> opposite and multiply by the resulting integer, which would lead to
> the original bug.
>
> Or content is just something different and specific to ginac?
>
> I should really look at the code, or stop asking stupid questions :)

These are not stupid questions. Unfortunately normalization is a black
art in itself. The correct thing to do is slightly different for each
algebraic domain. When we are dealing with symbolic expressions, it's
unclear altogether. I don't know how GiNaC handles these things either.


I am starting believe more and more that my initial fix is wrong. We
should change numeric::{div,mul}_dyn instead.

Cheers,
Burcin

[Burcin Erocal]

Rebased patches are on trac #9880.

From a brief inspection of doctest output, I think we still have the
random sign problems from factor() and the minpoly time out issue.
Searching for minpoly on trac turns up these tickets:

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

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


I won't have time to look into this in detail at least till next week
though.


Cheers,
Burcin