Opened 7 years ago
Closed 4 years ago
#17489 closed defect (wontfix)
factorial(algorithm=...) does not work as claimed
Reported by:  rws  Owned by:  

Priority:  major  Milestone:  sageduplicate/invalid/wontfix 
Component:  symbolics  Keywords:  integer symbolic function 
Cc:  kcrisman, nthiery  Merged in:  
Authors:  Reviewers:  Jeroen Demeyer  
Report Upstream:  N/A  Work issues:  
Branch:  Commit:  
Dependencies:  #24178  Stopgaps: 
Description (last modified by )
It's a defect because the reference/misc/sage/rings/arith.html
documentation makes users expect the algorithm
keyword to work but
sage: y=factorial(10^6,algorithm='gmp')  ... TypeError: __call__() got an unexpected keyword argument 'algorithm'
As the implementation of the algorithm keyword in symbolic function seems difficult (#17531) as pragmatic solution would be to accept that for algorithm to work the arith version of factorial must be explicitly called, see https://trac.sagemath.org/ticket/19461#comment:9 for the general argument.
The rings
version apparently gets overwritten on import and the function/
does not accept/transfer the algorithm
keyword.
Change History (51)
comment:1 Changed 7 years ago by
 Description modified (diff)
comment:2 followup: ↓ 3 Changed 7 years ago by
comment:3 in reply to: ↑ 2 Changed 7 years ago by
Replying to rws:
Timing comparison
In fact, the functions/other
version supposedly calling pynac/ginac actually indirectly calls the rings/arith
version, i.e., gmp.
So, there will be no speed changes with this ticket.
This, however, means also that the problem with passing algorithm
is due to Function_factorial
being a GinacFunction
. Of course, a GinacFunction
would only use Ginac, so it figures.
comment:4 Changed 7 years ago by
It looks like #9240 abandoned GiNaC behaviour for factorial
. Then why keep this as GinacFunction
and go through calling rings.arith.factorial
via py_factorial_py
?
comment:5 Changed 7 years ago by
 Branch set to u/rws/remove_redundant_factorial___from_rings_arith_py
comment:6 Changed 7 years ago by
 Commit set to c241edfedb553430b97b4a96a9b10658a53ce085
 Status changed from new to needs_review
comment:7 followup: ↓ 8 Changed 7 years ago by
If you no longer use the py_factorial_py
function, it should be deprecated.
comment:8 in reply to: ↑ 7 Changed 7 years ago by
Replying to jdemeyer:
If you no longer use the
py_factorial_py
function, it should be deprecated.
Sure? It is used by the py_factorial
doctest.
comment:9 followup: ↓ 10 Changed 7 years ago by
If it's only used by doctests, it's not used :)
comment:10 in reply to: ↑ 9 ; followup: ↓ 11 Changed 7 years ago by
Replying to jdemeyer:
If it's only used by doctests, it's not used :)
And remove the doctest?
In the same file there are more such wrappers: doublefactorial
,test_binomial
,py_real_for_doctests
etc.
comment:11 in reply to: ↑ 10 Changed 7 years ago by
comment:12 followup: ↓ 15 Changed 7 years ago by
 Status changed from needs_review to needs_work
Also, instead of removing the factorial function from rings/arith.py
, it should be deprecated (or perhaps a lazy import with deprecation).
comment:13 Changed 7 years ago by
 Cc kcrisman added
 Reviewers set to Jeroen Demeyer
comment:14 Changed 7 years ago by
 Commit changed from c241edfedb553430b97b4a96a9b10658a53ce085 to 3b54c755b2da09d40872276d0d95d941ddcdea66
comment:15 in reply to: ↑ 12 Changed 7 years ago by
 Status changed from needs_work to needs_review
