using table lookup to improve performance you might not want to try running crapssim( at home it takes long time to complete on most computers that raises the question of whether there is simple way to speed up the simulation the complexity of crapssim is (playhand)*handspergame*numgames the running time of playhand depends upon the number of times the loop in it is executed in principlethe loop could be executed an unbounded number of times since there is no bound on how long it could take to roll either seven or the point in practiceof coursewe have every reason to believe it will always terminate noticehoweverthat the result of call to playhand does not depend on how many times the loop is executedbut only on which exit condition is reached for each possible pointone can easily calculate the probability of rolling that point before rolling seven for exampleusing pair of dice one can roll in three different waysand and one can roll in six different waysand thereforeexiting the loop by rolling is twice as likely as exiting the loop by rolling figure contains an implementation of playhand that exploits this thinking we have pre-computed the probability of making the point before rolling for each possible value of the pointand stored those values in dictionary supposefor examplethat the point is the shooter continues to roll until he either rolls the point or rolls craps there are five ways of rolling an (and and six ways of rolling sothe value for the dictionary key is the value of the expression having this table allows us to replace the inner loopwhich contained an unbounded number of rollswith test against one call to random random the asymptotic complexity of this version of playhand is ( the idea of replacing computation by table lookup has broad applicability and is frequently used when speed is an issue table lookup is an example of the general idea of trading time for space we saw another example of this technique in our analysis of hashingthe larger the tablethe fewer the collisionsand the faster the average lookup in this casethe table is smallso the space cost is negligible