Efficient and accurate approximatiion of logarithm of binomial coefficients The 2019 Stack Overflow Developer Survey Results Are InWeighted sum of ratio of partial sum of binomial coefficientsStirling Binomial PolynomialIs there an efficient/low-complexity extension of Gauss-Hermite quadratures to N dimensions where N is not too large?Exponential series approximationFind the close form of a summation with binomial coefficients and fractionsnumerical optimization algorithm with approximate Gradient and Hessian only!Asymptotic expansion of a sum containing binomial coefficientsWhen to use forward or central difference approximations?Inequality with Sum of Binomial CoefficientsFast Evaluation of Multiple Binomial Coefficients
Button changing it's text & action. Good or terrible?
How can I autofill dates in Excel excluding Sunday?
Is a "Democratic" Oligarchy-Style System Possible?
Delete all lines which don't have n characters before delimiter
"as much details as you can remember"
Lightning Grid - Columns and Rows?
What is the motivation for a law requiring 2 parties to consent for recording a conversation
When should I buy a clipper card after flying to OAK?
Why isn't airport relocation done gradually?
Can we generate random numbers using irrational numbers like π and e?
How to support a colleague who finds meetings extremely tiring?
Can you compress metal and what would be the consequences?
What tool would a Roman-age civilization have for the breaking of silver and other metals into dust?
What is the most effective way of iterating a std::vector and why?
Worn-tile Scrabble
One word riddle: Vowel in the middle
The difference between dialogue marks
Output the Arecibo Message
Resizing object distorts it (Illustrator CC 2018)
Why hard-Brexiteers don't insist on a hard border to prevent illegal immigration after Brexit?
Why do UK politicians seemingly ignore opinion polls on Brexit?
Identify boardgame from Big movie
Shouldn't "much" here be used instead of "more"?
Is there a symbol for a right arrow with a square in the middle?
Efficient and accurate approximatiion of logarithm of binomial coefficients
The 2019 Stack Overflow Developer Survey Results Are InWeighted sum of ratio of partial sum of binomial coefficientsStirling Binomial PolynomialIs there an efficient/low-complexity extension of Gauss-Hermite quadratures to N dimensions where N is not too large?Exponential series approximationFind the close form of a summation with binomial coefficients and fractionsnumerical optimization algorithm with approximate Gradient and Hessian only!Asymptotic expansion of a sum containing binomial coefficientsWhen to use forward or central difference approximations?Inequality with Sum of Binomial CoefficientsFast Evaluation of Multiple Binomial Coefficients
$begingroup$
I am searching for an efficient and accurate way to approximate the logarithm of binomial coefficients since I have to deal with extremely large numbers in C++. Using Stirling approximation, I am able to compute values very fast:
$lnbinomnk approx ncdot ln(n) - mcdot ln(k) - (n-k)cdot ln(n-k) + frac12cdot (ln(n) - ln(k) - ln(n-k) - ln(2pi))$
However, the approximation is not very accurate. Since I am not very strong in numerical analysis, I would like to know if there is a better way to approximate $lnbinomnk$.
Any help would be much appreciated.
numerical-methods logarithms binomial-coefficients approximation
edited Apr 7 at 1:42
Roddy MacPhee
740118
asked Apr 6 at 20:22
PhilPhil
83
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I am searching for an efficient and accurate way to approximate the logarithm of binomial coefficients since I have to deal with extremely large numbers in C++. Using Stirling approximation, I am able to compute values very fast:
$lnbinomnk approx ncdot ln(n) - mcdot ln(k) - (n-k)cdot ln(n-k) + frac12cdot (ln(n) - ln(k) - ln(n-k) - ln(2pi))$
However, the approximation is not very accurate. Since I am not very strong in numerical analysis, I would like to know if there is a better way to approximate $lnbinomnk$.
Any help would be much appreciated.
numerical-methods logarithms binomial-coefficients approximation
edited Apr 7 at 1:42
Roddy MacPhee
740118
asked Apr 6 at 20:22
PhilPhil
83
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
2
$begingroup$
Show a concrete example where the approximation is poor. If $ n $ , $ k $ and $ n-k $ are all large, the approximation should be good. Additionally, where is $ k $ in the approximation ?
$endgroup$
– Peter
Apr 6 at 20:25
$begingroup$
In PARI/GP, you can use the lngamma-command for very accurate logarithms of huge binomial coefficients.
$endgroup$
– Peter
Apr 6 at 20:27
1
$begingroup$
Crosspost from stackoverflow.com/questions/55552775/…, there also with the specification that $nsim 10^7$.
$endgroup$
– LutzL
Apr 6 at 20:33
$begingroup$
@ LutzL: I have to apologize for the crosspost - I wasn't sure where to post this problem and since it is a computational as well as a numerical issue, I thought it might be appropriate for both sections. I should have chosen one, so indeed a beginner's mistake from my side. @ Peter: Thank you very much for this! This might actually do the trick.
$endgroup$
– Phil
Apr 7 at 1:35
add a comment |
$begingroup$
I am searching for an efficient and accurate way to approximate the logarithm of binomial coefficients since I have to deal with extremely large numbers in C++. Using Stirling approximation, I am able to compute values very fast:
$lnbinomnk approx ncdot ln(n) - mcdot ln(k) - (n-k)cdot ln(n-k) + frac12cdot (ln(n) - ln(k) - ln(n-k) - ln(2pi))$
However, the approximation is not very accurate. Since I am not very strong in numerical analysis, I would like to know if there is a better way to approximate $lnbinomnk$.
Any help would be much appreciated.
numerical-methods logarithms binomial-coefficients approximation
edited Apr 7 at 1:42
Roddy MacPhee
740118
asked Apr 6 at 20:22
PhilPhil
83
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I am searching for an efficient and accurate way to approximate the logarithm of binomial coefficients since I have to deal with extremely large numbers in C++. Using Stirling approximation, I am able to compute values very fast:
$lnbinomnk approx ncdot ln(n) - mcdot ln(k) - (n-k)cdot ln(n-k) + frac12cdot (ln(n) - ln(k) - ln(n-k) - ln(2pi))$
However, the approximation is not very accurate. Since I am not very strong in numerical analysis, I would like to know if there is a better way to approximate $lnbinomnk$.
Any help would be much appreciated.
numerical-methods logarithms binomial-coefficients approximation
numerical-methods logarithms binomial-coefficients approximation
edited Apr 7 at 1:42
Roddy MacPhee
740118
asked Apr 6 at 20:22
PhilPhil
83
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Apr 7 at 1:42
Roddy MacPhee
740118
asked Apr 6 at 20:22
PhilPhil
83
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited Apr 7 at 1:42
Roddy MacPhee
740118
edited Apr 7 at 1:42
Roddy MacPhee
740118
edited Apr 7 at 1:42
Roddy MacPhee
740118
740118
asked Apr 6 at 20:22
PhilPhil
83
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked Apr 6 at 20:22
PhilPhil
83
asked Apr 6 at 20:22
PhilPhil
83
83
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Phil is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
2
$begingroup$
Show a concrete example where the approximation is poor. If $ n $ , $ k $ and $ n-k $ are all large, the approximation should be good. Additionally, where is $ k $ in the approximation ?
$endgroup$
– Peter
Apr 6 at 20:25
$begingroup$
In PARI/GP, you can use the lngamma-command for very accurate logarithms of huge binomial coefficients.
$endgroup$
– Peter
Apr 6 at 20:27
1
$begingroup$
Crosspost from stackoverflow.com/questions/55552775/…, there also with the specification that $nsim 10^7$.
$endgroup$
– LutzL
Apr 6 at 20:33
$begingroup$
@ LutzL: I have to apologize for the crosspost - I wasn't sure where to post this problem and since it is a computational as well as a numerical issue, I thought it might be appropriate for both sections. I should have chosen one, so indeed a beginner's mistake from my side. @ Peter: Thank you very much for this! This might actually do the trick.
$endgroup$
– Phil
Apr 7 at 1:35
add a comment |
2
$begingroup$
Show a concrete example where the approximation is poor. If $ n $ , $ k $ and $ n-k $ are all large, the approximation should be good. Additionally, where is $ k $ in the approximation ?
$endgroup$
– Peter
Apr 6 at 20:25
$begingroup$
In PARI/GP, you can use the lngamma-command for very accurate logarithms of huge binomial coefficients.
$endgroup$
– Peter
Apr 6 at 20:27
1
$begingroup$
Crosspost from stackoverflow.com/questions/55552775/…, there also with the specification that $nsim 10^7$.
$endgroup$
– LutzL
Apr 6 at 20:33
$begingroup$
@ LutzL: I have to apologize for the crosspost - I wasn't sure where to post this problem and since it is a computational as well as a numerical issue, I thought it might be appropriate for both sections. I should have chosen one, so indeed a beginner's mistake from my side. @ Peter: Thank you very much for this! This might actually do the trick.
$endgroup$
– Phil
Apr 7 at 1:35
2
2
$begingroup$
Show a concrete example where the approximation is poor. If $ n $ , $ k $ and $ n-k $ are all large, the approximation should be good. Additionally, where is $ k $ in the approximation ?
$endgroup$
– Peter
Apr 6 at 20:25
$begingroup$
Show a concrete example where the approximation is poor. If $ n $ , $ k $ and $ n-k $ are all large, the approximation should be good. Additionally, where is $ k $ in the approximation ?
$endgroup$
– Peter
Apr 6 at 20:25
$begingroup$
In PARI/GP, you can use the lngamma-command for very accurate logarithms of huge binomial coefficients.
$endgroup$
– Peter
Apr 6 at 20:27
$begingroup$
In PARI/GP, you can use the lngamma-command for very accurate logarithms of huge binomial coefficients.
$endgroup$
– Peter
Apr 6 at 20:27
1
1
$begingroup$
Crosspost from stackoverflow.com/questions/55552775/…, there also with the specification that $nsim 10^7$.
$endgroup$
– LutzL
Apr 6 at 20:33
$begingroup$
Crosspost from stackoverflow.com/questions/55552775/…, there also with the specification that $nsim 10^7$.
$endgroup$
– LutzL
Apr 6 at 20:33
$begingroup$
@ LutzL: I have to apologize for the crosspost - I wasn't sure where to post this problem and since it is a computational as well as a numerical issue, I thought it might be appropriate for both sections. I should have chosen one, so indeed a beginner's mistake from my side. @ Peter: Thank you very much for this! This might actually do the trick.
$endgroup$
– Phil
Apr 7 at 1:35
$begingroup$
@ LutzL: I have to apologize for the crosspost - I wasn't sure where to post this problem and since it is a computational as well as a numerical issue, I thought it might be appropriate for both sections. I should have chosen one, so indeed a beginner's mistake from my side. @ Peter: Thank you very much for this! This might actually do the trick.
$endgroup$
– Phil
Apr 7 at 1:35
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
$$binomnk=fracn!(n-k)! , k!=fracGamma(n+1)Gamma(n-k+1),Gamma(k+1)$$
$$log (binomnk)=log(Gamma(n+1))-log(Gamma(n-k+1))-log(Gamma(k+1))$$
Now, have a look here.
answered Apr 7 at 6:42
Claude LeiboviciClaude Leibovici
125k1158135
$endgroup$
$begingroup$
Thank you very much! I wasn't aware that the solution could be this simple. It works, is fast and accurate. Great!
$endgroup$
– Phil
Apr 8 at 0:21
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Phil is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3177403%2fefficient-and-accurate-approximatiion-of-logarithm-of-binomial-coefficients%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
$$binomnk=fracn!(n-k)! , k!=fracGamma(n+1)Gamma(n-k+1),Gamma(k+1)$$
$$log (binomnk)=log(Gamma(n+1))-log(Gamma(n-k+1))-log(Gamma(k+1))$$
Now, have a look here.
answered Apr 7 at 6:42
Claude LeiboviciClaude Leibovici
125k1158135
$endgroup$
$begingroup$
Thank you very much! I wasn't aware that the solution could be this simple. It works, is fast and accurate. Great!
$endgroup$
– Phil
Apr 8 at 0:21
add a comment |
$begingroup$
$$binomnk=fracn!(n-k)! , k!=fracGamma(n+1)Gamma(n-k+1),Gamma(k+1)$$
$$log (binomnk)=log(Gamma(n+1))-log(Gamma(n-k+1))-log(Gamma(k+1))$$
Now, have a look here.
answered Apr 7 at 6:42
Claude LeiboviciClaude Leibovici
125k1158135
$endgroup$
$begingroup$
Thank you very much! I wasn't aware that the solution could be this simple. It works, is fast and accurate. Great!
$endgroup$
– Phil
Apr 8 at 0:21
add a comment |
$begingroup$
$$binomnk=fracn!(n-k)! , k!=fracGamma(n+1)Gamma(n-k+1),Gamma(k+1)$$
$$log (binomnk)=log(Gamma(n+1))-log(Gamma(n-k+1))-log(Gamma(k+1))$$
Now, have a look here.
answered Apr 7 at 6:42
Claude LeiboviciClaude Leibovici
125k1158135
$endgroup$
$$binomnk=fracn!(n-k)! , k!=fracGamma(n+1)Gamma(n-k+1),Gamma(k+1)$$
$$log (binomnk)=log(Gamma(n+1))-log(Gamma(n-k+1))-log(Gamma(k+1))$$
Now, have a look here.
answered Apr 7 at 6:42
Claude LeiboviciClaude Leibovici
125k1158135
answered Apr 7 at 6:42
Claude LeiboviciClaude Leibovici
125k1158135
answered Apr 7 at 6:42
Claude LeiboviciClaude Leibovici
125k1158135
answered Apr 7 at 6:42
Claude LeiboviciClaude Leibovici
125k1158135
125k1158135
$begingroup$
Thank you very much! I wasn't aware that the solution could be this simple. It works, is fast and accurate. Great!
$endgroup$
– Phil
Apr 8 at 0:21
add a comment |
$begingroup$
Thank you very much! I wasn't aware that the solution could be this simple. It works, is fast and accurate. Great!
$endgroup$
– Phil
Apr 8 at 0:21
$begingroup$
Thank you very much! I wasn't aware that the solution could be this simple. It works, is fast and accurate. Great!
$endgroup$
– Phil
Apr 8 at 0:21
$begingroup$
Thank you very much! I wasn't aware that the solution could be this simple. It works, is fast and accurate. Great!
$endgroup$
– Phil
Apr 8 at 0:21
add a comment |
Phil is a new contributor. Be nice, and check out our Code of Conduct.
Phil is a new contributor. Be nice, and check out our Code of Conduct.
Phil is a new contributor. Be nice, and check out our Code of Conduct.
Phil is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3177403%2fefficient-and-accurate-approximatiion-of-logarithm-of-binomial-coefficients%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
Show a concrete example where the approximation is poor. If $ n $ , $ k $ and $ n-k $ are all large, the approximation should be good. Additionally, where is $ k $ in the approximation ?
$endgroup$
– Peter
Apr 6 at 20:25
$begingroup$
In PARI/GP, you can use the lngamma-command for very accurate logarithms of huge binomial coefficients.
$endgroup$
– Peter
Apr 6 at 20:27
1
$begingroup$
Crosspost from stackoverflow.com/questions/55552775/…, there also with the specification that $nsim 10^7$.
$endgroup$
– LutzL
Apr 6 at 20:33
$begingroup$
@ LutzL: I have to apologize for the crosspost - I wasn't sure where to post this problem and since it is a computational as well as a numerical issue, I thought it might be appropriate for both sections. I should have chosen one, so indeed a beginner's mistake from my side. @ Peter: Thank you very much for this! This might actually do the trick.
$endgroup$
– Phil
Apr 7 at 1:35