Replying to jdemeyer:
Replying to rws:
Replying to jdemeyer: And remove the doctest?
No, add the deprecation message in the doctest.
Not possible because only the first message is printed. I removed the doctests.
Also, instead of removing the factorial function from
rings/arith.py
, it should be deprecated (or perhaps a lazy import with deprecation).
Any import of factorial
is overwritten by sage.functions.other.factorial
comment:16 Changed 7 years ago by
 Status changed from needs_review to needs_work
This is overly complicated:
try: x_in_ZZ = ZZ(x) coercion_success = True except TypeError: coercion_success = False if coercion_success and x_in_ZZ >= 0: return ZZ(x).factorial() else: return py_tgamma(x+1)
Why not
try: x = ZZ(x) except TypeError: pass else: if x >= 0: return x.factorial() return py_tgamma(x+1)
Also: the :trac:`9240`
syntax should be used in docstrings, not comments in code, so please revert that.
comment:17 Changed 7 years ago by
I'm not happy with the change of _eval_
to __call__
. You cannot expect every function which wants an algorithm
argument to override __call__
. Especially now that more and more nontrivial logic is going into the __call__
method of BuiltinFunction
.
It might make a lot more sense to move all this algorithm
stuff to a custom _evalf_
function, which does support an algorithm
argument.
In order words: I think the general question of how to handle algorithm
arguments in symbolic calls should be answered first.
comment:18 Changed 7 years ago by
comment:19 followup: ↓ 20 Changed 7 years ago by
Another idea I had which should probably be done first is to make a new class NumberTheoreticFunction
which would include the factorial
and binomial
function. That class could then be customized to use _evalf_
when given integers as input.
comment:20 in reply to: ↑ 19 ; followup: ↓ 26 Changed 7 years ago by
Replying to jdemeyer:
Another idea I had which should probably be done first is to make a new class
NumberTheoreticFunction
which would include thefactorial
andbinomial
function. That class could then be customized to use_evalf_
when given integers as input.
When adding the missing rising/falling/sub/multi_factorial
there is already the case for a separate file containing functions mainly defined over the integersor two, one for number theoretic, the other combinatorial entries. So maybe not NumberTheoreticFunction
but ZZDomainFunction
in the file number_theoretic.py
?
comment:21 followup: ↓ 22 Changed 7 years ago by
I don't like ZZDomainFunction
(why Domain
?), what do you think of IntegerFunction
? And the new file is certainly a very good idea.
comment:22 in reply to: ↑ 21 Changed 7 years ago by
Replying to jdemeyer:
I don't like
ZZDomainFunction
(whyDomain
?), what do you think ofIntegerFunction
? And the new file is certainly a very good idea.
"Given a function f:X→Y, the set X is the domain of f; the set Y is the codomain of f." But IntegerFunction
seems fine too. I guess I will have to override BuiltinFunction
methods somehow...
comment:23 followup: ↓ 24 Changed 7 years ago by
The algorithm
keyword can be given 1. as __call__
keyword, or 2. as n()
keyword. Do I understand you correctly that you don't want to have scenario 1?
EDIT: cannot be, as that would mean n()
is always needed to get numerics. So __call__
just hands it to _evalf_or_eval_()
comment:24 in reply to: ↑ 23 ; followup: ↓ 25 Changed 7 years ago by
Replying to rws:
Do I understand you correctly that you don't want to have scenario 1?
I didn't say that. I just said that I don't want an algorithm
keyword only for factorial()
. I don't want a "solution" which needs to treat factorial()
in a special way.
If you agree with this, please open a new ticket for supporting a more general algorithm
keyword.
comment:25 in reply to: ↑ 24 Changed 7 years ago by
 Dependencies set to #17531
comment:26 in reply to: ↑ 20 Changed 7 years ago by
...in the file
number_theoretic.py
?
Rather in combinatorial.py
...
comment:27 Changed 7 years ago by
If we agree on the class IntegerFunction
, then the file probably should be integerfunction.py
also.
comment:28 Changed 7 years ago by
A different bug concerning factorial
:
sage: parent(factorial(QQ(4))) Integer Ring
I think this should respect the parent and return a element of QQ
.
comment:29 Changed 7 years ago by
 Branch changed from u/rws/remove_redundant_factorial___from_rings_arith_py to public/17489
