choose.m

compute number of ways of choosing m objects from n distinct objects

Description

choose(n,m) computes the number of ways of choosing m objects from n distinct objects. The simplest definition of choose(n,m) is n! / (m! * (n-m)!), but the following algorithm is somewhat less susceptible to overflow, and is faster than Matlab's builtin nchoosek function.

• MATLAB release: MATLAB 7.7 (R2008b)

[Darren Rowland]

This is a poor submission to the FEX. It provides nothing that nchoosek does not, and computes the result in a way which is more susceptible to roundoff error. The input checks are inadequate and no warnings are given for large output values. Here is the file contents

function k= choose(n, m)
%
% choose(n,m) is the number of ways of choosing m objects from n
% distinct objects.

% Check input arguments:

if (nargin ~= 2)
   error('choose requires 2 arguments.');
end

if (m < 0 | m > n)
   error('m (second argument) must be between 0 and n, inclusive.');
end

% The simplest definition of choose(n,m) is n! / (m! * (n-m)!), but the
% following algorithm is somewhat less susceptible to overflow.

if (m >= n-m)
   k= prod(m+1:n) / prod(2:n-m);

else
   k= prod(n-m+1:n) / prod(2:m);
end

[John D'Errico]

Why submit functions that do the same thing that existing utilities in MATLB do better?

nchoosek does the same computation, but does it better, since nchoosek offers more functionality, and already exists in every copy of matlab for as far back as I can recall.

This has little in the way of error checking. No H1 line.

Admittedly, if you are trying to compute large binomial coefficients, you will be far better off using a variety of other tools. But this one fails when it needs not do so.

>> nchoosek(1000,800)
Warning: Result may not be exact. Coefficient is greater than 1.000000e+15
 and is only accurate to 15 digits.
> In nchoosek at 66
ans =
     6.61715556065931e+215

>> choose(1000,800)
ans =
   NaN

[Phillip M. Feldman]

Darren and John-

Most of what I do with Matlab is simulation. From the standpoint of a simulationist, nchoosek is probably more suitable in the development/debugging stage of a simulation, but once the development and debugging has been done, one wants the code to run as fast as possible. Below are the results of a simple timing comparison of nchoosek and choose:

>> mytime(0); for i=1:1e6; nchoosek(52,13); end; mytime;
19-May-2009 10:45:26 Timer initialized.
19-May-2009 10:46:01 Last step took 35.56 sec.; total elapsed= 35.56 sec.

>> mytime(0); for i=1:1e6; choose(52,13); end; mytime;
19-May-2009 10:46:11 Timer initialized.
19-May-2009 10:46:20 Last step took 8.70 sec.; total elapsed= 8.70 sec.

Note that my function runs over four times as fast as Matlab's builtin function. For the user who invokes nchoosek small numbers of times from the command line, the difference in speed is unimportant. But, when nchoosek or choose is being called millions or tens of milions of times from within a program, the difference becomes important. Please let me know if further explanation is required.

[Jos (10584)]

If it is all about speed, remove the error checks! For larger numbers the following formula is more appropriate:
exp(gammaln(N+1) - gammaln(K+1) - gammaln(N-K+1)) ;

[David Holdaway]

I would also suggest the following improvement to stop overflow..

k= prod(m+1:n) / prod(2:n-m)
---->
k = prod((m+1:n) ./ (1:n-m))

There is no reason to evaluate the products and then compare that's just likely to cause inf/inf type errors.