//  ============================================================
//
//  binomial.h
//
//  Copyright 2002, Dennis Meilicke and Rene Peralta
//
//  ============================================================
//
//  Description:
//
//  NTTL Implementation of:
//      Binomial
//
//  ============================================================
#ifndef __nttl_binomial__
#define __nttl_binomial__


#include <nttl/factorial.h>

template< class T >
void Binomial( T *Value, size_t n, size_t k ) 
//  ============================================================
//
//  Description
//
//  Compute 'n choose k' (the binomial coeeficient).
//
//  ============================================================
//
//  Algorithm
//
//  The algorithm is based on the formula:
//
//			Binomial( n, k ) = n! / ( k! (n-k)! )
//
//	We determine whether 'k' or 'n - k' is larger, and use the 
//  larger value to cancel the numerator.  This should lead to a
//  minimum number of multiplications.
//
//  ============================================================
//
//  Notes:
//
//  Since this function uses Product( ) and Factorial( )
//  functions, the range of 'n' and 'k' are effectively limited 
//  by those functions.
//
//  It should be possible to come up with an algorithm that 
//  "matches" numbers in the numerator with numbers in the 
//  denominator, cancelling as you go.  This would greatly 
//  increase the range of this function.  Could this make use of 
//  gcd()'s, and parital products? 
//
//  Time for a literature search..
//  
//  ============================================================
{
    size_t x;
    T Numerator, Denominator, Remainder;

    x = n - k;

    if( x < k )
    {
        Product( Numerator, k + 1, n );
        Factorial( Denominator, x );
    }
    else
    {
	    Product( Numerator, x + 1, n );
        Factorial( Denominator, k );
    }

    *Value = Numerator / Denominator;
}


#endif