[Chicago] Throw those dice!!!!

Wed Aug 5 21:54:15 CEST 2015

Ken, you're right, that way is much faster if you're calculating all of the
frequencies. The method I used is actually for calculating a single
frequency (a single coefficient of the expanded polynomial) and so wastes a
lot of calculations if you use it for all of the frequencies individually.

On Mon, Aug 3, 2015 at 10:11 PM, Ken Schutte <kenschutte at gmail.com> wrote:

> Note that you can solve this iteratively - which I think is easier and is
> much more efficient (at least in the cases where you want to compute the
> full distribution of possible sums):
>
> I tried it here, https://gist.github.com/kts/65d71c761baa9714151c
>
> I haven't fully tested it, but try running "$ time python multcoeff.py 6
> 1000 > out". which takes ~2.5sec on my little chromebook. It outputs the
> counts for all possible values, in this case they correspond to sums 1000,
> 1001, ..., 5999, 6000.
>
> The binomial coefficients can be computed in Pascal's triangle by simply
> sweeping across and adding two numbers from the row above. Here, it is
> similar, but you just have to add 6 numbers from the row above for each
> value.
>
> I think this is a nice example of "dynamic programming" - where an optimal
> solution depends upon a lot of highly overlapping sub-problems.  For
> example - how many ways can 100 dice add up to the value of 307? That is
> complicated, BUT if you know the distribution for 99 dice, it is trivial -
> you only have to know the counts for values 301,302,...,306 because those
> are the only sums of 99 dice that influence the question at hand.  And
> that's what this code does (and how one computes values in Pascal's
> triangle).
>
> A side note for anyone familiar with convolution - each level in computing
> such a triangle is really a convolution with all ones - for example K=6
> sided die is a convolution with [1,1,1,1,1,1].  Which makes you wonder if
> you can use fast (FFT, N log N) convolutions for such a problem - I would
> guess no in this case.
>
> Ken
>
>
> On Mon, Aug 3, 2015 at 2:00 PM, Adam Forsyth <adam at adamforsyth.net> wrote:
>
>> The bug has been spotted and fixed (off-list reply)! I updated the gist
>> <https://gist.github.com/agfor/8c59d6a6e9a643223f2d>. (range(m) replaced
>> with range(max(m, k)).) The fixed algorithm is still fast enough to handle
>> 1000 dice in about six minutes on my laptop.
>>
>> Adam
>>
>> On Sun, Aug 2, 2015 at 10:37 PM, Adam Forsyth <adam at adamforsyth.net>
>> wrote:
>>
>>> 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
>>>>
>>>>
>>>
>>
>> _______________________________________________
>> 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/20150805/750fcb03/attachment.html>