#12179: Binomial of integer (mod n) returns integer
----------------------------------------------------------------------------------+
Reporter: scotts
| Owner: AlexGhitza
Type: defect
| Status: needs_work
Priority: major
| Milestone: sage-4.8
Component: basic arithmetic
| Keywords: binomial coefficient modulo sd35
Work_issues: rebase on top of #11417, reST formatting issue, improve
efficiency | Upstream: N/A
Reviewer: Colton Pauderis, Johan Bosman, Marco Streng
| Author: Sam Scott
Merged:
| Dependencies: #11417
----------------------------------------------------------------------------------+
Comment(by scotts):
Replying to [comment:6 johanbosman]:
> Furthermore,
> {{{
> return x.parent()(binomial(ZZ(x), m, **kwds))
> }}}
> is inefficient when computing modulo a small number n: the binomial
coefficient over ZZ may be huge, whereas its reduction modulo n will be
small. It is therefore better to to the entire calculation modulo n.
I definitely agree, the changes I was proposing were to simply try and
return a more sensible type.
Since I am new to sage, I was trying to keep as much of the existing
algorithm intact, so that it wouldn't have any unexpected behaviour. For
example, currently it seems that sage uses Peri to calculate the usual
binomial coefficient. So I wasn't sure if the implementation for modulo n
would belong here.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12179#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