comment:30 followup: ↓ 31 Changed 7 years ago by
 Commit changed from 3b54c755b2da09d40872276d0d95d941ddcdea66 to bde83e270170e5a006705568ea72c1513abf0315
 Keywords integer symbolic function added
 Status changed from needs_work to needs_review
sage t long src/sage/combinat/partition.py # 3 doctests failed sage t long src/sage/combinat/skew_tableau.py # 5 doctests failed sage t long src/sage/combinat/permutation.py # 2 doctests failed sage t long src/sage/combinat/six_vertex_model.py # 1 doctest failed sage t long src/sage/combinat/sloane_functions.py # 5 doctests failed sage t long src/sage/combinat/alternating_sign_matrix.py # 5 doctests failed
Still, some odd doctest errors but basically ready for review. EDIT: Also, some doctests missing in integer_function.py
.
New commits:
eaed76a  17531: add _algorithm field to cdef class Function

bde83e2  17489: remove rings.arith.factorial; move functions.other.factorial to integer_function; implement IntegerGinacFunction; redirect imports, bindings

comment:31 in reply to: ↑ 30 Changed 7 years ago by
Still, some odd doctest errors...
They turned out to be more resilient than I thought. A plea for help: https://groups.google.com/forum/?hl=en#!topic/sagedevel/6wVipX3JPGU
comment:32 Changed 7 years ago by
 Commit changed from bde83e270170e5a006705568ea72c1513abf0315 to b33a16ceb903aed299cd419dbe207ac4b757afb2
Branch pushed to git repo; I updated commit sha1. New commits:
b33a16c  17489: fix bugs exposed by factorial now returning int

comment:33 Changed 7 years ago by
It seems that python ints returned by functions.factorial exposed several bugs in combinat.
comment:34 Changed 7 years ago by
 Commit changed from b33a16ceb903aed299cd419dbe207ac4b757afb2 to e50e40024cec70f7a5f32ad88cb5749c8e43df2a
Branch pushed to git repo; I updated commit sha1. New commits:
e50e400  17489: last doctests, cosmetics

comment:35 Changed 7 years ago by
 Commit changed from e50e40024cec70f7a5f32ad88cb5749c8e43df2a to 284470b209259928714b0ff91ac6f5b86746b157
Branch pushed to git repo; I updated commit sha1. New commits:
284470b  17489: negative int argument now returns oo

comment:36 followup: ↓ 37 Changed 7 years ago by
 Cc nthiery added
I'm not completely sure about changing the test in finite_enumerated_sets
to also allow for int
's as the (untrained) user might unexpectedly do a division and get 0 but is expecting a fraction. I think the better solution is to actually change the output of the cardinality
to be in ZZ
, and I'll be happy to make this change. (In fact, I think a doctest in that file is going to fail because of this change.)
comment:37 in reply to: ↑ 36 Changed 7 years ago by
Replying to tscrim:
I'm not completely sure about changing the test in
finite_enumerated_sets
to also allow forint
's as the (untrained) user might unexpectedly do a division and get 0 but is expecting a fraction. I think the better solution is to actually change the output of thecardinality
to be inZZ
, and I'll be happy to make this change. (In fact, I think a doctest in that file is going to fail because of this change.)
Sorry to have been unresponsive. Please go ahead with your plan. Can I consider my code part to be reviewed with this?
comment:38 Changed 7 years ago by
 Commit changed from 284470b209259928714b0ff91ac6f5b86746b157 to 21c2e641380c0788ed7884cf4ed3e7021c32cff7
Branch pushed to git repo; I updated commit sha1. New commits:
21c2e64  Merge branch 'develop' into t/17489/public/17489

