Opened 8 years ago
Closed 7 years ago
#16719 closed defect (fixed)
replace gap.eval with libgap calls in combinat/combinat.py
Reported by:  rws  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  combinatorics  Keywords:  gap, bignum, expect, pexpect, libgap, stirling 
Cc:  vbraun  Merged in:  
Authors:  Ralf Stephan  Reviewers:  Jeroen Demeyer, Volker Braun 
Report Upstream:  N/A  Work issues:  
Branch:  d6698e2 (Commits, GitHub, GitLab)  Commit:  d6698e2c4d7a3be2ff6c189a1bb24e55dda61616 
Dependencies:  #17157  Stopgaps: 
Description (last modified by )
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) <ipythoninput22b29f3b3e2003> in <module>() > 1 stirling_number1(Integer(1000),Integer(2)) /home/ralf/sage/local/lib/python2.7/sitepackages/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/sitepackages/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 (n1)!*H(n1)
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
Change History (29)
comment:1 Changed 8 years ago by
 Component changed from interfaces to combinatorics
 Description modified (diff)
 Keywords libgap added
 Summary changed from not all gap integers get converted to replace gap.eval with libgap.eval in combinat/combinat.py
comment:2 Changed 8 years ago by
 Description modified (diff)
comment:3 Changed 8 years ago by
 Description modified (diff)
 Keywords stirling added
comment:4 Changed 8 years ago by
 Dependencies set to #16380
comment:5 Changed 7 years ago by
 Dependencies changed from #16380 to #16380, #16750
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) <ipythoninput443379484318b> in <module>() > 1 a=ans.sage() /home/ralf/sage/local/lib/python2.7/sitepackages/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/sitepackages/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/sitepackages/sage/libs/gap/element.so in sage.libs.gap.element.GapElement.sage (build/cythonized/sage/libs/gap/element.c:8749)()
See #16750
comment:6 Changed 7 years ago by
 Branch set to u/rws/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py
comment:7 Changed 7 years ago by
 Cc vbraun added
 Commit set to 16922b5195624f1f2afd684b246a31fb00f5269e
New commits:
16922b5  16719: replace gap with libgap

comment:8 Changed 7 years ago by
 Commit changed from 16922b5195624f1f2afd684b246a31fb00f5269e to b69d63ff8b1ab648b71b86d840b666108de31053
comment:9 Changed 7 years ago by
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?
comment:10 Changed 7 years ago by
 Dependencies changed from #16380, #16750 to #16380
 Merged in set to #16750
comment:11 Changed 7 years ago by
 Commit changed from b69d63ff8b1ab648b71b86d840b666108de31053 to 240cc103d6c9e8e31ce2b8f8e335eae56ccc42f0
Branch pushed to git repo; I updated commit sha1. New commits:
240cc10  16719 reviewer's patch: attempt to fix previous patch

comment:12 Changed 7 years ago by
 Commit changed from 240cc103d6c9e8e31ce2b8f8e335eae56ccc42f0 to a1269fb79a1ffdd429596f74865a8cbb5d4ccc91
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

comment:13 Changed 7 years ago by
 Status changed from new to needs_review
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.
comment:14 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:15 Changed 7 years ago by
 Dependencies #16380 deleted
comment:16 Changed 7 years ago by
 Commit changed from a1269fb79a1ffdd429596f74865a8cbb5d4ccc91 to e82786b9ba853be2e8433d2798b62865d9769062
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

comment:17 Changed 7 years ago by
Note that this will conflict with #13982 for unordered_tuples
(FYI I handled GAP's output as strings differently).
comment:18 Changed 7 years ago by
 Dependencies set to #16750
 Merged in #16750 deleted
comment:19 Changed 7 years ago by
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.
comment:20 Changed 7 years ago by
 Commit changed from e82786b9ba853be2e8433d2798b62865d9769062 to 5b156ad3ed4d929c2eb03daf228d120e018a15be
Branch pushed to git repo; I updated commit sha1. New commits:
5b156ad  16719: revert change to unordered_tuples(), handled by 13982

comment:21 Changed 7 years ago by
For bell_number()
, I'm making the change at #17157, so you can remove that piece.
comment:22 Changed 7 years ago by
 Branch changed from u/rws/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py to u/jdemeyer/ticket/16719
 Created changed from 07/27/14 07:19:18 to 07/27/14 07:19:18
 Modified changed from 10/15/14 21:46:06 to 10/15/14 21:46:06
comment:23 Changed 7 years ago by
 Commit changed from 5b156ad3ed4d929c2eb03daf228d120e018a15be to 4339c5019b84ff5bf27c79100912511dd4aa37e7
 Dependencies changed from #16750 to #17157
 Reviewers set to Jeroen Demeyer
comment:24 Changed 7 years ago by
 Branch changed from u/jdemeyer/ticket/16719 to u/vbraun/ticket/16719
comment:25 Changed 7 years ago by
 Commit changed from 4339c5019b84ff5bf27c79100912511dd4aa37e7 to 9f4777d9bab0aba2fe50cadb0f72b6bc46e4ef77
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

comment:26 Changed 7 years ago by
 Reviewers changed from Jeroen Demeyer to Jeroen Demeyer, Volker Braun
 Status changed from needs_review to positive_review
comment:27 Changed 7 years ago by
 Summary changed from replace gap.eval with libgap.eval in combinat/combinat.py to replace gap.eval with libgap calls in combinat/combinat.py
comment:28 Changed 7 years ago by
 Commit changed from 9f4777d9bab0aba2fe50cadb0f72b6bc46e4ef77 to d6698e2c4d7a3be2ff6c189a1bb24e55dda61616
 Status changed from positive_review to needs_review
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_clifford15300' 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 alreadyclosed #17157 to resolve conflict

comment:29 Changed 7 years ago by
 Branch changed from u/vbraun/ticket/16719 to d6698e2c4d7a3be2ff6c189a1bb24e55dda61616
 Resolution set to fixed
 Status changed from needs_review to closed
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.