Opened 6 years ago
Closed 6 years ago
#16719 closed defect (fixed)
replace gap.eval with libgap calls in combinat/combinat.py
Reported by: | rws | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.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) | 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) <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
Change History (29)
comment:1 Changed 6 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 6 years ago by
- Description modified (diff)
comment:3 Changed 6 years ago by
- Description modified (diff)
- Keywords stirling added
comment:4 Changed 6 years ago by
- Dependencies set to #16380
comment:5 Changed 6 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) <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
comment:6 Changed 6 years ago by
- Branch set to u/rws/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py
comment:7 Changed 6 years ago by
- Cc vbraun added
- Commit set to 16922b5195624f1f2afd684b246a31fb00f5269e
New commits:
16922b5 | 16719: replace gap with libgap
|
comment:8 Changed 6 years ago by
- Commit changed from 16922b5195624f1f2afd684b246a31fb00f5269e to b69d63ff8b1ab648b71b86d840b666108de31053
comment:9 Changed 6 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 6 years ago by
- Dependencies changed from #16380, #16750 to #16380
- Merged in set to #16750
comment:11 Changed 6 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 6 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 6 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 6 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:15 Changed 6 years ago by
- Dependencies #16380 deleted
comment:16 Changed 6 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 6 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 6 years ago by
- Dependencies set to #16750
- Merged in #16750 deleted
comment:19 Changed 6 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 6 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 6 years ago by
For bell_number()
, I'm making the change at #17157, so you can remove that piece.
comment:22 Changed 6 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 6 years ago by
- Commit changed from 5b156ad3ed4d929c2eb03daf228d120e018a15be to 4339c5019b84ff5bf27c79100912511dd4aa37e7
- Dependencies changed from #16750 to #17157
- Reviewers set to Jeroen Demeyer
comment:24 Changed 6 years ago by
- Branch changed from u/jdemeyer/ticket/16719 to u/vbraun/ticket/16719
comment:25 Changed 6 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 6 years ago by
- Reviewers changed from Jeroen Demeyer to Jeroen Demeyer, Volker Braun
- Status changed from needs_review to positive_review
comment:27 Changed 6 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 6 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_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
|
comment:29 Changed 6 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.