Pynac comparison functions do not provide a SWO

[jpflori]

Here is a short example found by Burcin and reproducing the bug:

b = [var('b_%s'%i) for i in range(4)]

precomp = (2^b_2 + 2)*(2^b_1 + 2^(-b_1) + 2^b_1*2^b_0 - 2^b_1*2^(-b_0)
- 2^(-b_1)*2^b_0 - 2^(-b_1)*2^(-b_0) + 2^b_0 + 2^(-b_0) - 9) + (2^b_1 +
2^(-b_1) + 2^b_1*2^b_0 - 2^b_1*2^(-b_0) - 2^(-b_1)*2^b_0 -
2^(-b_1)*2^(-b_0) + 2^b_0 + 2^(-b_0) - 9)/2^b_2

repl_dict = {b_0: b_0, b_3: b_1, b_2: b_3, b_1: b_2}
P = precomp.substitute(repl_dict)
P.expand() 

This is already being discussed here: http://groups.google.com/group/sage-support/browse_thread/thread/7c85f02c76012722

The following patches are for the Sage library to enable access to the PyNaC order and randomly test that it is a SWO:

Install the package from here: http://boxen.math.washington.edu/home/jpflori/spkg/pynac-0.3.0.spkg

Then apply

1. attachment: trac_9880_pynac_order-sage_5_10_beta2.patch
2. attachment: trac_9880_randomized_testing-sage_5_10_beta2.patch
3. attachment: trac_9880-doctest_for_9046-sage_5_10_beta2.patch
4. attachment: trac_9880-add_doctests-sage_5_10_beta2.patch
5. attachment: trac_9880-fix_doctests-sage_5_10_beta2.take3.patch
6. attachment: trac_9880-review.patch

Depends on #13213
Depends on #9890
Depends on #14550

CC: @kcrisman @zimmermann6

Component: symbolics

Keywords: pynac spkg

Author: Burcin Erocal, Jean-Pierre Flori, Volker Braun

Reviewer: Burcin Erocal, Jean-Pierre Flori

Merged: sage-5.11.beta0

Issue created by migration from https://trac.sagemath.org/ticket/9880

[burcin]

Description changed:

--- 
+++ 
@@ -1,15 +1,17 @@
 Here is a short example found by Burcin and reproducing the bug:
 
+```
 b = [var('b_%s'%i) for i in range(4)]
 
-precomp = (2^b_2 + 2)*(2^b_1 + 2^(-b_1) + 2<sup>b_1*2</sup>b_0 - 2<sup>b_1*2</sup>(-b_0)
-- 2<sup>(-b_1)*2</sup>b_0 - 2<sup>(-b_1)*2</sup>(-b_0) + 2^b_0 + 2^(-b_0) - 9) + (2^b_1 +
-2^(-b_1) + 2<sup>b_1*2</sup>b_0 - 2<sup>b_1*2</sup>(-b_0) - 2<sup>(-b_1)*2</sup>b_0 -
-2<sup>(-b_1)*2</sup>(-b_0) + 2^b_0 + 2^(-b_0) - 9)/2^b_2
+precomp = (2^b_2 + 2)*(2^b_1 + 2^(-b_1) + 2^b_1*2^b_0 - 2^b_1*2^(-b_0)
+- 2^(-b_1)*2^b_0 - 2^(-b_1)*2^(-b_0) + 2^b_0 + 2^(-b_0) - 9) + (2^b_1 +
+2^(-b_1) + 2^b_1*2^b_0 - 2^b_1*2^(-b_0) - 2^(-b_1)*2^b_0 -
+2^(-b_1)*2^(-b_0) + 2^b_0 + 2^(-b_0) - 9)/2^b_2
 
 repl_dict = {b_0: b_0, b_3: b_1, b_2: b_3, b_1: b_2}
 P = precomp.substitute(repl_dict)
 P.expand() 
+```
 
 This is already being discussed here:
 http://groups.google.com/group/sage-support/browse_thread/thread/7c85f02c76012722 

[jpflori]

Description changed:

--- 
+++ 
@@ -12,6 +12,4 @@
 P = precomp.substitute(repl_dict)
 P.expand() 
 ```
-
-This is already being discussed here:
-http://groups.google.com/group/sage-support/browse_thread/thread/7c85f02c76012722 
+This is already being discussed here: http://groups.google.com/group/sage-support/browse_thread/thread/7c85f02c76012722

[jpflori]

The bug happened because of the comparison functions which are used in a call to std::sort.

I have finally looked at the comparison functions and exchanging :

cmpval = seq[0].coeff.compare(other.exponent);

by

cmpval = -seq[0].coeff.compare(other.exponent);

in mul::compare_pow (mul.cpp:1265) seems to prevent the above bug from happening.

It seems to fit better with the change made by William Stein in power::compare_same_type (power.cpp:951).

However it doesn't mean the problem is completely solved...

I'll try to take a deeper look at the comparison functions at some point.

I tested the above fix with pynac 0.2.1.

[jpflori]

Attachment: trac9880_pynac_order_burcin_original.patch.gz

Burcin original patch

[jpflori]

Patch to apply on top of the other one

[jpflori]

comment:3

Attachment: trac9880-pynac_order_jp_new.patch.gz

We've been working on a patch to fix the issue.

Original discussion is here:

http://groups.google.com/group/pynac-devel/browse_thread/thread/a36020bf9208bf08/abdf6671ef0b926a#abdf6671ef0b926a

Burcin produced a patch restoring GiNaC original order for internal use and using the new ones only for printing ; thus fixing the bug.

I then worked on top of it to get a more consistent order.

You can test them using pynac 0.2.1 from #9901 ("cd spkg/standard/pynac-0.2.1/src/" then "hg import" both patches and build/install, you should "./sage -b" if upgrading from a previous version of pynac).

I don't consider that version as definitve, but would like to get some feedback on the order used for printing.

I don't use everything pynac provides so it is more than probable that some expression are not correctly printed now.

Do not hesitate to report it.

[kcrisman]

comment:5

#10282 almost certainly is the same thing.

[kcrisman]

comment:6

Fixing this probably will close #9632 - just putting that here for the record.

[vbraun]

comment:7

Apply trac_9880_revert_marking_random_from_trac_10187.patch to re-enable doctests that fail on OSX/PPC.