Opened 4 years ago

Closed 4 years ago

#19510 closed enhancement (fixed)

asymptotic expansion generator for binomial(kn, n)

Reported by: dkrenn Owned by:
Priority: major Milestone: sage-7.1
Component: asymptotic expansions Keywords:
Cc: behackl, cheuberg Merged in:
Authors: Daniel Krenn Reviewers: Clemens Heuberger
Report Upstream: N/A Work issues:
Branch: c998922 (Commits) Commit: c9989221b159e595cfc2ae08077cc3b6757f477a
Dependencies: #19306, #19521, #19528, #19957 Stopgaps:

Description

Implement a generator for binomial(k*n, n).

Change History (22)

comment:1 Changed 4 years ago by dkrenn

  • Branch set to u/dkrenn/asy/generators-binomial

comment:2 Changed 4 years ago by dkrenn

  • Commit set to 221ad4f3ea14d1856ed432bacda948a718615639
  • Dependencies changed from #19306 to #19306, #19521

Last 10 new commits:

f0c7440use symbolic constants subring (instead of SR)
0d6cce3remove automatic parenthesing in parent_to_repr_short
3f5e1b1fix bug in split_str_by_op
6e366a5binomial_kn_n: change to symbolic constants subring (WIP)
ae1877crename binomial* --> Binomial*
f0ab41adelete code of binomial* since it was
559d1c4Merge branch 't/19306/asy/generators' into asy/generators-binomial
fd35046change base class to SageObject
532c41cwrite docstrings of Stirling generators
221ad4fMerge branch 't/19306/asy/generators' into asy/generators-binomial

comment:3 Changed 4 years ago by dkrenn

  • Dependencies changed from #19306, #19521 to #19306, #19521, #19528

comment:4 Changed 4 years ago by git

  • Commit changed from 221ad4f3ea14d1856ed432bacda948a718615639 to 4a27e66ce1f942ebe4f3ac91ee0c0cb431739052

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

a2b744dMerge branch 'coerce/inverse-action' into asy/generators-binomial
1bd2223make Binomial_kn_n really working
421e377mutable poset map: remove elements ``None``
1d28240term monoid: write change_parameter
2c37889correct a bug in change_parameter
bdcb72bwrite map_coefficients
2a0815dMerge branch 'asy/map_coefficients' into asy/generators-binomial
e93ce46simplify coefficients automatically and use the faster algorithm per default
f468de6docu
4a27e66result over QQ if skip-parameter given

comment:5 Changed 4 years ago by git

  • Commit changed from 4a27e66ce1f942ebe4f3ac91ee0c0cb431739052 to e59c71f0c97a00310b0c30864f38f457462c13e1

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

e59c71ftoc entry (at top of file)

comment:6 Changed 4 years ago by dkrenn

  • Status changed from new to needs_review

comment:7 Changed 4 years ago by git

  • Commit changed from e59c71f0c97a00310b0c30864f38f457462c13e1 to ea3dd35b42a60e491423b25f706ff50a4739e643

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

ea3dd35small bugfix

comment:8 Changed 4 years ago by cheuberg

  • Branch changed from u/dkrenn/asy/generators-binomial to u/cheuberg/asy/generators-binomial

comment:9 Changed 4 years ago by cheuberg

  • Commit changed from ea3dd35b42a60e491423b25f706ff50a4739e643 to 1529a4daf6eacfaac708816fdd5c4ee87fe127de
  • Milestone changed from sage-6.10 to sage-7.1

Merged latest version of #19306 to avoid doctest failure.


New commits:

cc256c8Trac #19306: remove old code
31e4dc4Trac #19306: other variables than n
a3fad56Trac #19306: fix error terms for low precision
a4c3f9dTrac #19306: Fix low precision for Stirling
eac4977Trac #19306: minor changes (cross-review and incorporate reviewer comments)
946a828Trac #19306: change % to .format
809d653Trac #19306: Merge tag '7.0' due to #19879
4d80eb3Trac #19306: sage.rings.arith -> sage.arith.all (after #19879)
1529a4dTrac #19510: Merge #19306 (due to #19879)

comment:10 Changed 4 years ago by git

  • Commit changed from 1529a4daf6eacfaac708816fdd5c4ee87fe127de to 5d9152ce307eafd280374cce90ff05c7fa2937c2

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

3e30659Trac #19510: modify constant factor: factor sqrt(k-1) is removed, too.
5d9152cTrac #19510: state constant factors/summands in Stirling and binomial

comment:11 follow-up: Changed 4 years ago by cheuberg

  • Reviewers set to Clemens Heuberger
  • Status changed from needs_review to needs_work

