math.rs

View source code here on GitHub!

Includes

pub fn math::factorial<I>(n: u8) -> I where I: NumAssign + From<u8>

Returns the factorial of a given number. Note that it only accepts a u8 because any number that requires a larger type is guaranteed to overflow.

pub fn n_choose_r<I>(n: usize, r: usize) -> I where I: Copy + From<u8> + From<u64> + NumAssign + PartialOrd

Returns the number of ways to choose r items from a set of n.

  1use std::cmp::PartialOrd;
  2use std::fmt::Debug;
  3use std::mem::size_of;
  4
  5use num_traits::NumAssign;
  6use num_traits::one;
  7use num_traits::CheckedMul;
  8
  9const MAX_FACTORIAL: [u8; 16] = [
 10    5, // u8
 11    8, // u16
 12    10, 12, // u32
 13    14, 16, 18, 20, // u64
 14    22, 24, 25, 27, 29, 30, 32, 34 // u128
 15];
 16
 17pub fn factorial<I>(n: u8) -> I
 18where I: NumAssign + From<u8>
 19{
 20    let mut answer: I = one();
 21    for i in 2..=n {
 22        answer *= i.into();
 23    }
 24    return answer
 25}
 26
 27pub fn n_choose_r<I>(n: usize, r: usize) -> I
 28where I: Copy + From<u8> + From<u64> + NumAssign + PartialOrd + CheckedMul + Debug
 29{
 30    if n < r {
 31        panic!("Out of function's bounds");
 32    }
 33    if n < MAX_FACTORIAL[size_of::<I>() - 1] as usize {
 34        return factorial::<I>(n as u8) / factorial::<I>(r as u8) / factorial::<I>((n - r) as u8);
 35    }
 36    // slow path for larger numbers
 37    let mut answer: I = one();
 38    let mut factors: Vec<i8> = vec![1; n + 1];
 39    factors[0] = 0;
 40    factors[1] = 0;
 41    // negative factor values indicate need to divide
 42    for i in 2..=r {
 43        factors[i] -= 1;
 44    }
 45    for i in 2..=(n - r) {
 46        factors[i] -= 1;
 47    }
 48    // this loop reduces to prime factors only
 49    for i in (1..n).rev() {
 50        for j in 2..i {
 51            if i % j == 0 {
 52                factors[j] += factors[i];
 53                factors[i / j] += factors[i];
 54                factors[i] = 0;
 55                break;
 56            }
 57        }
 58    }
 59    let mut i: usize = 2;
 60    let mut j: usize = 2;
 61    while i <= n {
 62        while factors[i] > 0 {
 63            let mut result = answer.checked_mul(&(i as u64).into());
 64            while result.is_none() && j <= n {
 65                while factors[j] < 0 {
 66                    answer /= (j as u64).into();
 67                    factors[j] += 1;
 68                }
 69                j += 1;
 70                result = answer.checked_mul(&(i as u64).into());
 71            }
 72            factors[i] -= 1;
 73            answer = result.unwrap_or_else(|| panic!("nCr overflow: {:?} * {}", answer, i));
 74        }
 75        i += 1;
 76    }
 77    while j <= n {
 78        while factors[j] < 0 {
 79            answer /= (j as u64).into();
 80            factors[j] += 1;
 81        }
 82        j += 1;
 83    }
 84    return answer;
 85}
 86
 87pub fn triangle<I>(n: I) -> I where I: NumAssign + Copy {
 88    let two = one::<I>() + one();
 89    return n * (n + one()) / two;
 90}
 91
 92pub fn pentagonal<I>(n: I) -> I where I: NumAssign + Copy {
 93    let two = one::<I>() + one();
 94    let three = two + one();
 95    return n * (three * n - one()) / two;
 96}
 97
 98pub fn hexagonal<I>(n: I) -> I where I: NumAssign + Copy {
 99    let two = one::<I>() + one();
100    return n * (two * n - one());
101}