diff options
| -rw-r--r-- | ChangeLog | 11 | ||||
| -rw-r--r-- | arith.c | 37 | ||||
| -rw-r--r-- | arith.h | 2 | ||||
| -rw-r--r-- | eval.c | 2 | ||||
| -rw-r--r-- | txr.1 | 31 |
5 files changed, 83 insertions, 0 deletions
@@ -1,5 +1,16 @@ 2014-01-11 Kaz Kylheku <kaz@kylheku.com> + * arith.c (rising_product): New static function. + (n_choose_k, n_perm_k): New functions. + + * arith.h (n_choose_k, n_perm_k): Declared. + + * eval.c (eval_init): New functions interned. + + * txr.1: Documented. + +2014-01-11 Kaz Kylheku <kaz@kylheku.com> + * arith.c (to_float): Print function name as ~a rather than ~s, so it doesn't have quotes around it. (cum_norm_dist): New function. @@ -1869,6 +1869,43 @@ val cum_norm_dist(val arg) } } +static val rising_product(val m, val n) +{ + val acc; + + if (lt(n, one)) + return one; + + if (ge(m, n)) + return one; + + if (lt(m, one)) + m = one; + + acc = m; + + m = plus(m, one); + + while (le(m, n)) { + acc = mul(acc, m); + m = plus(m, one); + } + + return acc; +} + +val n_choose_k(val n, val k) +{ + val top = rising_product(plus(minus(n, k), one), n); + val bottom = rising_product(one, k); + return trunc(top, bottom); +} + +val n_perm_k(val n, val k) +{ + return rising_product(plus(minus(n, k), one), n); +} + void arith_init(void) { mp_init(&NUM_MAX_MP); @@ -31,4 +31,6 @@ int highest_bit(int_ptr_t n); val normalize(val bignum); val in_int_ptr_range(val bignum); val cum_norm_dist(val x); +val n_choose_k(val n, val k); +val n_perm_k(val n, val k); void arith_init(void); @@ -2353,6 +2353,8 @@ void eval_init(void) reg_fun(intern(lit("exp"), user_package), func_n1(expo)); reg_fun(intern(lit("sqrt"), user_package), func_n1(sqroot)); reg_fun(intern(lit("cum-norm-dist"), user_package), func_n1(cum_norm_dist)); + reg_fun(intern(lit("n-choose-k"), user_package), func_n2(n_choose_k)); + reg_fun(intern(lit("n-perm-k"), user_package), func_n2(n_perm_k)); reg_fun(intern(lit("fixnump"), user_package), func_n1(fixnump)); reg_fun(intern(lit("bignump"), user_package), func_n1(bignump)); reg_fun(intern(lit("floatp"), user_package), func_n1(floatp)); @@ -8996,6 +8996,37 @@ The cum-norm-dist function calculates an approximation to the cumulative normal distribution function: the integral, of the normal distribution function, from negative infinity to the <argument>. +.SS Functions n-choose-k and n-perm-k + +.TP +Syntax: + + (n-choose-k <n> <k>) + (n-perm-k <n> <k>) + +.TP +Description: + +The n-choose-k function computes the binomial coefficient nCk which +expresses the number of combinations of <k> items that can be chosen from +a set of <n>, where combinations are subsets. + +The n-choose-k function computes nPk: the number of permutations of size <k> +that can be drawn from a set of <n>, where permutations are sequences, +whose order is significant. + +The calculations only make sense when <n> and <k> are nonnegative integers, and +<k> does not exceed <n>. The behavior is not specified if these conditions +are not met. + +.TP +Description: + +The cum-norm-dist function calculates an approximation to the cumulative normal +distribution function: the integral, of the normal distribution function, from +negative infinity to the <argument>. + + .SS Functions fixnump, bignump, integerp, floatp, numberp .TP |