Re: Better use of random number generator bits?

Ben Rudiak-Gould wrote:
DAC wrote:
[in "Better use of random number genator bits?" thread]
This is important for us because for example to shuffle a deck of cards we
are taking 51 random numbers (between 0 and 51 down to between 0 and 1).
This on average is a total of about 2880 bits to shuffle a deck (of course
there is no maximum on this number and I have encounter one situation that
took over 13,000 bits), where you should really only need log2(52!) = 226
bits to specify a specific shuffle. So at the moment we are using on average
10 times as many bits as we really need - and quantum generator modules are
expensive and soon we will need the numbers at a rate faster than we can
produce them.

You might consider the algorithm described here:

http://groups.google.com/group/comp.lang.functional/browse_frm/thread/570615e64e3e4fc0

It's multiplication- and division-free and uses very close to n*log2(n) bits
on average, which unfortunately is rather larger than log2(n!) for small n.
For n=52 it needs 299 bits, versus 52*log2(52) = 296 and log2(52!) = 226.
....

Following approach uses 226 bits, if I did the arithmetic
right. Create k-bit numbers (with k as in left column)
and then divide and mod to extract randoms under the sizes
shown at the right. The middle column (labeled L) is
approximate base 2 log of product of right numbers.

k L r
17 16.99 52 51 49
22 21.99 50 48 47 37
27 26.99 46 45 44 43 34
16 15.99 42 41 38
31 30.95 40 39 36 35 33 32
29 28.98 31 30 29 28 27 26
31 30.95 25 24 23 22 20 19 18
31 30.94 21 17 16 15 14 13 12 11
22 21.79 10 9 8 7 6 5 4 3 2 1

-jiw
.

Relevant Pages

  • Re: Better use of random number generator bits?
    ... This on average is a total of about 2880 bits to shuffle a deck (of ... The middle column is ... Where did you come up with those multiples, some very good work if it was ...
    (sci.math)
  • Re: Marke Cards/Stacking (LSJ) (rules team)
    ... deck so that a methodical pile shuffle will move certain cards together ... is not a shuffle at all. ... If you mean some method that fails to sufficiently randomize the decks, ...
    (rec.games.trading-cards.jyhad)
  • Re: spin-off topic: Is deal making inherent to mutiplayer games?
    ... playing the game, is not stalling. ... players build decks which necessitate ... then any deck which takes a long time per round ... "Shuffle" strategies look pretty time consuming. ...
    (rec.games.trading-cards.jyhad)
  • Re: Quote of the day
    ... grand proclamations to the effect of "I have super high standards that ... I have never seen anyone cut the cards in all the ... Frankly I don't recall if I ever cut the deck but having reasonable ... deck blackjack table style shuffle). ...
    (rec.games.bridge)
  • Re: Card dealing and random repetition
    ... and inspiring for an 'elegant' way to simulate a shuffle. ... The dealer divide the deck in two parts, trying to make them equally big (but I estimate the error margin being between 1 to 5 cards from the count of 26 cards per half-deck). ... adding a random probability of the next card on the array being picked instead of the next of the other array. ...
    (comp.programming)