math - Probability of getting specific sum after rolling n dice. Ruby -

what best solution finding probability of rolling sum n dice? i'm solving finding

1. mean.
2. standard deviation.
3. z_score numbers below x
4. z_score numbers above x
5. converting both probabilities
6. subtracting 1 other

this i've done far.

# sides - number of sides on 1 die def get_mean(sides)   (1..sides).inject(:+) / sides.to_f end  def get_variance(sides)   mean_of_squares = ((1..sides).inject {|sum, side| sum + side ** 2}) / sides.to_f   square_mean = get_mean(sides) ** 2    mean_of_squares - square_mean end  def get_sigma(variance)   variance ** 0.5 end  # x - number of points in question def get_z_score(x, mean, sigma)   (x - mean) / sigma.to_f end  # converts z_score probability def z_to_probability(z)   return 0 if z < -6.5   return 1 if z > 6.5    fact_k = 1   sum = 0   term = 1   k = 0    loop_stop = math.exp(-23)   while term.abs > loop_stop     term = 0.3989422804 * ((-1)**k) * (z**k) / (2*k+1) / (2**k) * (z**(k+1)) / fact_k     sum += term     k += 1     fact_k *= k   end    sum += 0.5   1 - sum end  # calculate probability of getting 'х' total points rolling 'n' dice 'sides' number of sides. def probability_of_sum(x, n, sides=6)    mean = n * get_mean(sides)   variance = get_variance(sides)   sigma = get_sigma(n * variance)    # rolling below sum   z1 = get_z_score(x, mean, sigma)   prob_1 = z_to_probability(z1)    # rolling above sum   z2 = get_z_score(x+1, mean, sigma)   prob_2 = z_to_probability(z2)    prob_1 - prob_2 end  # run probability 100 dice puts probability_of_sum(400, 100) 

what concerns me is, when pick x = 200, probability 0. correct solution?

there exact solution involving alternating sum of binomial coefficients. have written out in few places (on quora , mse), , can find elsewhere although there flawed versions. careful if implement that, may need cancel binomial coefficients larger final result, , if use floating point arithmetic might lose precision.

neil slater's suggestion use dynamic programming compute convolution one. slower summation of binomial coefficients, reasonably robust. can speed in few ways, such using exponentiation squaring, , using fast fourier transform, many people find overkill.

to fix method, should use (simple) continuity correction normal approximation, , restrict context have enough dice , evaluating far enough maximum , minimum expect normal approximation good, either in absolute or relative sense. continuity correction replace count of n interval n-1/2 n+1/2.

the exact count of number of ways roll total of 200 7745954278770349845682110174816333221135826585518841002760, probability divided 6^100, 1.18563 x 10^-20.

the normal approximation simple continuity correction phi((200.5-350)/sqrt(3500/12))-phi((199.5-350)/sqrt(3500/12)) = 4.2 x 10^-19. accurate in absolute terms, since close 0, off factor of 35 it's not great in relative terms. normal approximation gives better relative approximation closer center.