0
Answered

nchoosek, binomial coefficient

dattorro 4 years ago updated by Pavel Holoborodko 2 weeks ago 7

How do we increase dynamic range of Matlab's binomial coefficient function nchoosek()?

It will not accept multiprecision mp() input.

Answer

Answer
Answered

Jon, I have just released new version of toolbox - 5.3.6.15927.

It doesn't use the MATLAB's implementation of nchoosek anymore.

Instead it is now implemented directly in toolbox core.

 

>> nchoosek(mp(76), mp(32))
ans = 
    2695592391875730827550

Please update your environment.

Under review

Toolbox doesn't include this function at the moment. Now I am considering to add it.

How do you use it? Just to compute binomial coefficient or to generate all combinations?

There is a quick way to make the built-in 'nchoosek()' work with toolbox. Create flintmax.m file in [toolbox_folder]\@char directory with following content:

function r = flintmax( classname )

if strcmpi('mp',classname)
r = 2^ceil(mp.Digits() * mp('log2(10)'));
else
r = builtin('flintmax',classname);
end
end

Restart MATLAB and test 'nchoosek()', e.g.:

>> mp.Digits(100);
>> x = nchoosek(mp(1000),50)

x = 

9460461017585217574825413104128279942327590136138287606176460370151247948488653144064
Answered

We have just updated toolbox distribution/installer with the 'flintmax.m' already included.

Please download and use the latest toolbox version.

Pavel, on your webpage

https://www.advanpix.com/documentation/version-history/

there is reference to Matlab's nchoosek().

I posted matlab code for linking to its complete (negative argument) binomial coefficient definition here:

https://www.convexoptimization.com/wikimization/index.php/Binomial_coefficient

Here is LaTeX output:

 

mp.Digits(1034); nchoosek(mp('76'), mp('32'))

Warning: Result may not be exact. 

Coefficient has a maximum relative error of 7.9936e-15, corresponding to absolute error 21547503.
> In nchoosek (line 121)

      ans = 2 695 592 391 875 732 963 328  % incorrect

Correct answer is: 2 695 592 391 875 730 827 550

I have just checked the source code of the nchoosek in the newest versions of MATLAB.
MathWorks changed it to do all the computations in double. Here is some code from the function: 

% Do the computation in doubles.  
nd = full(double(n)); 
kd = full(double(k));           

I am not sure, but the code might start work fine after replacing all the "double" to "mp".

Looks like MW has no plans to support OOP/custom classes properly at all.


Meanwhile I will try to implement the function in toolbox's core.

Answer
Answered

Jon, I have just released new version of toolbox - 5.3.6.15927.

It doesn't use the MATLAB's implementation of nchoosek anymore.

Instead it is now implemented directly in toolbox core.

 

>> nchoosek(mp(76), mp(32))
ans = 
    2695592391875730827550

Please update your environment.