#13413 closed defect (fixed)
Correct bug in symmetric functions caused by Symmetrica using integers longer than 32 bits
Reported by: | saliola | Owned by: | sage-combinat |
---|---|---|---|
Priority: | critical | Milestone: | sage-5.13 |
Component: | combinatorics | Keywords: | symmetric functions, symmetrica, memleak |
Cc: | sage-combinat, aschilling, zabrocki, mguaypaq, darij, tscrim, mhansen | Merged in: | sage-5.13.beta2 |
Authors: | Jeroen Demeyer | Reviewers: | Mike Zabrocki |
Report Upstream: | Reported upstream. No feedback yet. | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by zabrocki)
There are two examples of bugs that this patch corrects.
The first is in the conversion of integers between Symmetrica and Sage:
sage: from sage.libs.symmetrica.symmetrica import test_integer sage: test_integer(2^76)==2^76 False sage: test_integer(2^75)==2^75 True
The second is that coefficients in symmetric function package are not always correct.
sage: s = SymmetricFunctions(QQ).s() sage: p = SymmetricFunctions(QQ).p() sage: c = s(p([1]*36)).coefficient([7,6,5,4,3,3,2,2,1,1,1,1]) sage: c==StandardTableaux([7,6,5,4,3,3,2,2,1,1,1,1]).cardinality() False
This bug is corrected by modifying the Symmetrica spkg to ensure that computations are done assuming that INT's are 4 bytes.
spkg: http://boxen.math.washington.edu/home/jdemeyer/spkg/symmetrica-2.0.p8.spkg (spkg diff)
apply 13413_symmetrica.patch
Attachments (4)
Change History (58)
comment:1 Changed 20 months ago by saliola
- Description modified (diff)
comment:2 Changed 20 months ago by aschilling
- Cc aschilling zabrocki added
Changed 18 months ago by mguaypaq
comment:3 Changed 18 months ago by mguaypaq
- Cc mguaypaq added
Running the attached file symmetrica-test.py exhibits the problem on some machines (e.g., a Mac of some sort, I don't have the specs with me) but on my own laptop (ancient Dell laptop running Ubuntu 10.04 LTS) the test runs out of memory before finding a problem. Curiously enough, for the Mac I tried the problem appears at size 47, same as in the problem description.
I think this shows that the problem is in (or extremely close to) Symmetrica, not Sage itself.
Also, given that the coefficients change even without any intervening computations, I strongly suspect that we're seeing a memory leak in Symmetrica, not an integer overflow error. Most likely,
- Symmetrica computes some result,
- caches a pointer to the result,
- frees the memory containing the result,
- this memory eventually gets reused,
- so the cached result now points to garbage.
It's interesting to note that the error only seems to happen when dealing with coefficients in QQ, not in ZZ, as Anne's testing shows. However, given the state of the Symmetrica source code, I'm not optimistic about actually finding (and fixing) the bug.
Do we know if there are other changes of basis which exhibit similar problems?
For convenience, note that the content of symmetrica-test.py is simply:
from sage.all import QQ, ZZ, Partition from sage.libs.symmetrica.all import t_POWSYM_SCHUR as convert from time import time one = QQ(1) bad_input = {Partition([ZZ(2)] * 2): one} good_output = convert(bad_input) start_time = time() k = 1 while True: dummy = convert({Partition([ZZ(1)] * k): one}) if convert(bad_input) != good_output: break print 'Size %d seems fine after %d seconds.' % (k, time() - start_time) k += 1 print 'Found a problem at size %d:' % k for k in range(10): print convert(bad_input)
comment:4 Changed 8 months ago by jdemeyer
- Milestone changed from sage-5.11 to sage-5.12
comment:5 Changed 6 months ago by zabrocki
This problem is much worse than originally stated. Mercedes Rosas contacted me and said that they are getting strange answers for calculations in the symmetric function package. I started to do some experiments.
sage: s = SymmetricFunctions(QQ).s() sage: p = SymmetricFunctions(QQ).p() sage: %time s(p([1]*36))==sum(StandardTableaux(la).cardinality()*s(la) for la in Partitions(36)) CPU times: user 91.50 s, sys: 0.26 s, total: 91.75 s Wall time: 91.65 s False sage: s(p([1]*35))==sum(StandardTableaux(la).cardinality()*s(la) for la in Partitions(35)) True sage: s(p[2,2]) s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
The first statement should return True and the second and third are not returning the clearly false coefficients that we are seeing when the calculation goes as high as degree 47.
WARNING: calculations using the symmetric function package should not be believed beyond a certain degree. I will continue to see what we can do to track down this bug.
comment:6 Changed 6 months ago by zabrocki
Hmmm. I wonder if this has something to do with Mac's being a 64 bit architecture? I checked the size of the coefficients for [1]*35 v. [1]*36 and found:
sage: s = SymmetricFunctions(QQ).s() sage: p = SymmetricFunctions(QQ).p() sage: g = s(p([1]*35)) sage: max(float(log(c)/log(2)) for c in g.coefficients()) 62.76221725889632 sage: g = s(p([1]*36)) sage: max(float(log(c)/log(2)) for c in g.coefficients()) 64.9241936394965
I suspect the function _py_longint in symmetrica.pxi is at fault but I haven't been able to track down some of the definitions in that file.
comment:7 Changed 6 months ago by zabrocki
If others are experiencing/not experiencing the same problems please let me know. I am running sage on mac running OSX 10.8.5 with Intel Core i7 processors. I am seeing the same bug at degree 36 on a linux machine at work.
comment:8 Changed 6 months ago by zabrocki
There is a function test_integer in the symmetrica package. It passes on some integers, but not all!
sage: from sage.libs.symmetrica.symmetrica import test_integer sage: s = SymmetricFunctions(QQ).s() sage: p = SymmetricFunctions(QQ).p() sage: g = s(p([1]*35)) sage: all( test_integer(c)==c for c in g.coefficients()) True sage: g = s(p([1]*36)) sage: all( test_integer(c)==c for c in g.coefficients()) False sage: c=StandardTableaux([10,9,8,7,6,5,4,3,2,1]).cardinality() sage: test_integer(c)==c False
comment:9 Changed 6 months ago by zabrocki
Simple test:
sage: from sage.libs.symmetrica.symmetrica import test_integer sage: test_integer(2^76)==2^76 False sage: test_integer(2^75)==2^75 True
Changed 6 months ago by zabrocki
comment:10 Changed 6 months ago by zabrocki
I have a fix (see patch) for *only* one problem. A two line change fixes the issue with test_integer.
But sadly :( this does not fix the issue with s(p([1]*36)).
comment:11 Changed 6 months ago by zabrocki
The error seems to be within Symmetrica. I computed s(p([1]*36)) and stuck in a print statement to print out the intermediate symmetrica object. I found that the coefficient of the partition 111122334567 is 5.061293.630159.021056 and this agrees with what is returned by the command g = s(p([1]*36))
sage: g.coefficient([7,6,5,4,3,3,2,2,1,1,1,1]) 5061293630159021056
however the coefficient should be
sage: StandardTableaux([7,6,5,4,3,3,2,2,1,1,1,1]).cardinality() 12961662907729536000
comment:12 Changed 6 months ago by darij
- Cc darij added
- Keywords symmetrica memleak added
- Priority changed from major to critical
comment:13 Changed 6 months ago by darij
Ouch.
I can't help with understanding C code, but if anyone needs some of the German in Symmetrica translated, I can help.
Has the error so far only occurred in high degrees or with big coefficients only, or should all of Sym be considered a minefield until further notice?
comment:14 Changed 6 months ago by zabrocki
This is bad. Technically any calculation that involves the p basis over degree 20 and other bases of degree 30+ should be suspect. I make this assessment because it seems that the integer calculations with coefficients using 64 bits may be a problem. If you check sage.combinat.sf.sfa.zee(la) for la partitions of 21 and the number of standard tableaux of degree 35 have values > 2**64.
I can understand C, but it is a bit rusty for me. The fact that the C is written in German makes it slightly more of a challenge since for some functions I really have to make wild guesses.
comment:15 Changed 6 months ago by zabrocki
Mike H. posted a test.c program to try out in Symmetrica.
#include "def.h" #include "macro.h" ANFANG scan(POW_SYM,a); t_POWSYM_SCHUR(a, b); println(b); ENDE
Run this program with input "36" followed by thirty-six "1"'s, followed by "1" (to indicate an integer coefficient), followed by "1" (to indicate that the coefficient is 1) "n" and the output says again 5.061293.630159.021056 111122334567. This means that the error is within Symmetrica.
comment:16 Changed 6 months ago by tscrim
- Cc tscrim added
I shouldn't be too rusty with my C, but this might take a combined effort at Sage Days to fully complete it. I'll take a look at the code as well.
Here's my two guesses about the problem from the discussion:
- It is an overflow error and the big fix will be to convert Symmetrica to use mpz instead of the usual machine integers.
- Symmetrica is using its own high precision integers (perhaps with a fixed maximum size) and it's overflowing that block of memory.
comment:17 Changed 6 months ago by zabrocki
I've spent some time looking through the Symmetrica code. It is not hard to figure out the basic ideas behind the library, but it uses some very terse C, non-obvious abbreviations, and a mix of German and English. It also has very little documentation.
Symmetrica "longints" are a structure of three INTs w2,w1,w0 with 0<=w_i<=2^15-1 plus a pointer to the next batch of 3 or NULL.
I've played with some programs that do some addition and multiplication with these longints and I haven't been able to make them fail, but it must be that in the calculation of p([1]*36) that some arithmetic fails when some overflow occurs. It will almost definitely easier to identify the bug in the library than to adapt it to another data structure.
comment:18 Changed 6 months ago by jdemeyer
Please report this upstream then.
comment:19 Changed 6 months ago by zabrocki
- Report Upstream changed from N/A to Reported upstream. No feedback yet.
So I wrote to symmetric(at)symmetrica.de and told them about the bug and pointed them to the ticket for the example.
comment:20 Changed 6 months ago by jdemeyer
Maybe it's good to indicate in the ticket description where/how you reported this upstream.
comment:21 Changed 6 months ago by zabrocki
Yea! I think I found it! I thought about it and realized that the coefficient that I have been concentrating on as my example must be coming from adding the number of standard tableaux of shape formed by removing an outer corner together. I tried the following as a test.c.
#include "def.h" #include "macro.h" ANFANG sscan_integer("1003805253100650000",a); println(a); sscan_integer("1357888495095475200",b); println(b); sscan_integer("1472208106707261000",c); println(c); sscan_integer("1336535106226320000",d); println(d); sscan_integer("2194567264800768000",e); println(e); sscan_integer("2252538987957858600",f); println(f); sscan_integer("3344119693841203200",g); println(g); printf("-------------------\n"); add(a,b,h); println(h); add(c,h,h); println(h); add(d,h,h); println(h); add(e,h,h); println(h); add(f,h,h); println(h); add(g,h,h); println(h); ENDE
So above the line we will see the numbers of standard tableaux formed by removing a corner (which I calculated in sage, but compared them to the output of the program in comment 15. And the output is....
SYMMETRICA VERSION 3.0 - STARTING Thu Feb 26 14:58:10 MET 1998 1003805253100650000 1357888495095475200 1472208106707261000 1336535106226320000 2194567264800768000 2252538987957858600 3344119693841203200 ------------------- 2361693748196125200 3833901854903386200 5170436961129706200 7365004225930474200 2.252539.342021.485568 5.596659.035862.688768 SYMMETRICA VERSION 3.0 - ENDING last changed: Thu Feb 26 14:58:10 MET 1998
Lets do the same thing by hand in sage:
sage: 1003805253100650000+1357888495095475200 2361693748196125200 sage: _+1472208106707261000 3833901854903386200 sage: _+1336535106226320000 5170436961129706200 sage: _+2194567264800768000 7365004225930474200 sage: _+2252538987957858600 9617543213888332800
Notice that as soon as I add two 'integer' objects together so that they become a 'longint' object (marked by where the program starts printing out periods in the number) the answer is wrong. So now I just have to find the routine which adds two ints and gives an overflow into longints.
comment:22 Changed 6 months ago by zabrocki
Here is a mini test.c to verify if the programs are working
#include "def.h" #include "macro.h" ANFANG sscan_integer("7365004225930474200",a); println(a); sscan_integer("2252538987957858600",b); println(b); printf("+------------------\n"); add(a,b,h); println(h); printf("but the answer should be....\n"); printf("9617543213888332800\n"); ENDE
Currently on my computer the answer is... 7.365004.528389.219328
comment:23 Changed 6 months ago by zabrocki
I sent a second bug report to symmetrica(at)symmetrica.de with the above example.
comment:24 Changed 6 months ago by zabrocki
Here seems to be the problem. If I take an integer and convert it into a long integer then it isn't right.
#include "def.h" #include "macro.h" ANFANG sscan_integer("2252538987957858600",a); println(a); printf("but when I convert it into a long integer...\n"); t_int_longint(a,b); println(b); ENDE
The output on my computer:
SYMMETRICA VERSION 3.0 - STARTING Thu Feb 26 14:58:10 MET 1998 2252538987957858600 but when I convert it into a long integer... 302458.745128 SYMMETRICA VERSION 3.0 - ENDING
comment:25 Changed 6 months ago by mhansen
- Cc mhansen added
comment:26 Changed 6 months ago by mhansen
That makes sense since it's always expecting ints to be at most 32 bits. I'm testing out a patch now.
comment:27 Changed 6 months ago by zabrocki
It seems as though ints can be as large as 45 bits and the function t_int_longint will still work properly.
comment:28 Changed 6 months ago by mhansen
Okay, the fix is to make def.h look like the following:
#include <stdint.h> #ifdef __alpha typedef int32_t INT; typedef uint32_t UINT; #else /* __alpha */ typedef int32_t INT; typedef uint32_t UINT; #endif /* __alpha */
(and you probably don't need to change the first part.
comment:29 Changed 6 months ago by zabrocki
Thanks Mike.
The first two lines of def.h read:
/* file def.h SYMMETRICA */ /* INT should always be 4 byte */
Now it is becoming clearer to me...
comment:30 Changed 6 months ago by zabrocki
So I haven't the first clue about how to muck with the spkg's. Will you post your fix? I haven't even been able to check that it corrects the problems with the symmetric function calculations in sage. Essentially there are two problems that need to be checked (or three if you count the first issue that I provide a fix for above).
The first one is that at degree 36 the calculation is not correct. The second one is that after a calculation at degree 47 the coefficients start to become random.
comment:31 Changed 6 months ago by jdemeyer
I can easily make a spkg.
comment:32 Changed 6 months ago by jdemeyer
- Description modified (diff)
comment:33 Changed 6 months ago by jdemeyer
I'm a bit worried by some of the compiler warnings, but these already existed before the patches...
comment:34 Changed 6 months ago by zabrocki
I'm having some issues installing it because I seem to be getting errors and not just warnings.
Are you getting the same error messages?
symmetrica-2.0.p8 ==================================================== Extracting package /Users/zabrocki/Downloads/symmetrica-2.0.p8.spkg -rw-r--r--@ 1 zabrocki staff 680547 Oct 17 09:26 /Users/zabrocki/Downloads/symmetrica-2.0.p8.spkg Finished extraction **************************************************** Host system: Darwin Mikes-MacBook-Pro.local 12.5.0 Darwin Kernel Version 12.5.0: Sun Sep 29 13:33:47 PDT 2013; root:xnu-2050.48.12~1/RELEASE_X86_64 x86_64 **************************************************** C compiler: gcc C compiler version: Using built-in specs. COLLECT_GCC=gcc COLLECT_LTO_WRAPPER=/Applications/sage/local/bin/../libexec/gcc/x86_64-apple-darwin12.3.0/4.7.3/lto-wrapper Target: x86_64-apple-darwin12.3.0 Configured with: ../src/configure --prefix=/Users/dehayebuildbot/build/sage/dehaye/dehaye_binary/build/sage-5.10/local --with-local-prefix=/Users/dehayebuildbot/build/sage/dehaye/dehaye_binary/build/sage-5.10/local --with-gmp=/Users/dehayebuildbot/build/sage/dehaye/dehaye_binary/build/sage-5.10/local --with-mpfr=/Users/dehayebuildbot/build/sage/dehaye/dehaye_binary/build/sage-5.10/local --with-mpc=/Users/dehayebuildbot/build/sage/dehaye/dehaye_binary/build/sage-5.10/local --with-system-zlib --disable-multilib --disable-nls Thread model: posix gcc version 4.7.3 (GCC) **************************************************** patching file de.c patching file def.h patching file macro.h patching file bar.c patching file def.h Hunk #1 succeeded at 3100 (offset -5 lines). Hunk #2 succeeded at 3266 (offset -5 lines). patching file di.c patching file ga.c patching file galois.c patching file macro.h patching file nc.c patching file nu.c patching file part.c patching file perm.c patching file rest.c patching file ta.c patching file zyk.c gcc -O2 -g -DFAST -DALLTRUE -c -o bar.o bar.c gcc -O2 -g -DFAST -DALLTRUE -c -o bi.o bi.c gcc -O2 -g -DFAST -DALLTRUE -c -o boe.o boe.c gcc -O2 -g -DFAST -DALLTRUE -c -o bruch.o bruch.c gcc -O2 -g -DFAST -DALLTRUE -c -o classical.o classical.c gcc -O2 -g -DFAST -DALLTRUE -c -o de.o de.c gcc -O2 -g -DFAST -DALLTRUE -c -o di.o di.c gcc -O2 -g -DFAST -DALLTRUE -c -o ff.o ff.c gcc -O2 -g -DFAST -DALLTRUE -c -o galois.o galois.c gcc -O2 -g -DFAST -DALLTRUE -c -o ga.o ga.c gcc -O2 -g -DFAST -DALLTRUE -c -o gra.o gra.c gcc -O2 -g -DFAST -DALLTRUE -c -o hash.o hash.c gcc -O2 -g -DFAST -DALLTRUE -c -o hiccup.o hiccup.c gcc -O2 -g -DFAST -DALLTRUE -c -o io.o io.c gcc -O2 -g -DFAST -DALLTRUE -c -o ko.o ko.c gcc -O2 -g -DFAST -DALLTRUE -c -o list.o list.c gcc -O2 -g -DFAST -DALLTRUE -c -o lo.o lo.c lo.c:84:5: error: conflicting types for 'loc_index' In file included from lo.c:3:0: macro.h:559:13: note: previous declaration of 'loc_index' was here lo.c:85:5: error: conflicting types for 'loc_size' In file included from lo.c:3:0: macro.h:559:24: note: previous declaration of 'loc_size' was here lo.c:86:5: error: conflicting types for 'loc_counter' In file included from lo.c:3:0: macro.h:559:33: note: previous declaration of 'loc_counter' was here lo.c:88:5: error: conflicting types for 'mem_counter_loc' In file included from lo.c:3:0: macro.h:562:35: note: previous declaration of 'mem_counter_loc' was here lo.c:89:5: error: conflicting types for 'longint_speicherindex' In file included from lo.c:3:0: macro.h:562:13: note: previous declaration of 'longint_speicherindex' was here lo.c:90:5: error: conflicting types for 'longint_speichersize' In file included from lo.c:3:0: macro.h:562:51: note: previous declaration of 'longint_speichersize' was here make: *** [lo.o] Error 1 Error building Symmetrica. real 0m28.966s user 0m27.970s sys 0m0.759s ************************************************************************ Error installing package symmetrica-2.0.p8 ************************************************************************ Please email sage-devel (http://groups.google.com/group/sage-devel) explaining the problem and including the relevant part of the log file /Applications/sage/logs/pkgs/symmetrica-2.0.p8.log Describe your computer, operating system, etc. If you want to try to fix the problem yourself, *don't* just cd to /Applications/sage/spkg/build/symmetrica-2.0.p8 and type 'make' or whatever is appropriate. Instead, the following commands setup all environment variables correctly and load a subshell for you to debug the error: (cd '/Applications/sage/spkg/build/symmetrica-2.0.p8' && '/Applications/sage/sage' --sh) When you are done debugging, you can type "exit" to leave the subshell. ************************************************************************
Any ideas?
comment:35 Changed 6 months ago by jdemeyer
This is work in progress, not yet needs_review.
Changed 6 months ago by jdemeyer
comment:36 Changed 6 months ago by jdemeyer
- Description modified (diff)
comment:37 Changed 6 months ago by jdemeyer
- Status changed from new to needs_review
Changed 6 months ago by jdemeyer
comment:38 Changed 6 months ago by jdemeyer
- Description modified (diff)
comment:39 Changed 6 months ago by jdemeyer
Added doctests
comment:40 Changed 6 months ago by zabrocki
The version you just posted seems to compile (I was having issues before) but it looks like the fix only solves 1/2 of the problem.
sage: s = SymmetricFunctions(QQ).s() sage: p = SymmetricFunctions(QQ).p() sage: g = s(p([1]*36)) sage: g.coefficient([7,6,5,4,3,3,2,2,1,1,1,1]) 12961662907729536000 sage: g = s(p([1]*47)) sage: s(p[2,2]) s[1, 1, 1, 1] - s[2, 1, 1] + 1589352607*s[2, 2] - s[3, 1] + s[4]
Are you getting similar results? We may have to go back to the drawing board.
comment:41 Changed 6 months ago by jdemeyer
I get
sage: s = SymmetricFunctions(QQ).s() sage: p = SymmetricFunctions(QQ).p() sage: g = s(p([1]*36)) sage: g.coefficient([7,6,5,4,3,3,2,2,1,1,1,1]) 12961662907729536000 sage: g = s(p([1]*47)) sage: s(p[2,2]) s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
Sorry to ask the obvious, but you did run ./sage -b after installing the spkg, right?
comment:42 Changed 6 months ago by zabrocki
I did. I just touched all the files in the sage/libs/symmetrica directory and re-ran the sage -b. It fixes the problem so now both problems are fixed. I'll do a few more tests but that looks fantastic! Thanks.
comment:43 Changed 6 months ago by zabrocki
I don't know if this kicks the can down the road or if something else is going wrong. I am still finding failing tests if I go higher in degree.
sage: s = SymmetricFunctions(QQ).s() sage: p = SymmetricFunctions(QQ).p() sage: g = s(p([1]*47)) sage: g.coefficient([9,8,7,6,5,4,3,2,2,1]) 14333651730948448927581696000 sage: StandardTableaux([9,8,7,6,5,4,3,2,2,1]).cardinality() 14333651730948448927581696000 sage: g = s(p([1]*55)) sage: g.coefficient([10,9,8,7,6,5,4,3,2,1]) 8018556129655805634621347419399180139888640 sage: StandardTableaux([10,9,8,7,6,5,4,3,2,1]).cardinality() 44261486084874072183645699204710400 sage: s(p[2,2]) s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4] sage: g = s(p([1]*61)) sage: g.coefficient([10,9,8,7,6,5,5,4,3,2,1,1]) 776260975585827810735172007007698644433817545700 sage: StandardTableaux([10,9,8,7,6,5,5,4,3,2,1,1]).cardinality() 5801010788714895536587439870454056838000 sage: s(p[2,2]) s[1, 1, 1, 1] - s[2, 1, 1] + 498984676*s[2, 2] - s[3, 1] + s[4]
Note that computing the degree 61 calculations takes a long time. Are you finding the same errors?
comment:44 Changed 6 months ago by jdemeyer
I get
jdemeyer@boxen:/release/merger/sage-5.12$ ./sage ┌────────────────────────────────────────────────────────────────────┐ │ Sage Version 5.12, Release Date: 2013-10-07 │ │ Type "notebook()" for the browser-based notebook interface. │ │ Type "help()" for help. │ └────────────────────────────────────────────────────────────────────┘ sage: s = SymmetricFunctions(QQ).s() sage: p = SymmetricFunctions(QQ).p() sage: g = s(p([1]*47)) sage: g.coefficient([9,8,7,6,5,4,3,2,2,1]) 14333651730948448927581696000 sage: StandardTableaux([9,8,7,6,5,4,3,2,2,1]).cardinality() 14333651730948448927581696000 sage: g = s(p([1]*55)) sage: g.coefficient([10,9,8,7,6,5,4,3,2,1]) 44261486084874072183645699204710400 sage: StandardTableaux([10,9,8,7,6,5,4,3,2,1]).cardinality() 44261486084874072183645699204710400 sage: s(p[2,2]) s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4] sage: g = s(p([1]*61)) sage: g.coefficient([10,9,8,7,6,5,5,4,3,2,1,1]) 5801010788714895536587439870454056838000 sage: StandardTableaux([10,9,8,7,6,5,5,4,3,2,1,1]).cardinality() 5801010788714895536587439870454056838000 sage: s(p[2,2]) s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
comment:45 Changed 6 months ago by zabrocki
Trials on linux machine give correct answers, on Mac I am getting errors. I am running sage -ba to see if this makes a difference.
comment:46 Changed 6 months ago by zabrocki
On two different macs am getting:
sage: s = SymmetricFunctions(QQ).s() sage: p = SymmetricFunctions(QQ).p() sage: sage: g = s(p([1]*47)) sage: g.coefficient([9,8,7,6,5,4,3,2,2,1]) 14333651730948448927581696000 sage: sage: g = s(p([1]*47)) sage: g.coefficient([9,8,7,6,5,4,3,2,2,1]) 6813423452539470910666189837844044800
The first time the value is computed it seems to be correct. The second time it is random. This does not happen on linux.
comment:47 Changed 6 months ago by zabrocki
So I ran on an old copy of sage (no correction installed) on the same linux machine:
sage: s = SymmetricFunctions(QQ).s() sage: p = SymmetricFunctions(QQ).p() sage: g = s(p([1]*47)) sage: s(p([1]*5)) s[1, 1, 1, 1, 1] + 4*s[2, 1, 1, 1] + 5*s[2, 2, 1] + 6*s[3, 1, 1] + 5*s[3, 2] + 4*s[4, 1] + s[5]
On an old copy of sage on mac (correction installed or not):
sage: s = SymmetricFunctions(QQ).s() sage: p = SymmetricFunctions(QQ).p() sage: g = s(p([1]*47)) sage: s(p([1]*5)) s[1, 1, 1, 1, 1] - 1004621421*s[2, 1, 1, 1] - 2015815354*s[2, 2, 1] - 2018818386*s[3, 1, 1] - 2013245610*s[3, 2] - 1015866049*s[4, 1] + s[5]
This means that there are two (at least partially) independent problems going on here. One of them does not seem to appear on linux machines. When I run the examples in the patch description, I do not see the random coefficients in the expansion of s(p([2,2])). Do you see it on boxen?
comment:48 Changed 6 months ago by zabrocki
I am running on the hypothesis that on (at least certain) linux machines that the bug described in the patch description never existed. It was only a bug on Macs. However starting in comment 5, I identified a second bug that we can recreate at degree 36. This second bug is all corrected by installing the spkg and the patch (maybe there is a third bug around test_integer?).
I've only tested this on a couple of Macs and one linux machine and Jeroen has been posting the results from boxen. All evidence that I have says that the first bug is not resolved, but is only a problem on Macs. Can someone recreate the bug in the patch description on a linux machine?
The original description points to "some wrapper functions around symmetrica." This is probably still the case.
comment:49 Changed 6 months ago by darij
Ubuntu in a virtualbox, 64bit, sage 5.13.beta0 with patches installed (hopefully correctly: I -i'd symmetrica 2.0p8, but I never explicitly uninstalled 2.0p7).
Exhibit A:
sage: s = SymmetricFunctions(QQ).s() sage: sage: p = SymmetricFunctions(QQ).p() sage: g = s(p([1]*47)) sage: g.coefficient([9,8,7,6,5,4,3,2,2,1]) 14333651730948448927581696000 sage: g = s(p([1]*47)) sage: g.coefficient([9,8,7,6,5,4,3,2,2,1]) 14333651730948448927581696000
Exhibit B:
sage: p = SymmetricFunctions(QQ).powersum() sage: s = SymmetricFunctions(QQ).schur() sage: sage: s(p[2,2]) s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4] sage: time g = s(p([1]*47)) /home/darij/sage-5.13.beta0/local/lib/python2.7/site-packages/sage/misc/sage_extension.py:371: DeprecationWarning: Use %time instead of time. See http://trac.sagemath.org/12719 for details. line = f(line, line_number) CPU times: user 19.23 s, sys: 0.06 s, total: 19.29 s Wall time: 19.81 s sage: s(p[2,2]) s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
This speaks for it being a Mac problem. (No, I don't have one to test.)
Seeing that there really seem to be two separate issues here, can we get the current patch into beta1 without waiting for the Mac issue to be resolved? I am scared of working with Sym now...
EDIT: And to verify that the other issue has been resolved, Exhibit C:
sage: s = SymmetricFunctions(QQ).s() sage: p = SymmetricFunctions(QQ).p() sage: %time s(p([1]*36))==sum(StandardTableaux(la).cardinality()*s(la) for la in Partitions(36)) CPU times: user 122.02 s, sys: 0.52 s, total: 122.53 s Wall time: 129.03 s True
Many thanks for this, Mike and Jeroen!!
comment:50 follow-up: ↓ 51 Changed 6 months ago by zabrocki
- Description modified (diff)
- Status changed from needs_review to positive_review
- Summary changed from fix integer overflow (?) in conversion of powersums to Schur functions to Correct bug in symmetric functions caused by Symmetrica using integers longer than 32 bits
Since 95% of this discussion really is about the correction of the second bug, I decided to move the original description to a new trac ticket #15312.
comment:51 in reply to: ↑ 50 Changed 6 months ago by jdemeyer
comment:52 Changed 6 months ago by jdemeyer
- Reviewers set to Mike Zabrocki
comment:53 Changed 6 months ago by jdemeyer
- Merged in set to sage-5.13.beta2
- Resolution set to fixed
- Status changed from positive_review to closed
comment:54 Changed 4 months ago by jdemeyer
- Reviewers changed from Mike Zabrocki to Mike Zabrocki
Running "sage symmetrica-test.py" may exhibit the bug.