time-to-botec

Benchmark sampling in different programming languages
Log | Files | Refs | README

binomcoef.js (2460B)

      1 /**
      2 * @license Apache-2.0
      3 *
      4 * Copyright (c) 2018 The Stdlib Authors.
      5 *
      6 * Licensed under the Apache License, Version 2.0 (the "License");
      7 * you may not use this file except in compliance with the License.
      8 * You may obtain a copy of the License at
      9 *
     10 *    http://www.apache.org/licenses/LICENSE-2.0
     11 *
     12 * Unless required by applicable law or agreed to in writing, software
     13 * distributed under the License is distributed on an "AS IS" BASIS,
     14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     15 * See the License for the specific language governing permissions and
     16 * limitations under the License.
     17 */
     18 
     19 'use strict';
     20 
     21 // MODULES //
     22 
     23 var isInteger = require( './../../../../base/assert/is-integer' );
     24 var isnan = require( './../../../../base/assert/is-nan' );
     25 var isOdd = require( './../../../../base/assert/is-odd' );
     26 var round = require( './../../../../base/special/round' );
     27 
     28 
     29 // MAIN //
     30 
     31 /**
     32 * Computes the binomial coefficient of two integers.
     33 *
     34 * ## Method
     35 *
     36 * -   Instead of evaluating the factorial form, which is inefficient and prone to overflow for large inputs arguments, this module computes the following multiplicative representation of the binomial coefficient for integer arguments
     37 *
     38 *     ```tex
     39 *     \binom nk = \prod_{i=1}^k \frac{n+1-i}{i}
     40 *     ```
     41 *
     42 * @param {integer} n - input value
     43 * @param {integer} k - second input value
     44 * @returns {integer} function value
     45 *
     46 * @example
     47 * var v = binomcoef( 8, 2 );
     48 * // returns 28
     49 *
     50 * @example
     51 * var v = binomcoef( 0, 0 );
     52 * // returns 1
     53 *
     54 * @example
     55 * var v = binomcoef( -4, 2 );
     56 * // returns 10
     57 *
     58 * @example
     59 * var v = binomcoef( NaN, 3 );
     60 * // returns NaN
     61 *
     62 * @example
     63 * var v = binomcoef( 5, NaN );
     64 * // returns NaN
     65 *
     66 * @example
     67 * var v = binomcoef( NaN, NaN );
     68 * // returns NaN
     69 */
     70 function binomcoef( n, k ) {
     71 	var res;
     72 	var j;
     73 	if ( isnan( n ) || isnan( k ) ) {
     74 		return NaN;
     75 	}
     76 	if ( !isInteger( n ) || !isInteger( k ) ) {
     77 		return NaN;
     78 	}
     79 	if ( k < 0 ) {
     80 		return 0;
     81 	}
     82 	if ( n < 0 ) {
     83 		res = binomcoef( -n + k - 1, k );
     84 		if ( isOdd( k ) ) {
     85 			res = -res;
     86 		}
     87 		return res;
     88 	}
     89 	if ( k > n ) {
     90 		return 0;
     91 	}
     92 	if ( k === 0 || k === n ) {
     93 		return 1;
     94 	}
     95 	if ( k === 1 || k === n - 1 ) {
     96 		return n;
     97 	}
     98 	if ( n - k < k ) {
     99 		k = n - k;
    100 	}
    101 	// Use recursive definition...
    102 	res = n;
    103 	for ( j = 2; j <= k; j++ ) {
    104 		res *= ( n - j + 1 ) / j;
    105 	}
    106 	// Correct for rounding errors...
    107 	return ( isInteger( res ) ) ? res : round( res );
    108 }
    109 
    110 
    111 // EXPORTS //
    112 
    113 module.exports = binomcoef;