# Factorial optimization

**URL:** <https://discuss.python.org/t/factorial-optimization/57707>\
**Category:** Python Help\
**Tags:** help\
**Created:** [July 9, 2024, 7:27am UTC](https://discuss.python.org/t/factorial-optimization/57707 "2024-07-09T07:27:59Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![Ivanchik](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/ivanchik/32/20320_2.png) [@Ivanchik](https://discuss.python.org/u/Ivanchik)\
**Post date:** [July 9, 2024, 7:27am UTC](https://discuss.python.org/t/factorial-optimization/57707/1 "2024-07-09T07:27:59Z")

</div>

I have a function that takes two numbers (the first is greater than the second) and returns the result of dividing their factorials.

```python
import math
def factorial_division(n, d):
    return math.factorial(n) / math.factorial(d)

```

However, with large quantities, it works for a very long time because of `math.factorial(n)`.  
Is there a way to optimize this?

---

<div class="post-metadata">

**Author:** ![blhsing](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/blhsing/32/25812_2.png) [@blhsing](https://discuss.python.org/u/blhsing)\
**Post date:** [July 9, 2024, 8:34am UTC](https://discuss.python.org/t/factorial-optimization/57707/2 "2024-07-09T08:34:41Z")

</div>

The factors of the smaller factorial in the denominator cancel out those in the larger factorial in the numerator, so you only need to calculate the product of the remaining factors in the numerator.

> **[Dividing Factorials](https://www.chilimath.com/lessons/intermediate-algebra/dividing-factorials/)**
>
> Learn the tips and tricks behind factorial division. Expand numerators and denominators, cancel out common factors and simplify in no time!

---

<div class="post-metadata">

**Author:** ![Ivanchik](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/ivanchik/32/20320_2.png) [@Ivanchik](https://discuss.python.org/u/Ivanchik)\
**Post date:** [July 9, 2024, 8:58am UTC](https://discuss.python.org/t/factorial-optimization/57707/3 "2024-07-09T08:58:50Z")

</div>

@blhsing I followed your advice and created the following function:

```python
def factorial_division(n, d):
    ans = 1
    ln = []
    ld = []
    for i in range(n): # list of n multipliers
        ln.append(n - i)
    for i in range(d): # list of d multipliers
        ld.append(d - i)
    for i in ld: # removing the same elements
        ln.remove(i)
    for i in ln: # and multiply
        ans *= i
    return ans

```

But it’s still **slow**.  
How can I do it **faster**?

---

<div class="post-metadata">

**Author:** ![petercordia](https://avatars.discourse-cdn.com/v4/letter/p/bb73d2/32.png) [@petercordia](https://discuss.python.org/u/petercordia)\
**Post date:** [July 9, 2024, 9:09am UTC](https://discuss.python.org/t/factorial-optimization/57707/4 "2024-07-09T09:09:19Z")

</div>

```python
import numpy as np
def f(x,y):
    return np.prod(np.arange(y+1,x+1))

```

---

<div class="post-metadata">

**Author:** ![Ivanchik](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/ivanchik/32/20320_2.png) [@Ivanchik](https://discuss.python.org/u/Ivanchik)\
**Post date:** [July 9, 2024, 9:14am UTC](https://discuss.python.org/t/factorial-optimization/57707/5 "2024-07-09T09:14:55Z")

</div>

@petercordia Briefly, but:

```python
import numpy as np
def f(x,y):
    return np.prod(np.arange(y+1,x+1))
print(f(500, 30))

```

print `0`.

---

<div class="post-metadata">

**Author:** ![petercordia](https://avatars.discourse-cdn.com/v4/letter/p/bb73d2/32.png) [@petercordia](https://discuss.python.org/u/petercordia)\
**Post date:** [July 9, 2024, 9:21am UTC](https://discuss.python.org/t/factorial-optimization/57707/6 "2024-07-09T09:21:13Z")

</div>

Fair.

```python
import numpy as np
def f(x,y):
    return np.prod(np.arange(y+1,x+1, dtype=np.float64))

```

is slightly better. Can also be written as

```python
import numpy as np
def f(x,y):
    return np.arange(y+1,x+1).prod(dtype=np.float64)

```

---

<div class="post-metadata">

**Author:** ![Rosuav](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/rosuav/32/3429_2.png) [@Rosuav](https://discuss.python.org/u/Rosuav)\
**Post date:** [July 9, 2024, 9:42am UTC](https://discuss.python.org/t/factorial-optimization/57707/7 "2024-07-09T09:42:45Z")

</div>

> [@Ivanchik](#):
>
> But it’s still **slow**.  
> How can I do it **faster**?

There is a very important _pattern_ in factorials. It isn’t a coincidence that there are a lot of the same elements.

---

<div class="post-metadata">

**Author:** ![defjaf](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/defjaf/32/12838_2.png) [@defjaf](https://discuss.python.org/u/defjaf)\
**Post date:** [July 9, 2024, 10:20am UTC](https://discuss.python.org/t/factorial-optimization/57707/8 "2024-07-09T10:20:40Z")

</div>

A lot depends on the size of the arguments to your function, and the accuracy you require. If they are large, and far apart, and you only need moderate accuracy, you can use [Stirling’s Approximation](https://en.wikipedia.org/wiki/Stirling's_approximation). Alternately, you can just use the [Gamma function](https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.gamma.html) which is trivially related to the factorial.

(And even if you are going to go the route of explicit multiplication, you should almost always calculate the _log-factorial_ by _adding_ up the _logarithm_ of the factors, rather than _multiplying_ the factors themselves. Similarly, it is often a good idea to use the [log-gamma function](https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.gammaln.html).)

---

<div class="post-metadata">

**Author:** ![Stefan2](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/stefan2/32/18492_2.png) [@Stefan2](https://discuss.python.org/u/Stefan2)\
**Post date:** [July 9, 2024, 11:35am UTC](https://discuss.python.org/t/factorial-optimization/57707/9 "2024-07-09T11:35:58Z")

</div>

You could try `math.perm`:

```python
def factorial_division(n, d):
    return float(math.perm(n, n-d))

```

---

<div class="post-metadata">

**Author:** ![Stefan2](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/stefan2/32/18492_2.png) [@Stefan2](https://discuss.python.org/u/Stefan2)\
**Post date:** [July 9, 2024, 11:38am UTC](https://discuss.python.org/t/factorial-optimization/57707/10 "2024-07-09T11:38:31Z")

</div>

How large are your actual n and d?

---

<div class="post-metadata">

**Author:** ![Ivanchik](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/ivanchik/32/20320_2.png) [@Ivanchik](https://discuss.python.org/u/Ivanchik)\
**Post date:** [July 9, 2024, 12:12pm UTC](https://discuss.python.org/t/factorial-optimization/57707/11 "2024-07-09T12:12:46Z")

</div>

Like `6.08606003260358e+100`

---

<div class="post-metadata">

**Author:** ![Stefan2](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/stefan2/32/18492_2.png) [@Stefan2](https://discuss.python.org/u/Stefan2)\
**Post date:** [July 9, 2024, 12:22pm UTC](https://discuss.python.org/t/factorial-optimization/57707/12 "2024-07-09T12:22:23Z")

</div>

Which one of the two is that, and what’s the other?

---

<div class="post-metadata">

**Author:** ![Ivanchik](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/ivanchik/32/20320_2.png) [@Ivanchik](https://discuss.python.org/u/Ivanchik)\
**Post date:** [July 9, 2024, 1:32pm UTC](https://discuss.python.org/t/factorial-optimization/57707/13 "2024-07-09T13:32:16Z")

</div>

For example `n = 2230505856425722403` and `d = 2230505856425722365`.

---

<div class="post-metadata">

**Author:** ![franklinvp](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/franklinvp/32/11142_2.png) [@franklinvp](https://discuss.python.org/u/franklinvp)\
**Post date:** [July 9, 2024, 1:39pm UTC](https://discuss.python.org/t/factorial-optimization/57707/14 "2024-07-09T13:39:55Z")

</div>

If you know that the distance between them is somewhat small, then you can just multiply the integers between them

```python
import math
math.prod(range(2230505856425722365 + 1, 2230505856425722403 + 1))

```

Did you want a `float` representative of the result, or an `int`?

In this case the `float` would be `float('inf')` while the `int` would be

```python
17351138597226293352630193935665609594693978581996498781843019433078963027860489317612178572279296282556948008308450983789210463173334229571315086962509040932155200507618870712043548430561950788261692250464289134388486635536666564908417332515148578295039482470616499986575509864916249532872327205353234164677571012766394131744290828469332114312611766044284905128640843598683647829878418330776003244032794141636915677820604912776872518559455231692123159366281106422219638122840647095448201676717904639972497190201538542268643416837206517701093840322733676316941180912257933682401688265844902076608703084793987212327675008079248381690481566503581722166765264410829545064918974514741683159040000000000

```

---

<div class="post-metadata">

**Author:** ![petercordia](https://avatars.discourse-cdn.com/v4/letter/p/bb73d2/32.png) [@petercordia](https://discuss.python.org/u/petercordia)\
**Post date:** [July 9, 2024, 1:51pm UTC](https://discuss.python.org/t/factorial-optimization/57707/15 "2024-07-09T13:51:58Z")

</div>

You should use int for convenience.

```python
prod = 1
for i in range(2230505856425722365+1, 2230505856425722403+1):
    prod*=i
prod

```

gives an exact answer instantly.

```python
prod = 1.0
for i in range(2230505856425722365+1, 2230505856425722403+1):
    prod*=i
prod

```

returns inf.

Because Python automatically creates ints consisting of many bytes there is no largest possible int. But floats can cap out.

Though for all practical purposes  
`2230505856425722403**38` should also be good enough.

---

<div class="post-metadata">

**Author:** ![Stefan2](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/stefan2/32/18492_2.png) [@Stefan2](https://discuss.python.org/u/Stefan2)\
**Post date:** [July 9, 2024, 2:19pm UTC](https://discuss.python.org/t/factorial-optimization/57707/16 "2024-07-09T14:19:55Z")

</div>

@franklinvp

```python
13.6 μs math.prod(range(d+1, n+1))
10.3 μs math.perm(n, n-d)
13.1 μs math.prod(range(d+1, n+1))
10.3 μs math.perm(n, n-d)
13.3 μs math.prod(range(d+1, n+1))
10.9 μs math.perm(n, n-d)

```

Benchmark script:

```python
from timeit import repeat

s = '''
import math
n = 2230505856425722403
d = 2230505856425722365
'''

es = [
    'math.prod(range(d+1, n+1))',
    'math.perm(n, n-d)',
]

for e in es * 3:
    t = min(repeat(e, s, number=1000)) / 1000
    print(round(t*1e6, 1), 'μs ', e)

```

[Attempt This Online!](https://ato.pxeger.com/run?1=bZA9TgMxEIVFOxJ3mM524oDXGy8RUk6CKBZ5NnHhH3m9BWehSQOn4AwcgNNgJ0GiYKrRe28-jd7bR3otxxhOp_elTJvd983tlKPH4jy5gs6nmAtmSjQWgBn3yBiDq-zHcoRQNa17ZZTZmWGrzYPWW9WD_UfvBwPtHqiRngDrsEa5SzlansdwIG7XncSw7oRg8m-CsuehOhvbjGeAKWYkdAErbYX94zlcKti7wC8vc5I415vFv1Ded0opIfAe23JOp-xC4TkuwfKy6miQ2AmJ7OtzRiaRxKWVazm_Jf0A)

---

<div class="post-metadata">

**Author:** ![kknechtel](https://avatars.discourse-cdn.com/v4/letter/k/e47c2d/32.png) [@kknechtel](https://discuss.python.org/u/kknechtel)\
**Post date:** [July 9, 2024, 3:07pm UTC](https://discuss.python.org/t/factorial-optimization/57707/17 "2024-07-09T15:07:44Z")

</div>

Just to give some background understanding:

The attempt here:

> [@Ivanchik](#):
>
> ```python
> def factorial_division(n, d):
> ans = 1
> ln = []
> ld = []
> for i in range(n): # list of n multipliers
> ln.append(n - i)
> for i in range(d): # list of d multipliers
> ld.append(d - i)
> for i in ld: # removing the same elements
> ln.remove(i)
> for i in ln: # and multiply
> ans *= i
> return ans
> 
> ```

is slow because it spends a lot of time making the lists and then searching them to remove the values. There’s no point to this, because we know ahead of time which values will cancel out: all the ones from `d` downward. (It’s even worse because `ln.remove` doesn’t know that the values are sorted, so it has to keep searching the entire list to find the `1`, `2` etc. which were put at the _end_ of the list by the previous `append` loops. It would have been faster to append the values in ascending order - but still a lot slower than needed, because when you remove the values from the start of the list, everything else has to shift down in memory.

Therefore, we should only consider the values greater than that, in the first place - by changing the bounds of the loop. But also, we don’t need to make a list of numbers to multiply. We can just multiply them, as we find them:

```python
def factorial_division(n, d):
    ans = 1
    for i in range(d+1, n+1):
        ans *= 1
    return ans

```

* * *

The `math` module provides a [faster implementation of factorial](https://stackoverflow.com/questions/9815252/) than naively multiplying all the numbers together.

The fact that it’s written in C doesn’t matter very much, because it still has to work through the Python data structures - and more importantly, the actual math is the bottleneck once the numbers get large. If you use a naive loop in Python, most of the time is spent in the C implementation of the multiplication operator. Instead, `math` speeds things up by factoring out powers of two, which produces some overlapping results, and reusing common work.

For a small example, suppose we compute 16!:

16 \* 15 \* 14 \* 13 \* 12 \* 11 \* 10 \* 9 \* 8 \* 7 \* 6 \* 5 \* 4 \* 3 \* 2 \* 1

First, factor out a power of two from each even number, and group the values where we did that:

= 8 \* 15 \* 7 \* 13 \* 6 \* 11 \* 5 \* 9 \* 4 \* 7 \* 3 \* 5 \* 2 \* 3 \* 1 \* 1 \* 28

= (15 \* 13 \* 11 \* 9 \* 7 \* 5 \* 3 \* 1) \* (8 \* 7 \* 6 \* 5 \* 4 \* 3 \* 2 \* 1) \* 28

Notice the second group is just 8!. So if we iterate this process, eventually we get:

= (15 \* 13 \* 11 \* 9 \* 7 \* 5 \* 3 \* 1) \* (7 \* 5 \* 3 \* 1) \* (3 \* 1) \* (1) \* 215

The (3 \* 1) result can be reused when computing (7 \* 5 \* 3 \* 1), which can be reused when computing (15 \* 13 \* 11 \* 9 \* 7 \* 5 \* 3 \* 1). And the factors of two can be multiplied all at once, by a simple bit-shift.

* * *

However, these kinds of optimizations don’t work so neatly for permutations and combinations. The products of all the odd numbers don’t telescope nearly so neatly when you don’t multiply all the way down to 1. And sometimes these kinds of optimizations are just low priority. Up through Python 3.10, `math.perm` [simply multiplied in a loop](https://github.com/python/cpython/blob/3.10/Modules/mathmodule.c#L3299), like the Python code I showed above.

Starting in 3.11, it… does much more complicated things. There’s a long thread on the issue tracker here, describing the changes:

> <https://github.com/python/cpython/issues/81476>
>
> BPO | \[37295\](https://bugs.python.org/issue37295)
> \--- | :---
> Nosy | @tim-one, @r…hettinger, @mdickinson, @serhiy-storchaka, @PedanticHacker, @mcognetta, @pochmann
> PRs | \<li\>python/cpython#29020\</li\>\<li\>python/cpython#29030\</li\>\<li\>python/cpython#29090\</li\>\<li\>python/cpython#30275\</li\>\<li\>python/cpython#30305\</li\>\<li\>python/cpython#30313\</li\>
> Files | \<li\>\[comb\_with\_primes.py\](https://bugs.python.org/file50439/comb\_with\_primes.py "Uploaded as text/plain at 2021-11-15.04:27:26 by @pochmann")\</li\>\<li\>\[comb\_with\_side\_limits.py\](https://bugs.python.org/file50526/comb\_with\_side\_limits.py "Uploaded as text/plain at 2021-12-29.18:41:09 by @rhettinger"): Compute limits for comb\_small\</li\>\<li\>\[timecomb.py\](https://bugs.python.org/file50530/timecomb.py "Uploaded as text/plain at 2021-12-30.19:38:10 by @mdickinson")\</li\>\<li\>\[driver.py\](https://bugs.python.org/file50531/driver.py "Uploaded as text/plain at 2021-12-30.19:38:24 by @mdickinson")\</li\>\<li\>\[comb\_pole.py\](https://bugs.python.org/file50557/comb\_pole.py "Uploaded as text/plain at 2022-01-12.05:03:37 by @rhettinger"): Experiment with precomputed diagonal -- runs on 3.8 or later\</li\>\<li\>\[comb\_pole2.py\](https://bugs.python.org/file50559/comb\_pole2.py "Uploaded as text/plain at 2022-01-13.03:43:19 by @rhettinger"): Precomputed k diagonal and handling for small k\</li\>
> 
> \<sup\>\*Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.\*\</sup\>
> 
> \<details\>\<summary\>Show more details\</summary\>\<p\>
> 
> GitHub fields:
> \`\`\`python
> assignee = None
> closed\_at = None
> created\_at = \<Date 2019-06-15.19:17:40.265\>
> labels = \['library', 'performance'\]
> title = 'Possible optimizations for math.comb()'
> updated\_at = \<Date 2022-01-23.22:42:15.922\>
> user = 'https://github.com/rhettinger'
> \`\`\`
> 
> bugs.python.org fields:
> \`\`\`python
> activity = \<Date 2022-01-23.22:42:15.922\>
> actor = 'tim.peters'
> assignee = 'none'
> closed = False
> closed\_date = None
> closer = None
> components = \['Library (Lib)'\]
> creation = \<Date 2019-06-15.19:17:40.265\>
> creator = 'rhettinger'
> dependencies = \[\]
> files = \['50439', '50526', '50530', '50531', '50557', '50559'\]
> hgrepos = \[\]
> issue\_num = 37295
> keywords = \['patch'\]
> message\_count = 73.0
> messages = \['345711', '345731', '345761', '345784', '345876', '345952', '345956', '404184', '404208', '404429', '404472', '406300', '406337', '406338', '406341', '407736', '408867', '408952', '408954', '408962', '408970', '408984', '408989', '408994', '409000', '409001', '409002', '409010', '409024', '409028', '409062', '409095', '409110', '409116', '409154', '409254', '409268', '409269', '409270', '409274', '409277', '409298', '409315', '409317', '409320', '409321', '409331', '409346', '409360', '409373', '409376', '409377', '409382', '409383', '409393', '409417', '409432', '410145', '410339', '410347', '410382', '410383', '410387', '410420', '410448', '410460', '410543', '410587', '410925', '410931', '411343', '411427', '411430'\]
> nosy\_count = 7.0
> nosy\_names = \['tim.peters', 'rhettinger', 'mark.dickinson', 'serhiy.storchaka', 'PedanticHacker', 'mcognetta', 'Stefan Pochmann'\]
> pr\_nums = \['29020', '29030', '29090', '30275', '30305', '30313'\]
> priority = 'normal'
> resolution = None
> stage = 'patch review'
> status = 'open'
> superseder = None
> type = 'performance'
> url = 'https://bugs.python.org/issue37295'
> versions = \[\]
> \`\`\`
> 
> \</p\>\</details\>

It’s written about `math.comb` (i.e, combinations rather than permutations), but many of the optimizations are shared. Some of them even apply to `math.factorial`, because there’s now a precomputed table of small odd-factorial results.

I tried the benchmarks mentioned in the OP there (on slightly slower hardware 🙂 ). From 3.8 to 3.12, the “just calculate factorials and divide” approach (for 100000 choose 50000) already takes about 30% less time than before, which is impressive. The implementation used by `math.comb` is now faster than the naive factorial division approach, instead of being slower. Overall it’s now more than ten times as fast for these values (and it’s an algorithmic improvement, so it only gets better for larger inputs). And up to the factorial of (on 64-bit builds) 20 is a table lookup now. (This doesn’t improve things very much for those inputs, because when things are this fast, the time is dominated by sanity checks and working through the C-Python API. But I assume it matters a lot for the algorithm internally.)

---

<div class="post-metadata">

**Author:** ![Stefan2](https://sea2.discourse-cdn.com/flex002/user_avatar/discuss.python.org/stefan2/32/18492_2.png) [@Stefan2](https://discuss.python.org/u/Stefan2)\
**Post date:** [July 9, 2024, 3:14pm UTC](https://discuss.python.org/t/factorial-optimization/57707/18 "2024-07-09T15:14:56Z")

</div>

> [@kknechtel](#):
>
> it has to keep searching the entire list to find the `1`, `2` etc.

Not really, as _both_ lists are descending. So it finds not 1,2,etc but d,d-1,etc. And with their example where d is close to n, those are almost at the start.

---

<div class="post-metadata">

**Author:** ![kknechtel](https://avatars.discourse-cdn.com/v4/letter/k/e47c2d/32.png) [@kknechtel](https://discuss.python.org/u/kknechtel)\
**Post date:** [July 9, 2024, 3:17pm UTC](https://discuss.python.org/t/factorial-optimization/57707/19 "2024-07-09T15:17:17Z")

</div>

True, I didn’t _quite_ think that through 🙂
