multinomial() may lead to hidden overflow

[sylvaticus]

multinomial internally uses binomial. While the latter check for overflow, the whole computation of multinomial is not checked for overflow, leading to :

multinomial(150, 150, 150, 150) --> error overflow reported by binomial
multinomial(15, 15, 15, 15) --> no error reported

See also this thread on Discourse.

[GoodDayToYouAll]

Since this has been dormant for a while and I ran into this exact problem, I wanted to give this issue a small kick:

I would say that multinomial(15,15,15) returning a negative value is very dangerous and can lead to very hard to detect bugs.

[inkydragon]

A quick fix that detects the overflow properly:

function multinomial(k...)
    s = 0
    result = 1
    @inbounds for i in k
        s += i
        bi = binomial(s, i)
        result, f = Base.mul_with_overflow(result, bi)
        f && error("overflow: $(result)")
    end
    result
end

julia> multinomial(15, 15, 15, 15)
ERROR: overflow: -1845252435754023168
Stacktrace:

Need to further examine the performance cost and see if we need to put the error path outside of the for loop, and then we can send the pr.