#13413: fix integer overflow (?) in conversion of powersums to Schur functions
-------------------------------------------------+-------------------------
Reporter: saliola | Owner: sage-
Type: defect | combinat
Priority: critical | Status: new
Component: combinatorics | Milestone: sage-5.13
Keywords: symmetric functions, | Resolution:
symmetrica, memleak | Merged in:
Authors: Jeroen Demeyer | Reviewers:
Report Upstream: Reported upstream. No | Work issues:
feedback yet. | Commit:
Branch: | Stopgaps:
Dependencies: |
-------------------------------------------------+-------------------------
Description changed by jdemeyer:
Old description:
> To begin with, let's do a change of basis in a small degree:
> {{{
> sage: p = SymmetricFunctions(QQ).powersum()
> sage: s = SymmetricFunctions(QQ).schur()
> sage: s(p[2,2])
> s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
> }}}
> Now let's do one in a larger degree:
> {{{
> sage: time g = s(p([1]*47))
> Time: CPU 19.16 s, Wall: 20.91 s
> }}}
> Now let's do that first one again:
> {{{
> sage: s(p[2,2])
> s[1, 1, 1, 1] - s[2, 1, 1] + 4571483302*s[2, 2] - s[3, 1] + s[4]
> }}}
> That's not the correct answer ! And the next time you ask Sage, it
> gives different, still incorrect, answers:
> {{{
> sage: s(p[2,2])
> s[1, 1, 1, 1] - s[2, 1, 1] + 4614252243*s[2, 2] - s[3, 1] + s[4]
> sage: s(p[2,2])
> s[1, 1, 1, 1] - s[2, 1, 1] + 4634718110*s[2, 2] - s[3, 1] + s[4]
> sage: s(p[2,2])
> s[1, 1, 1, 1] - s[2, 1, 1] + 4631047636*s[2, 2] - s[3, 1] + s[4]
> }}}
>
> In [https://groups.google.com/d/topic/sage-combinat-
> devel/fWMuS4R5M9Q/discussion this discussion] on sage-combinat-devel,
> Anne noticed that the problem is "not symmetrica per se, but some wrapper
> functions around symmetrica, as the following example shows":
> {{{
> sage: f = eval('symmetrica.t_POWSYM_SCHUR')
> sage: f({Partition([2,2]):Integer(1)})
> s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
> sage: time g = f({Partition([1]*47):Integer(1)})
> Time: CPU 13.03 s, Wall: 13.04 s
> sage: f({Partition([2,2]):Integer(1)})
> s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
> sage: Sym = SymmetricFunctions(QQ)
> sage: p = Sym.power()
> sage: s = Sym.schur()
> sage: s(p[2,2])
> s[1, 1, 1, 1] - s[2, 1, 1] + 4631790164*s[2, 2] - s[3, 1] + s[4]
> sage: f({Partition([2,2]):Integer(1)})
> s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
> }}}
>
> And Travis commented that:
>
> > When (random) big numbers appear like that, it almost always is an
> integer overflow. I suspect the communication with Symmetrica goes
> through the native integer. Is this correct? If so, then that's where I'd
> say the problem lies.
>
> '''spkg''':
> [http://boxen.math.washington.edu/home/jdemeyer/spkg/symmetrica-2.0.p8.spkg]
New description:
To begin with, let's do a change of basis in a small degree:
{{{
sage: p = SymmetricFunctions(QQ).powersum()
sage: s = SymmetricFunctions(QQ).schur()
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
}}}
Now let's do one in a larger degree:
{{{
sage: time g = s(p([1]*47))
Time: CPU 19.16 s, Wall: 20.91 s
}}}
Now let's do that first one again:
{{{
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 4571483302*s[2, 2] - s[3, 1] + s[4]
}}}
That's not the correct answer ! And the next time you ask Sage, it
gives different, still incorrect, answers:
{{{
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 4614252243*s[2, 2] - s[3, 1] + s[4]
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 4634718110*s[2, 2] - s[3, 1] + s[4]
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 4631047636*s[2, 2] - s[3, 1] + s[4]
}}}
In [https://groups.google.com/d/topic/sage-combinat-
devel/fWMuS4R5M9Q/discussion this discussion] on sage-combinat-devel, Anne
noticed that the problem is "not symmetrica per se, but some wrapper
functions around symmetrica, as the following example shows":
{{{
sage: f = eval('symmetrica.t_POWSYM_SCHUR')
sage: f({Partition([2,2]):Integer(1)})
s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
sage: time g = f({Partition([1]*47):Integer(1)})
Time: CPU 13.03 s, Wall: 13.04 s
sage: f({Partition([2,2]):Integer(1)})
s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
sage: Sym = SymmetricFunctions(QQ)
sage: p = Sym.power()
sage: s = Sym.schur()
sage: s(p[2,2])
s[1, 1, 1, 1] - s[2, 1, 1] + 4631790164*s[2, 2] - s[3, 1] + s[4]
sage: f({Partition([2,2]):Integer(1)})
s[1, 1, 1, 1] - s[2, 1, 1] + 2*s[2, 2] - s[3, 1] + s[4]
}}}
And Travis commented that:
> When (random) big numbers appear like that, it almost always is an
integer overflow. I suspect the communication with Symmetrica goes through
the native integer. Is this correct? If so, then that's where I'd say the
problem lies.
'''spkg''':
[http://boxen.math.washington.edu/home/jdemeyer/spkg/symmetrica-2.0.p8.spkg]
([attachment:symmetrica-2.0.p8.diff spkg diff])
'''apply''' [attachment:13413_include.patch]
--
--
Ticket URL: <http://trac.sagemath.org/ticket/13413#comment:36>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
