New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Binomial of integer (mod n) returns integer #12179
Comments
Attachment: 12179.patch.gz |
comment:1
Attached patch should add this functionality with no impact on speed of standard integer/float/etc binomial calculation. |
comment:2
Looks good to me: positive review. |
Author: Sam Scott |
comment:4
Attachment: 12179.2.patch.gz Patch added to deal with the case where the input was a primitive python int. Thanks to Colton (cpauderis) for catching that one. |
comment:5
The line
|
comment:6
The line
should end in two colons (for docbuilding). Furthermore,
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. |
Changed keywords from binomial coefficiant, modulo to binomial coefficiant, modulo sd35 |
Work Issues: rebase on top of #11417, reST formatting issue, improve efficiency |
comment:8
Patch is incompatible with #11417, which is already merged. |
Reviewer: Colton Pauderis, Johan Bosman, Marco Streng |
Dependencies: #11417 |
Changed keywords from binomial coefficiant, modulo sd35 to binomial coefficient modulo sd35 |
comment:9
Replying to @sagetrac-johanbosman:
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. |
comment:10
That should obviously be Pari, not Peri. |
comment:11
Replying to @sagetrac-scotts:
That sounds sensible, this is a bugfix patch and the inefficiency is not introduced by your patch. So if you don't want to, you don't have to improve the speed. However, since you're editing anyway, you might as well. It's up to you. The other issues
do need to be resolved though. For the first issue, after building Sage, use As for the second issue, you should not write two independent patches editing the same part of a file. They can't be applied after each other, because the second-to-be-applied can't find the piece of code that it should change. You should write your patch for #12179 on top of a copy of Sage that has #11417 applied. |
Attachment: 12179.3.patch.gz |
comment:12
Finally got around to reinstalling sage after a hard-drive failure. Hoping to get back on track with contributing to sage. Sorry for the incredibly slow response. Hopefully this should tie up this loose end. While I do agree that there is room for improving the speed of calculating binomial coefficients mod N, I don't feel like it's worth bloating the binomial function with multiple extra lines of code for something which doesn't seem to be used much. Perhaps it could be added as a feature at a later stage when the need is there. However, I feel that this patch adequately addresses the original issue: that elements are treated as integers and returned as such, with no attempt to return them to their original class. This could potentially help with other cases. Thanks for the advice with regards to the other issues. |
comment:14
Replying to @mstreng:
no, wait, I meant |
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
This comment has been minimized.
Changed dependencies from #11417 to none |
Changed author from Sam Scott to Sam Scott, Marco Streng |
This comment has been minimized.
This comment has been minimized.
comment:16
apply only 12179_new.patch |
comment:17
Attachment: 12179_new.patch.gz New version, but it screws up lots of symbolic things. Perhaps a few special cases, like binomial(n, n) always returning 1, will fix this. I'm done with this for now. |
comment:22
Replying to @mstreng:
Pari does this too.
Example with Pari:
|
comment:23
Hello, I just discover this ticket. During a cleanup in
Vincent |
This comment has been minimized.
This comment has been minimized.
comment:24
Replying to @videlec:
This should be So of the two points in the ticket description, the work in #17852 fixes the second one, but the first one is still open. |
comment:25
Replying to @mstreng:
Right! |
comment:26
Hi, Ticket #17852 is in pass to be positively reviewed. Let me summarize what will change when calling
Vincent |
Stopgaps: todo |
But
binomial(R(5), R(2))
is nonsense, both as an element of ZZ and as an element of R:On input
binomial(x, y)
, what Sage should do instead is the following:If the parent of y is Zmod(n) rather than ZZ, a
TypeError
should be raised.(This seems to be fixed by Cleanup in rings.arith and rings.integer #17852) If factorial(y) is zero or a zero-divisor in the parent of x, a
ZeroDivisionError
should be raised. This is automatic if one computes binomial(x, y) simply asApply:
Component: basic arithmetic
Keywords: binomial coefficient modulo sd35
Stopgaps: todo
Author: Sam Scott, Marco Streng
Reviewer: Colton Pauderis, Johan Bosman, Marco Streng
Issue created by migration from https://trac.sagemath.org/ticket/12179
The text was updated successfully, but these errors were encountered: