CODEWITHSUNDEEP
pythonalgorithmmath
Stack Tracer
Stack Tracer

Reputation: 1028

How to calculate the sum of dice rolls efficiently?

The following code:

import random
def roll(num_dice,num_faces):
    return sum([random.randint(1,num_faces) for x in range(num_dice)])

does randomly generate the sum of num_dice num_faces-faced dice, but it is slow (O(N)) for large numbers of dice.

What is a more efficient way to calculate this in python?

Upvotes: 0

Views: 516

Answers (2)

Reiner Czerwinski
Reiner Czerwinski

Reputation: 296

You can calculate it much faster, if you use the multinominal distribution:

import numpy as np
def roll_np(num_dice,num_faces):
    return sum((np.array(range(num_faces))+1)*np.random.multinomial(num_dice,[1/float(num_faces)]*num_faces))

The runtime of this implemetion is independent from num_dice. I have tested it:

from time import time
t=time();roll_np(10000,6);print(time()-t)

34997

0.0005793571472167969

t=time();roll_np(10000,6);print(time()-t)

34938

0.0005676746368408203

t=time();roll_np(10000000,6);print(time()-t)

34996283

0.0006160736083984375

t=time();roll_np(10000000,6);print(time()-t)

34996047

0.000567913055419921

Upvotes: 0

Reiner Czerwinski
Reiner Czerwinski

Reputation: 296

To calculate it in O(1) have a look at this function:

https://docs.scipy.org/doc/numpy/reference/generated/numpy.random.multinomial.html

if you calculate

np.random.multinomial(num_dices,[1/float(num_faces)]*num_faces)

the execution time depends only from num_faces, not from num_dices

Upvotes: 2

Related Questions