/****************************************************************/
/*  Jeff Balsley                                                */
/*  gcc -lm choose.c -o choose                                  */
/*                                                              */
/****************************************************************/

#include <stdio.h>
#include <math.h>

double choose (double n, double k);
double fac(double x);

int main(void)
{
    double n, k;

    printf("This program will calculate n choose k\n");
    printf("Enter n >");
    scanf("%lf", &n);
    printf("Enter k >");
    scanf("%lf", &k);

    printf("n choose k is %f\n", choose(n,k));

    return(0);
}

double choose(double n, double k)
{
    int i;
    double product = 1;

    /* check a few things first */
    if (k > n ){
        return(0);
    }else if( k == n || k == 0 ){
        return(1.0);
    }

    if (k < n/2.0){
        for (i=n; i > (n-k); --i){
            product = product * i;
        }
        /*printf("1 product is %f\n", product);*/
        return( product/fac(k) );
    }
    if ( k >= n/2.0 ){
        for (i=n; i > k; --i){
            product = product * i;
        }
        /*printf("2 product is %f\n", product);*/
        return( product / fac( n-k ) );
    }
}

double fac(double x)
{
    int i;
    double product = 1;

    if (x > 1){
        for(i=x; i>1; --i){
            product = product * i;
        }
    }else if( x < 0){
        printf("Can't take factorial of a negative number!!\n");
        return(0);
    }

    return(product);
}