replace gap.eval with libgap calls in combinat/combinat.py

[rwst]

As first reported in #15625 (comment:7) with lucas_number1, the same problem is encountered with gap evaluation of Stirling numbers:

sage: stirling_number1(1000,2)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-22-b29f3b3e2003> in <module>()
----> 1 stirling_number1(Integer(1000),Integer(2))

/home/ralf/sage/local/lib/python2.7/site-packages/sage/combinat/combinat.pyc in stirling_number1(n, k)
    650     """
    651     return Integer(gap.eval("Stirling1({0},{1})".format(Integer(n),
--> 652                                                         Integer(k))))
    653 
    654 

/home/ralf/sage/local/lib/python2.7/site-packages/sage/rings/integer.so in sage.rings.integer.Integer.__init__ (build/cythonized/sage/rings/integer.c:7902)()

TypeError: unable to convert x (=<integer 301...000 (2566 digits)>) to an integer

The way to go would be to replace gap.eval with libgap.eval and it's faster, too:

sage: timeit('Integer(gap.eval("Stirling1(100,2)"))')
625 loops, best of 3: 419 µs per loop
sage: timeit('libgap.eval("Stirling1(100,2)").sage()')
625 loops, best of 3: 125 µs per loop
sage: timeit('libgap.eval("Stirling1(1000,2)").sage()')
125 loops, best of 3: 6.45 ms per loop

Addendum: even faster would be to use (n-1)!*H(n-1) for stirling(n,2), dependent on #16671:

sage: harmonic_number(99)*factorial(99)==stirling_number1(100,2)
True
sage: timeit('harmonic_number(99)*factorial(99)')
625 loops, best of 3: 56.9 µs per loop
sage: timeit('harmonic_number(999)*factorial(999)')
625 loops, best of 3: 119 µs per loop

Depends on #17157

CC: @vbraun

Component: combinatorics

Keywords: gap, bignum, expect, pexpect, libgap, stirling

Author: Ralf Stephan

Branch/Commit: d6698e2

Reviewer: Jeroen Demeyer, Volker Braun

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

[rwst]

Changed keywords from gap, bignum, expect, pexpect to gap, bignum, expect, pexpect, libgap

[rwst]

Description changed:

--- 
+++ 
@@ -18,4 +18,14 @@

 TypeError: unable to convert x (=<integer 301...000 (2566 digits)>) to an integer

-Alternatively, this ticket may discuss abandoning the GAP expect interface for such big number results and use libpari instead. +The way to go would be to replace gap.eval with libgap.eval and it's faster, too: + + +sage: timeit('Integer(gap.eval("Stirling1(100,2)"))') +625 loops, best of 3: 419 µs per loop +sage: timeit('libgap.eval("Stirling1(100,2)").sage()') +625 loops, best of 3: 125 µs per loop +sage: timeit('libgap.eval("Stirling1(1000,2)").sage()') +125 loops, best of 3: 6.45 ms per loop + +

[rwst]

Description changed:

--- 
+++ 
@@ -28,4 +28,12 @@
 sage: timeit('libgap.eval("Stirling1(1000,2)").sage()')
 125 loops, best of 3: 6.45 ms per loop

+Addendum: even faster would be to use (n-1)!*H(n-1) for stirling(n,2), dependent on #16671:

+ +sage: harmonic_number(99)*factorial(99)==stirling_number1(100,2) +True +sage: timeit('harmonic_number(99)*factorial(99)') +625 loops, best of 3: 56.9 µs per loop + +

[rwst]

Changed keywords from gap, bignum, expect, pexpect, libgap to gap, bignum, expect, pexpect, libgap, stirling

[rwst]

Description changed:

--- 
+++ 
@@ -35,5 +35,7 @@
 True
 sage: timeit('harmonic_number(99)*factorial(99)')
 625 loops, best of 3: 56.9 µs per loop
+sage: timeit('harmonic_number(999)*factorial(999)')
+625 loops, best of 3: 119 µs per loop

[tscrim]

Dependencies: #16380

[tscrim]

comment:4

Also with #16380 (which I've added as a dependency because it's not been put into a release yet), we don't have to worry about the startup time of libgap anymore (which was really annoying). +1 to doing this.

[rwst]

comment:5

This is blocked by:

sage: ans=libgap.eval("UnorderedTuples(['a','b','c'],2)")
sage: type(ans)
<type 'sage.libs.gap.element.GapElement_List'>
sage: a=ans.sage()
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
<ipython-input-4-43379484318b> in <module>()
----> 1 a=ans.sage()

/home/ralf/sage/local/lib/python2.7/site-packages/sage/libs/gap/element.so in sage.libs.gap.element.GapElement_List.sage (build/cythonized/sage/libs/gap/element.c:14661)()

/home/ralf/sage/local/lib/python2.7/site-packages/sage/libs/gap/element.so in sage.libs.gap.element.GapElement_List.sage (build/cythonized/sage/libs/gap/element.c:14661)()

/home/ralf/sage/local/lib/python2.7/site-packages/sage/libs/gap/element.so in sage.libs.gap.element.GapElement.sage (build/cythonized/sage/libs/gap/element.c:8749)()

See #16750

[rwst]

Changed dependencies from #16380 to #16380, #16750

[rwst]

Branch: u/rws/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py

[vbraun]

New commits:

16922b5

16719: replace gap with libgap

[vbraun]

Commit: 16922b5

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 16922b5 to b69d63f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

843ba48	Convert Gap chars into Python strings
b69d63f	Merge branch 'u/vbraun/libgap_fails_converting_string_gapelements_to_sage' of trac.sagemath.org:sage into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py

[rwst]

comment:9

OK, now that strings get to GAP, back they get as GapElement_List of chars:

sage: ans = libgap.eval("UnorderedTuples(['a', 'b', 'c'],2)"); ans
[ "aa", "ab", "ac", "bb", "bc", "cc" ]
sage: type(ans[0])
<type 'sage.libs.gap.element.GapElement_List'>
sage: ans.sage()
[["'a'", "'a'"],
 ["'a'", "'b'"],
 ["'a'", "'c'"],
 ["'b'", "'b'"],
 ["'b'", "'c'"],
 ["'c'", "'c'"]]

Shouldn't lists of chars be converted to strings?

[rwst]

Author: Ralf Stephan

[rwst]

Changed dependencies from #16380, #16750 to #16380

[rwst]

Merged: #16750

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

240cc10

16719 reviewer's patch: attempt to fix previous patch

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b69d63f to 240cc10

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 240cc10 to a1269fb

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

47f0796	Merge branch 'develop' into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py
7cc26d5	Improve GAP String handling
6fe1fc5	Treat the empty GAP list as list and not as string
6a4892d	Merge branch 't/16750/libgap_fails_converting_string_gapelements_to_sage' into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py
a1269fb	16719: unordered_tuples() distinguishes now between set types

[rwst]

comment:13

It felt more natural to give tuples of chars as string, but tuples of char+string as list of strings. If the latter had been the original behaviour the GAP T_CHAR hassle wouldn't have been necessary.

Please review.

[kcrisman]

Changed dependencies from #16380 to none

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

e82786b

Merge branch 'develop' into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a1269fb to e82786b

[tscrim]

comment:17

Note that this will conflict with #13982 for unordered_tuples (FYI I handled GAP's output as strings differently).

[tscrim]

Changed merged from #16750 to none

[tscrim]

Dependencies: #16750

[rwst]

comment:19

I wouldn't mind removing the unordered tuples bit from this patch, especially for speed reasons, and choice of algorithm. It's just that I don't like it that you simply remove that doctest that results in ['aa', 'ab', 'ac', 'bb', 'bc', 'cc']. I think you should support it.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

5b156ad

16719: revert change to unordered_tuples(), handled by 13982

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e82786b to 5b156ad

[jdemeyer]

comment:21

For bell_number(), I'm making the change at #17157, so you can remove that piece.

[jdemeyer]

Changed branch from u/rws/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py to u/jdemeyer/ticket/16719

[jdemeyer]

Changed commit from 5b156ad to 4339c50

[jdemeyer]

comment:23

Reviewer patch needs review.

---

New commits:

0266cef	Improve formula for Bell numbers
fd22966	Merge branch 'ticket/17157' into ticket/16719
4339c50	Remove superfluous type conversions, use libgap for unordered_tuples()

[jdemeyer]

Changed dependencies from #16750 to #17157

[jdemeyer]

Reviewer: Jeroen Demeyer

[vbraun]

Changed branch from u/jdemeyer/ticket/16719 to u/vbraun/ticket/16719

[vbraun]

Changed commit from 4339c50 to 9f4777d

[vbraun]

comment:25

The reviewer commits look good to me. I've added a patch to make the calls to my beautiful library interface less ugly ;-)

---

New commits:

9f4777d

Beautify libgap calls

[jdemeyer]

Changed reviewer from Jeroen Demeyer to Jeroen Demeyer, Volker Braun

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:

34c9b4c	Changes from the reviewers.
b47af6a	A minor tweaking of the doc.
53a9d7e	Families return output based on order of variable names. Fixed coercion issue.
339b71d	Fixed some typos.
3ce3f6a	Merge branch 'public/algebras/weyl_clifford-15300' of git://trac.sagemath.org/sage into clifford
8698275	lifting bilinear forms onto exterior algebras
a002f4b	Some tweaks to lifted_bilinear_form and fixed doctest.
ff27bdc	further fixes
330617c	Merge commit 'ff27bdc5d87967d0e7fd5c1305cef4340db816c7' into ticket/17157
d6698e2	Merge already-closed #17157 to resolve conflict

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9f4777d to d6698e2

[vbraun]

Changed branch from u/vbraun/ticket/16719 to d6698e2