Binomial for BigInt does not work with k > typemax(UInt64)

[originalsouth]

1. The output of versioninfo()

Julia Version 1.8.4
Commit 00177ebc4fc (2022-12-23 21:32 UTC)
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 16 × AMD Ryzen 7 5800U with Radeon Graphics
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-13.0.1 (ORCJIT, znver3)
  Threads: 1 on 16 virtual cores

2. How you installed Julia
   See https://aur.archlinux.org/packages/julia-bin

3. A minimal working example (MWE), also known as a minimum reproducible example

julia> binomial(big(1), big(typemax(UInt64))+1)
ERROR: InexactError: UInt64(18446744073709551616)
Stacktrace:
 [1] Type
   @ ./gmp.jl:354 [inlined]
 [2] binomial(n::BigInt, k::BigInt)
   @ Base.GMP ./gmp.jl:685
 [3] top-level scope
   @ REPL[3]:1

Culprit base/gmp.jl:685:

binomial(n::BigInt, k::Integer) = k < 0 ? BigInt(0) : binomial(n, UInt(k))

This is probably a limitation due to GMP, but in that case

1. Probably binomial(n::BigInt, k::Integer) = k < 0 ? BigInt(0) : binomial(n, UInt(min(k, n-k))) will cover more cases,
2. Limitations are not currently documented.

Please advise on how to proceed — if at all — thanks!

[oscardssmith]

Your solution seems like a good start. the limitation is due to GMP so unless we want to make a pure Julia binomial (which I kind of doubt) it's probably all we are going to want to do.

[fingolfin]

This limitation is also due to the limited storage of computers as they exist today. I.e., the smallest (?) case not covered by the improvement @originalsouth proposes is this: binomial(big(2)^65, big(2)^64). An extremely generous (bad lower bound for this value is $2^{2^{64}}$. Storing the actual value would require more storage than any computer currently in existence has (I am too lazy to check if it also exceeds the total amount of memory available when adding all compute storage ever built, but let's just say that slightly larger inputs will easily get there).

So in this sense, the patch by @originalsouth is the best possible. And this also explain why the GMP authors "limited" the API in this way: there is just no point in offering a more general API.

[originalsouth]

Fixed by #48073.