Opened 5 years ago

Closed 20 months ago

#17489 closed defect (wontfix)

factorial(algorithm=...) does not work as claimed

Reported by: rws Owned by:
Priority: major Milestone: sage-duplicate/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 rws)

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

  • Description modified (diff)

comment:2 follow-up: Changed 5 years ago by rws

Timing comparison:

  • (timeit) 103!: sympy: 3.38 µs, ginac: 11.6 µs, gmp: 11.8 µs, pari: 22.4 µs
  • (time) 106!: sympy: 10s, ginac: 200 ms, gmp: 190 ms, pari: 410 ms

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.2-0.4 seconds per call to factorial(106) 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.

Last edited 5 years ago by rws (previous) (diff)

comment:3 in reply to: ↑ 2 Changed 5 years ago by rws

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

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

  • Branch set to u/rws/remove_redundant_factorial___from_rings_arith_py

comment:6 Changed 5 years ago by rws

  • Authors set to Ralf Stephan
  • Commit set to c241edfedb553430b97b4a96a9b10658a53ce085
  • Status changed from new to needs_review

Found a way to use algorithm without abandoning the use of GinacFunction.


New commits:

4aef05817489: import factorial only from functions/other
c241edf17489: move factorial to functions; enable algorithms,hold keywords

comment:7 follow-up: Changed 5 years ago by jdemeyer

If you no longer use the py_factorial_py function, it should be deprecated.

comment:8 in reply to: ↑ 7 Changed 5 years ago by rws

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 follow-up: Changed 5 years ago by jdemeyer

If it's only used by doctests, it's not used :-)

comment:10 in reply to: ↑ 9 ; follow-up: Changed 5 years ago by rws

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

Replying to rws:

Replying to jdemeyer:

If it's only used by doctests, it's not used :-)

And remove the doctest?

No, add the deprecation message in the doctest.

comment:12 follow-up: Changed 5 years ago by jdemeyer

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

  • Cc kcrisman added
  • Reviewers set to Jeroen Demeyer

comment:14 Changed 5 years ago by git

  • Commit changed from c241edfedb553430b97b4a96a9b10658a53ce085 to 3b54c755b2da09d40872276d0d95d941ddcdea66

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

80274a1Merge branch 'develop' into t/17489/remove_redundant_factorial___from_rings_arith_py
3b54c7517489: deprecate superfluous functions

comment:15 in reply to: ↑ 12 Changed 5 years ago by rws

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

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

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 non-trivial 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.

Last edited 5 years ago by jdemeyer (previous) (diff)

comment:18 Changed 5 years ago by jdemeyer

See also #12289 and #15200.

comment:19 follow-up: Changed 5 years ago by jdemeyer

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 ; follow-up: Changed 5 years ago by rws

Replying to jdemeyer:

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.

When adding the missing rising/falling/sub/multi_factorial there is already the case for a separate file containing functions mainly defined over the integers---or two, one for number theoretic, the other combinatorial entries. So maybe not NumberTheoreticFunction but ZZDomainFunction in the file number_theoretic.py?

comment:21 follow-up: Changed 5 years ago by jdemeyer

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

Replying to jdemeyer:

I don't like ZZDomainFunction (why Domain?), what do you think of IntegerFunction? 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 follow-up: Changed 5 years ago by rws

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_()

Last edited 5 years ago by rws (previous) (diff)

comment:24 in reply to: ↑ 23 ; follow-up: Changed 5 years ago by jdemeyer

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

  • Dependencies set to #17531

Replying to jdemeyer:

If you agree with this, please open a new ticket for supporting a more general algorithm keyword.

See #17531.

comment:26 in reply to: ↑ 20 Changed 5 years ago by rws

...in the file number_theoretic.py?

Rather in combinatorial.py...

comment:27 Changed 5 years ago by jdemeyer

If we agree on the class IntegerFunction, then the file probably should be integerfunction.py also.

comment:28 Changed 5 years ago by jdemeyer

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

  • Branch changed from u/rws/remove_redundant_factorial___from_rings_arith_py to public/17489

comment:30 follow-up: Changed 5 years ago by rws

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

eaed76a17531: add _algorithm field to cdef class Function
bde83e217489: remove rings.arith.factorial; move functions.other.factorial to integer_function; implement IntegerGinacFunction; redirect imports, bindings
Last edited 5 years ago by rws (previous) (diff)

comment:31 in reply to: ↑ 30 Changed 5 years ago by rws

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/sage-devel/6wVipX3JPGU

comment:32 Changed 5 years ago by git

  • Commit changed from bde83e270170e5a006705568ea72c1513abf0315 to b33a16ceb903aed299cd419dbe207ac4b757afb2

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

b33a16c17489: fix bugs exposed by factorial now returning int

comment:33 Changed 5 years ago by rws

It seems that python ints returned by functions.factorial exposed several bugs in combinat.

comment:34 Changed 5 years ago by git

  • Commit changed from b33a16ceb903aed299cd419dbe207ac4b757afb2 to e50e40024cec70f7a5f32ad88cb5749c8e43df2a

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

e50e40017489: last doctests, cosmetics

comment:35 Changed 5 years ago by git

  • Commit changed from e50e40024cec70f7a5f32ad88cb5749c8e43df2a to 284470b209259928714b0ff91ac6f5b86746b157

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

284470b17489: negative int argument now returns -oo

comment:36 follow-up: Changed 5 years ago by tscrim

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

Replying to tscrim:

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.)

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

  • Commit changed from 284470b209259928714b0ff91ac6f5b86746b157 to 21c2e641380c0788ed7884cf4ed3e7021c32cff7

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

21c2e64Merge branch 'develop' into t/17489/public/17489

comment:39 Changed 5 years ago by kcrisman

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

  • Status changed from needs_review to needs_work

comment:41 Changed 5 years ago by rws

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

  • Milestone changed from sage-6.5 to sage-pending

comment:43 Changed 4 years ago by rws

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 catch algorithm, 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 in functions/integerfunction.py is the idea. The ticket #17531 would deal with this, but has unexpected pitfalls.

comment:44 Changed 3 years ago by rws

  • Authors Ralf Stephan deleted
  • Branch public/17489 deleted
  • Commit 21c2e641380c0788ed7884cf4ed3e7021c32cff7 deleted
  • Description modified (diff)
  • Milestone changed from sage-pending to sage-7.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 3 years ago by rws

  • Dependencies #17531 deleted
  • Description modified (diff)

comment:46 Changed 3 years ago by rws

  • Branch set to u/rws/factorial_algorithm______does_not_work_as_claimed

comment:47 Changed 3 years ago by rws

  • Authors set to Ralf Stephan
  • Commit set to b27a3c4e9cf1f0ebcd69196d25c75c003c501190
  • Status changed from needs_work to needs_review

Jeroen, are you still reviewer of this ticket?


New commits:

b27a3c417489: amend documentation

comment:48 Changed 23 months ago by rws

  • Branch u/rws/factorial_algorithm______does_not_work_as_claimed deleted
  • Commit b27a3c4e9cf1f0ebcd69196d25c75c003c501190 deleted
  • Milestone changed from sage-7.5 to sage-8.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 23 months ago by rws

  • Dependencies set to #24178

comment:50 Changed 23 months ago by rws

  • Authors Ralf Stephan deleted
  • Milestone changed from sage-8.2 to sage-duplicate/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 20 months ago by vdelecroix

  • Resolution set to wontfix
  • Status changed from positive_review to closed

closing positively reviewed duplicates

Note: See TracTickets for help on using tickets.