4 ms·

This won't work. f gives 1 to 5. 7 * f gives 7 to 35. But 7 to 35 will not be evenly generated. Think about it: There are more ways to get a 20 than there are t

• nostrademons 18y ago
  That was my second thought too (my first thought was to upvote the comment), but at least in the 2-die case, the modulus takes care of it. If you work out the probabilities, the chance of getting 0mod2 = 1/36 (2) + 3/36 (4) + 5/36 (6) + 5/36 (8) + 3/36 (10) + 1/36 (12) = 18/36 = 1/2. Same goes for getting 1mod2. So you end up with a fair result even though the chances for each individual outcome are biased. I didn't want to go through all 5^7 possibilities for the 7-die case, but I figured it's likely enough that he's right that I'd keep my mouth shut.
  • llimllib 18y ago
    experimental evidence says that it is in fact a uniform distribution: r = random.Random() def one_to_five(): return r.randint(1, 5) def mod_seven(): return (sum(one_to_five() for x in xrange(7)) % 7) + 1 def test_dist(lst): return [(x, lst.count(x)) for x in [1,2,3,4,5,6,7]]
    • sdfx 18y ago
      i've tried it out experimentally in google docs and it looks really good for big numbers. No real proof tho and it might be that the errors counter each other by chance: http://spreadsheets.google.com/ccc?key=pq4tB7LQWN03gF7ImGhIPAw http://spreadsheets.google.com/ccc?key=pq4tB7LQWN03gF7ImGhIP...
      • greendestiny 18y ago
        Have a look at the distributions for each sum here: http://brianpmearns.com/ext/dice/dice.html http://brianpmearns.com/ext/dice/dice.html edit: Oops bad addition on my part, could be uniform, but you'd have to work out the actual number exactly.
        • sdfx 18y ago
          here are the exact numbers: 1 -> 11177 2 -> 11172 3 -> 11158 4 -> 11144 5 -> 11144 6 -> 11158 7 -> 11172 ...not quite
    • gaius 18y ago
      I've done a lot of Python but never knew about xrange - thanks!
• MaysonL 18y ago
  f * f gives you 25 boxes, number 11, 12, ... 15, 21,...25...55. Assign 3 each of 21 of those to 1..7. If f * f doesn't fall into one of those 21 boxes, repeat until it does.
  • andreyf 18y ago
    Runtime: O(infinity)?
    • paulgb 18y ago
      Technically speaking, yes. But, if you want to uniformly map a random number from set X to set Y where (IIRC) lcm(|X|, |Y|) != |X|, it seems you need an infinite worst-case running time. Here's an informal proof that you can't have a finite upper bound to the number of iterations. After n iterations, you have |X|^n possible outcomes. But, since lcm(|X|, |Y|) != |X|, |X|^n cannot be divided evenly by |Y| (since its factors are the same). So some outcomes in Y must be more likely than others. (This is not nearly complete, but hopefully it's enough to show how it might be right.) Of course, in practice it is highly unlikely that you will get past more than a couple iterations before determining an outcome.
      • deleted 18y ago
        [deleted]
      • andreyf 18y ago
        since lcm(|X|, |Y|) != |X|, |X|^n cannot be divided evenly by |Y| (since its factors are the same) Can you go into more detail about this part?
        • paulgb 18y ago
          Sure. Sorry, I didn't take the time to work this out on paper before posting or I would have realized that the condition itself is wrong. The condition lcm(|X|,|Y|) != |X| instead should be that |Y| has some prime factor that |X| does not. Here is an explanation with the new condition: Let p be any prime factor of |Y| that |X| does not have. It follows from Euclid's First Theorem[1] that p cannot divide |X|^n for any n [2]. Since every integer (> 1) has a unique prime factorization, it follows that |X|^n can't divide |Y|, because the prime p divides |Y| but not |X|^n. [1] http://mathworld.wolfram.com/EuclidsTheorems.html http://mathworld.wolfram.com/EuclidsTheorems.html [2] We are given that p does not divide |X|^1. Suppose that p also does not divide |X|^(n-1) for some n > 1. |X|^n = |X|^(n-1) * |X|^1, so by Euclid's First Theorem, if p divides |X|^n it must divide either |X|^(n-1) or |X|^1. We know it divides neither, so p does not divide |X|^n. By induction, this is true for all n > 0.
• deleted 18y ago
  [deleted]
• hhm 18y ago
  You're right in that my original reasoning was wrong. Thank you for your comment.
• hhm 18y ago
  Ok, a less elegant one then, but one that works for a reasonably simple reason. f gives 1 to 5, if it gives 5, try again, and so on, until you have a number from 1 to 4. Then, do that mod 2. You have a random binary digit, that's unbiased. Now use that process to get 3 binary digits. You get a random number from 0 to 7. If the random number is 0, start again... eventually you'll get a number from 1 to 7, and all numbers have the same chances.