comment:39 Changed 7 years ago by
I didn't say that. I just said that I don't want an algorithm keyword only for factorial(). I don't want a "solution" which needs to treat factorial() in a special way.
Hmm. After thinking about this, I would like to suggest that factorial
is a pretty special example. It's not a typical function of this type (even if we do make it like gamma
in the end. It certainly shouldn't be in .n()
since we want integer output from the algorithms (right?).
comment:40 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:41 Changed 7 years ago by
Can this slowdown be explained?
sage: from sage.rings.arith import factorial as arith_factorial sage: %timeit arith_factorial(10) 1000000 loops, best of 3: 474 ns per loop sage: %timeit factorial(10) 1000000 loops, best of 3: 1.02 µs per loop
comment:42 Changed 7 years ago by
 Milestone changed from sage6.5 to sagepending
comment:43 Changed 6 years ago by
To summarize:
 the "arith" version moved to
src/sage/arith/misc.py
 the use of
py_factorial_py
cannot be deprecated so doctests using it must be deleted right away (adding the deprecation message in the doctest is not possible because only the first message is printed)  deprecating the "arith" version will not print a deprecation message for interactive users because (as the ticket states the arith version apparently gets overwritten on import). Maybe the deprecation shows if one imports directly from arith
 do not use
__call__
to catchalgorithm
, use_evalf_
 the general question of how to handle algorithm arguments in symbolic calls should be answered first, meaning no special solution just for factorial. Having an abstract
IntegerFunction
infunctions/integerfunction.py
is the idea. The ticket #17531 would deal with this, but has unexpected pitfalls.
comment:44 Changed 6 years ago by
 Branch public/17489 deleted
 Commit 21c2e641380c0788ed7884cf4ed3e7021c32cff7 deleted
 Description modified (diff)
 Milestone changed from sagepending to sage7.5
 Summary changed from remove redundant factorial() from rings/arith.py to factorial(algorithm=...) does not work as claimed
In order to make some progress on the original issue I removed the demand to replace arith/factorial
by function/factorial
. This ticket is now entirely about factorial(algorithm=)
. See #21560 for the negative integer argument issue.
comment:45 Changed 5 years ago by
 Dependencies #17531 deleted
 Description modified (diff)
comment:46 Changed 5 years ago by
 Branch set to u/rws/factorial_algorithm______does_not_work_as_claimed
comment:47 Changed 5 years ago by
 Commit set to b27a3c4e9cf1f0ebcd69196d25c75c003c501190
 Status changed from needs_work to needs_review
comment:48 Changed 4 years ago by
 Branch u/rws/factorial_algorithm______does_not_work_as_claimed deleted
 Commit b27a3c4e9cf1f0ebcd69196d25c75c003c501190 deleted
 Milestone changed from sage7.5 to sage8.2
 Status changed from needs_review to needs_work
I think we are coming to the conclusion that functions with additional keywords (other than hold
) need to be implemented as global interface function + symbolic specialization pair. This split has proven beneficial to #24554 as well. Whether the global interfaces all reside in arith/
or in function/
may have to be decided, or maybe not.
comment:49 Changed 4 years ago by
 Dependencies set to #24178
comment:50 Changed 4 years ago by
 Milestone changed from sage8.2 to sageduplicate/invalid/wontfix
 Status changed from needs_work to positive_review
The issue was moot because the algorithm
keyword is only supported in the arith/
version of factorial/
so just import it.
comment:51 Changed 4 years ago by
 Resolution set to wontfix
 Status changed from positive_review to closed
closing positively reviewed duplicates
Timing comparison:
Here, sympy caches the result (or the computation), so subsequent calls with the same argument are fast. In contrast, the other programs always use 0.20.4 seconds per call to factorial(10^{6}) so, by wrapping in a @cached function, they would be as fast as sympy in followup calls.
This clearly shows sympy is not up to it, EDIT: and this ticket will speed up many computations 2x.