Opened 5 years ago

Closed 5 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 rws)

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 5 years ago by rws

  • 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 5 years ago by rws

  • Description modified (diff)

comment:3 Changed 5 years ago by rws

  • Description modified (diff)
  • Keywords stirling added

comment:4 Changed 5 years ago by tscrim

  • Dependencies set to #16380

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.

comment:5 Changed 5 years ago by rws

  • 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 5 years ago by rws

  • Branch set to u/rws/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py

comment:7 Changed 5 years ago by vbraun

  • Cc vbraun added
  • Commit set to 16922b5195624f1f2afd684b246a31fb00f5269e

New commits:

16922b516719: replace gap with libgap

comment:8 Changed 5 years ago by git

  • Commit changed from 16922b5195624f1f2afd684b246a31fb00f5269e to b69d63ff8b1ab648b71b86d840b666108de31053

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

843ba48Convert Gap chars into Python strings
b69d63fMerge 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

comment:9 Changed 5 years ago by rws

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 5 years ago by rws

  • Authors set to Ralf Stephan
  • Dependencies changed from #16380, #16750 to #16380
  • Merged in set to #16750

comment:11 Changed 5 years ago by git

  • Commit changed from b69d63ff8b1ab648b71b86d840b666108de31053 to 240cc103d6c9e8e31ce2b8f8e335eae56ccc42f0

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

240cc1016719 reviewer's patch: attempt to fix previous patch

comment:12 Changed 5 years ago by git

  • Commit changed from 240cc103d6c9e8e31ce2b8f8e335eae56ccc42f0 to a1269fb79a1ffdd429596f74865a8cbb5d4ccc91

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

47f0796Merge branch 'develop' into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py
7cc26d5Improve GAP String handling
6fe1fc5Treat the empty GAP list as list and not as string
6a4892dMerge branch 't/16750/libgap_fails_converting_string_gapelements_to_sage' into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py
a1269fb16719: unordered_tuples() distinguishes now between set types

comment:13 Changed 5 years ago by rws

  • 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 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:15 Changed 5 years ago by kcrisman

  • Dependencies #16380 deleted

comment:16 Changed 5 years ago by git

  • Commit changed from a1269fb79a1ffdd429596f74865a8cbb5d4ccc91 to e82786b9ba853be2e8433d2798b62865d9769062

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

e82786bMerge branch 'develop' into t/16719/replace_gap_eval_with_libgap_eval_in_combinat_combinat_py

comment:17 Changed 5 years ago by tscrim

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

comment:18 Changed 5 years ago by tscrim

  • Dependencies set to #16750
  • Merged in #16750 deleted

comment:19 Changed 5 years ago by rws

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 5 years ago by git

  • Commit changed from e82786b9ba853be2e8433d2798b62865d9769062 to 5b156ad3ed4d929c2eb03daf228d120e018a15be

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

5b156ad16719: revert change to unordered_tuples(), handled by 13982

comment:21 Changed 5 years ago by jdemeyer

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

comment:22 Changed 5 years ago by jdemeyer

  • 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 5 years ago by jdemeyer

  • Commit changed from 5b156ad3ed4d929c2eb03daf228d120e018a15be to 4339c5019b84ff5bf27c79100912511dd4aa37e7
  • Dependencies changed from #16750 to #17157
  • Reviewers set to Jeroen Demeyer

Reviewer patch needs review.


New commits:

0266cefImprove formula for Bell numbers
fd22966Merge branch 'ticket/17157' into ticket/16719
4339c50Remove superfluous type conversions, use libgap for unordered_tuples()

comment:24 Changed 5 years ago by vbraun

  • Branch changed from u/jdemeyer/ticket/16719 to u/vbraun/ticket/16719

comment:25 Changed 5 years ago by vbraun

  • 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:

9f4777dBeautify libgap calls

comment:26 Changed 5 years ago by jdemeyer

  • Reviewers changed from Jeroen Demeyer to Jeroen Demeyer, Volker Braun
  • Status changed from needs_review to positive_review

comment:27 Changed 5 years ago by jdemeyer

  • 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 5 years ago by git

  • 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:

34c9b4cChanges from the reviewers.
b47af6aA minor tweaking of the doc.
53a9d7eFamilies return output based on order of variable names. Fixed coercion issue.
339b71dFixed some typos.
3ce3f6aMerge branch 'public/algebras/weyl_clifford-15300' of git://trac.sagemath.org/sage into clifford
8698275lifting bilinear forms onto exterior algebras
a002f4bSome tweaks to lifted_bilinear_form and fixed doctest.
ff27bdcfurther fixes
330617cMerge commit 'ff27bdc5d87967d0e7fd5c1305cef4340db816c7' into ticket/17157
d6698e2Merge already-closed #17157 to resolve conflict

comment:29 Changed 5 years ago by vbraun

  • Branch changed from u/vbraun/ticket/16719 to d6698e2c4d7a3be2ff6c189a1bb24e55dda61616
  • Resolution set to fixed
  • Status changed from needs_review to closed
Note: See TracTickets for help on using tickets.