math.lua

View source code here on GitHub!

factorial(n)
Returns:

The factorial of n

Return type:

number

n_choose_r(n, r)
Returns:

The number of ways to choose r elements from a sample of size n

Return type:

number

 1local function factorial(n)
 2    local answer = 1
 3
 4    for i = 2,n do
 5        answer = answer * i
 6    end
 7
 8    return answer
 9end
10
11local function factor_gen(n, r)
12    local factors = {}
13
14    -- collect factors of final number
15    for i = 2,n do
16        factors[i] = 1
17    end
18
19    -- negative factor values indicate need to divide
20    for i = 2,r do
21        factors[i] = factors[i] - 1
22    end
23    for i = 2,(n - r) do
24        factors[i] = factors[i] - 1
25    end
26
27    -- this loop reduces to prime factors only
28    for i = n,2,-1 do
29        for j = 2,(i - 1) do
30            if i % j == 0 then
31                factors[j] = factors[j] + factors[i]
32                factors[i / j] = factors[i / j] + factors[i]
33                factors[i] = 0
34                break
35            end
36        end
37    end
38
39    return factors
40end
41
42local function n_choose_r(n, r)
43    if n < 20 then -- fast path if number is small
44        return factorial(n) / factorial(r) / factorial(n - r)
45    end
46
47    -- slow path for big numbers// slow path for larger numbers
48    local factors = factor_gen(n, r)
49    local answer
50    local tmp
51    local i = 2
52    local j = 2
53    answer = 1;
54    while i <= n do
55        while factors[i] > 0 do
56            tmp = answer
57            answer = answer * i
58            while answer < tmp and j <= n do
59                while factors[j] < 0 do
60                    tmp = math.floor(tmp / j)
61                    factors[j] = factors[j] + 1
62                end
63                j = j + 1;
64                answer = tmp * i
65            end
66
67            if answer < tmp then
68                return nil, "math error: overflow"
69            end
70            factors[i] = factors[i] - 1
71        end
72        i = i + 1
73    end
74
75    while j <= n do
76        while factors[j] < 0 do
77            answer = answer / j
78            factors[j] = factors[j] + 1
79        end
80        j = j + 1
81    end
82
83    return answer
84end
85
86return {
87    factorial = factorial,
88    n_choose_r = n_choose_r,
89}