# How is factorial(BigInt) so fast?

**URL:** <https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166>\
**Category:** Performance\
**Created:** [November 5, 2018, 2:08pm UTC](https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166 "2018-11-05T14:08:39Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![frank](https://avatars.discourse-cdn.com/v4/letter/f/3d9bf3/32.png) [@frank](https://discourse.julialang.org/u/frank)\
**Post date:** [November 5, 2018, 2:08pm UTC](https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166/1 "2018-11-05T14:08:39Z")

</div>

As an experiment, I copy/pasted Julia’s [factorial() function](https://github.com/JuliaLang/julia/blob/0d713926f85dfa3e4e0962215b909b8e47e94f48/base/intfuncs.jl#L784-L810) and renamed it. But when I use it to evaluate a bigint, it is way slower than Julia’s factorial(BigInt). If the base function uses the same code, then why is the base function faster and is there a way I can achieve those speeds?

I’m guessing Julia’s either uses a dictionary lookup or somehow avoids most of the performance loss of bigints. The latter would be a useful trick to know.

I understand that creating a bigint longer than 9 digits is about 10x slower than creating a smaller bigint, and that another slowdown happens at 20 digits. Therefore, hypothetically if you evaluate BigInt(15)! manually, it’s faster to do

`BigInt(15*14*13*12*11) * BigInt(10*9*8*7*6*5*4*3*2)`

than it is to do

```julia
BigInt(15*14*13*12*11*10*9*8*7*6) * BigInt(5*4*3*2)

```

because (15 P 5) and 10! are both under 10 digits whereas (15 P 10) is not.

In fact, I know of no faster way to manually evaluate BigInt(15)! than to split it into two BigInts where each is smaller than 1 billion. It’s faster than BigInt(15_14_…\*2), or BigInt(15)_BigInt(14)_…\*BigInt(2), or any conceivable possibility.

However, even that is twice as slow as factorial(BigInt(15)) according to @btime. Julia has a trick up its sleeve and I want to know about it 🙂

Thanks

---

<div class="post-metadata">

**Author:** ![sdanisch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sdanisch/32/1406_2.png) [@sdanisch](https://discourse.julialang.org/u/sdanisch)\
**Post date:** [November 5, 2018, 2:21pm UTC](https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166/2 "2018-11-05T14:21:25Z")

</div>

You copied the wrong function

```nohighlight
julia> @which factorial(BigInt(1))
factorial(x::BigInt) in Base.GMP at gmp.jl:564

julia> @which factorial(1)
factorial(n::Union{Int64, UInt64}) in Base at combinatorics.jl:27

```

The correct one seems to be implemented by GMP.  
You might also have luck with adapting the factorial code to be in-place (BigInts are mutable I think).

---

<div class="post-metadata">

**Author:** ![chakravala](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chakravala/32/6832_2.png) [@chakravala](https://discourse.julialang.org/u/chakravala)\
**Post date:** [November 5, 2018, 3:07pm UTC](https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166/3 "2018-11-05T15:07:10Z")

</div>

Why are there multiple versions of factorial, and is this an ambiguity that happens more often, or does it only happen with factorial?

---

<div class="post-metadata">

**Author:** ![affans](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/affans/32/11911_2.png) [@affans](https://discourse.julialang.org/u/affans)\
**Post date:** [November 5, 2018, 3:09pm UTC](https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166/4 "2018-11-05T15:09:50Z")

</div>

It’s the strength of Julia by dispatching in type. The algorithm for factorial (or any other function) may be optimized for different types.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 5, 2018, 3:12pm UTC](https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166/5 "2018-11-05T15:12:12Z")

</div>

> [@chakravala](#):
>
> does it only happen with factorial?

Try `methods(*)` in the REPL.

---

<div class="post-metadata">

**Author:** ![chakravala](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chakravala/32/6832_2.png) [@chakravala](https://discourse.julialang.org/u/chakravala)\
**Post date:** [November 5, 2018, 3:16pm UTC](https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166/6 "2018-11-05T15:16:01Z")

</div>

Right, I’m aware of the multiple dispatch of Julia, I use it all the time. But normally, if a function is extended, it was extended globally, but maybe the behavior is different in 1.0, so it should still have all the same methods available if it is reassigned to a new name, shouldnt it?

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 5, 2018, 3:17pm UTC](https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166/7 "2018-11-05T15:17:23Z")

</div>

I don’t know what extended globally means but `factorial` is no different from `*`

```julia
julia> methods(factorial)
# 7 methods for generic function "factorial":
[1] factorial(n::UInt128) in Base at combinatorics.jl:26
[2] factorial(n::Int128) in Base at combinatorics.jl:25
[3] factorial(x::BigFloat) in Base.MPFR at mpfr.jl:594
[4] factorial(x::BigInt) in Base.GMP at gmp.jl:564
[5] factorial(n::Union{Int64, UInt64}) in Base at combinatorics.jl:27
[6] factorial(n::Union{Int16, Int32, Int8, UInt16, UInt32, UInt8}) in Base at combinatorics.jl:33
[7] factorial(n::Integer) in Base at intfuncs.jl:820

```

---

<div class="post-metadata">

**Author:** ![chakravala](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chakravala/32/6832_2.png) [@chakravala](https://discourse.julialang.org/u/chakravala)\
**Post date:** [November 5, 2018, 3:21pm UTC](https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166/8 "2018-11-05T15:21:39Z")

</div>

Well, if I do `g = factorial` and take `methods` of that, then all the definitions are retained. So, it behaves as I expected. I figured thats what OP meant by renaming the function.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [November 5, 2018, 3:25pm UTC](https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166/9 "2018-11-05T15:25:54Z")

</div>

> [@chakravala](#):
>
> I figured thats what OP meant by renaming the function.

No, they copied the source code of one method.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [November 5, 2018, 4:05pm UTC](https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166/10 "2018-11-05T16:05:06Z")

</div>

> [@frank](#):
>
> As an experiment, I copy/pasted Julia’s [factorial() function](https://github.com/JuliaLang/julia/blob/0d713926f85dfa3e4e0962215b909b8e47e94f48/base/intfuncs.jl#L784-L810) and renamed it.

.

---

<div class="post-metadata">

**Author:** ![frank](https://avatars.discourse-cdn.com/v4/letter/f/3d9bf3/32.png) [@frank](https://discourse.julialang.org/u/frank)\
**Post date:** [November 5, 2018, 4:32pm UTC](https://discourse.julialang.org/t/how-is-factorial-bigint-so-fast/17166/11 "2018-11-05T16:32:47Z")

</div>

Mystery solved, thanks!