[Chicago] Throw those dice!!!!

[Adam Forsyth]

Douglas,

Using your algorithm -- generating all possible rolls -- but a different
implementation, the best I was able to do was calculate the frequencies for
11 dice in a couple of minutes. So there is no way the naive algorithm can
handle large numbers of dice. If you're looking to speed yours up, I
suggest you work on writing your own version of the built-in
itertools.product, as this is at least the second problem you've posted to
the list where that would have come in handy.

Using a different algorithm, I was able to calculate the frequencies for
1000+ dice in just a few seconds (though there is a bug in my code causing
the answers to be wrong for more than ~20 dice). Calculating the
frequencies is the same as calculating the coefficients for the expansion
of the polynomial:

(x**6 + x ** 5 + .... x ** 2 + x + 1) ** n

where n is the number of dice. While this is complicated, doing it for two
sided dice is simple -- you're using the binomial theorem
<https://en.wikipedia.org/wiki/Binomial_theorem>, and the coefficients
<https://en.wikipedia.org/wiki/Binomial_coefficient> for a given n are the
nth row of Pascal's Triangle
<https://en.wikipedia.org/wiki/Pascal%27s_triangle>. I found a paper
<http://digitalscholarship.unlv.edu/cgi/viewcontent.cgi?article=2852&context=thesesdissertations>
that gives the formula we need to do this for n-sided dice instead of
two-sided dice -- property 6 given in section 2.1.2.

I've put my work in a gist
<https://gist.github.com/agfor/8c59d6a6e9a643223f2d>.

*I'll buy lunch for anyone who can correct the mistake in my code.*
Adam



On Sun, Aug 2, 2015 at 8:16 PM, Joshua Herman <zitterbewegung at gmail.com>
wrote:

> Dear Lewitt,
> What is the expected value of two die rolls? Also, given N dice rolls
> could I create a compression algorithm for those dice rolls?
> Sincerely,
> Joshua Herman
>
> On Sun, Aug 2, 2015 at 8:04 PM Lewit, Douglas <d-lewit at neiu.edu> wrote:
>
>> Hey guys,
>>
>> I will admit that I'm rather proud of this little Python program that I
>> wrote, but for values larger than 6 either the program crashes because of a
>> stack overflow or the program becomes really painfully SLOW!
>>
>> Let me explain what this program does.  Let's say that you roll two
>> dice.  What are all the possible sums.  If both dice land with the one-side
>> face up, that's a sum of 2.  If both dice land with the six-side face up,
>> that is 6 + 6, which gives you a sum of 12.  Then you have all the sums in
>> between.  Any student of statistics will tell you that these sums are NOT
>> all equally probable or equally likely.  For example, in the case of two
>> dice, the most probable sum is 7 because there are several ways to get that
>> sum.  First die = 3, second die = 4, {3, 4} or {4, 3} or {5, 2} or {2, 5}
>> or {1, 6} or {6, 1} or ..... get the idea?
>>
>> But why limit ourselves to just two dice?  What about three dice?  Or
>> four dice?  Or five dice?  Or six dice?  Or any number of dice that we
>> choose to throw?
>>
>> My approach works pretty well for any number of dice from 1 to 6.  Beyond
>> 6 however, that's when I run into some real problems.
>>
>> Is there an "easy" way to fix this?  Probably not, but I thought I would
>> check with people who are more experienced in Python than I am.
>>
>> I appreciate the feedback, but may not be able to reply until next
>> weekend.  I'm VERY busy this week!  But still I appreciate any constructive
>> feedback that you can provide.
>>
>> Many thanks,
>>
>> Douglas Lewit
>>
>> _______________________________________________
>> Chicago mailing list
>> Chicago at python.org
>> https://mail.python.org/mailman/listinfo/chicago
>>
>
> _______________________________________________
> Chicago mailing list
> Chicago at python.org
> https://mail.python.org/mailman/listinfo/chicago
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/chicago/attachments/20150802/a4180c11/attachment.html>