Reviewed the code (without its dependency #19521) and the documentation, but did not yet verify the final output of the doctests. I had to modify the "constant factor" in order to get rational coefficients when k-1 is not a square.

I am not happy with the growth group of the output:

  • (e^(n*log(n)))^(Symbolic Constants Subring) will never occur.
  • log(n)^(Symbolic Constants Subring) will never occur.
  • (e^n)^(Symbolic Constants Subring) is hard to read; actually, the only exponential factor that will ever occur is (k^k/(k-1)^(k-1))^n, so FractionField(k.parent())^n would be enough (so QQ^n in all examples). However, it is not clear to me how to implement this without pain.

comment:12 Changed 4 years ago by dkrenn

  • Branch changed from u/cheuberg/asy/generators-binomial to u/dkrenn/asy/generators-binomial

comment:13 in reply to: ↑ 11 Changed 4 years ago by dkrenn

  • Commit changed from 5d9152ce307eafd280374cce90ff05c7fa2937c2 to 10cd04bde3be402ea4c3550793475135096f27fb
  • Status changed from needs_work to needs_review

Replying to cheuberg:

Reviewed the code (without its dependency #19521) and the documentation, but did not yet verify the final output of the doctests. I had to modify the "constant factor" in order to get rational coefficients when k-1 is not a square.

I am not happy with the growth group of the output:

  • (e^(n*log(n)))^(Symbolic Constants Subring) will never occur.
  • log(n)^(Symbolic Constants Subring) will never occur.
  • (e^n)^(Symbolic Constants Subring) is hard to read; actually, the only exponential factor that will ever occur is (k^k/(k-1)^(k-1))^n, so FractionField(k.parent())^n would be enough (so QQ^n in all examples). However, it is not clear to me how to implement this without pain.

More or less complete rewrite of function.


Last 10 new commits:

1b62954Trac #19946: add doctests to document behavior
24c153cTrac #19946: reviewer commit: ReSt error
7918417Trac #19946: additional doctest
1471336Trac #19946: rewrite and improve explaination of 1b62954
9f9a23fTrac #19961: document rpow
101e4deMerge branch 'u/dkrenn/t/19961' of trac.sagemath.org:sage into t/19946
7179c78Trac #19946: link from general doc to detailed explaination
1259201Trac #19946: fix typo
37caf25Merge branch 'u/cheuberg/t/19946' of trac.sagemath.org:sage into t/19510/asy/generators-binomial
10cd04bTrac #19510: major rewrite of binomial kn over n

comment:14 Changed 4 years ago by cheuberg

  • Branch changed from u/dkrenn/asy/generators-binomial to u/cheuberg/asy/generators-binomial

comment:15 Changed 4 years ago by cheuberg

  • Commit changed from 10cd04bde3be402ea4c3550793475135096f27fb to 78bdd0f93c1c45c6b93fc631d99c95f7d79c76a7
  • Dependencies changed from #19306, #19521, #19528 to #19306, #19521, #19528, #19957

I reviewed this version.

I merged #19957 and added doctests using compare_with_values. Please cross-review and set to positive if you are satisfied.


Last 10 new commits:

7337e61Trac 19957 review: restructure part of the code and remove inner list to make it better readable
0632fd3Trac 19957 review: minor changes in doc
4a8ea9aTrac #19957: move see also blocks to position given in developer guide
9ea47b9Trac #19957: fix dead link
3d51289Trac #19957: Merge #19946 to avoid work-around
b606fdfTrac #19957: remove work-around for #19946
4346994Trac #19957: rename e to expansion in doctests
5d6e9b2Trac #19957: Introduce parameter relative tolerance
00eae5dMerge branch 't/19957/asy/compare-with-values' into t/19510/asy/generators-binomial
78bdd0fTrac #19510: additional doctests using compare_with_values

comment:16 Changed 4 years ago by dkrenn

  • Status changed from needs_review to positive_review

comment:17 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

http://build.sagedev.org/release/builders/%20%20fast%20Oxford%20arando%20%28Ubuntu%2013.04%20i686%29%20incremental/builds/797/steps/shell_4/logs/stdio

sage -t --long src/sage/rings/asymptotic/asymptotic_expansion_generators.py
**********************************************************************
File "src/sage/rings/asymptotic/asymptotic_expansion_generators.py", line 141, in sage.rings.asymptotic.asymptotic_expansion_generators.AsymptoticExpansionGenerators.Stirling
Failed example:
    expansion.compare_with_values(n, lambda x: x.factorial(), [5, 10, 20])
Expected:
    [(5, 0.00675841118?), (10, 0.0067589306?), (20, 0.006744925?)]
Got:
    [(5, 0.006758411181?), (10, 0.0067589306?), (20, 0.006744925?)]
**********************************************************************
1 item had failures:
   1 of  11 in sage.rings.asymptotic.asymptotic_expansion_generators.AsymptoticExpansionGenerators.Stirling
    [45 tests, 1 failure, 8.78 s]

comment:18 Changed 4 years ago by git

  • Commit changed from 78bdd0f93c1c45c6b93fc631d99c95f7d79c76a7 to 2b713794ab0c19bc98fb4088a32fdb5b93ebc6e6

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

2b71379Trac #19510: specify relative tolerance for doctests

comment:19 Changed 4 years ago by cheuberg

  • Status changed from needs_work to needs_review

Added relative tolerance.

comment:20 Changed 4 years ago by dkrenn

  • Branch changed from u/cheuberg/asy/generators-binomial to u/dkrenn/asy/generators-binomial

comment:21 Changed 4 years ago by dkrenn

  • Commit changed from 2b713794ab0c19bc98fb4088a32fdb5b93ebc6e6 to c9989221b159e595cfc2ae08077cc3b6757f477a
  • Status changed from needs_review to positive_review

New commits:

c998922Trac #19510: constitent spacings

comment:22 Changed 4 years ago by vbraun

  • Branch changed from u/dkrenn/asy/generators-binomial to c9989221b159e595cfc2ae08077cc3b6757f477a
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.