/*
Copyright (C) 2026 Stephen Hewitt cambridgeclarion.org
This file is free software: you can redistribute it and/or modify
it under the terms of version 3 of the GNU General Public Licence as
published by the Free Software Foundation.
It is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public Licence version 3 for more details.
You should have received a copy of the GNU General Public Licence
version 3 with this programme. If not, see .
*/
/*
A single-file programme to calculate the probability of generating each possible number of random bits
using a particular method (cambridgeclarion.org/110.html) to generate random bits
from a deck of shuffled playing cards.
It also calculates qualitatively the max and min possible number of bits generated.
*/
#include
class Exponent {
public:
unsigned bits;
unsigned mask;
};
// an array indexed by j to give 2^j
static const Exponent exponents[] = {
{0,1},
{1,2},
{2,4},
{3,8},
{4,16},
{5,32},
};
const unsigned INITIAL_CARDS_IN_DECK_N = 52;
const unsigned MAX_ARRAY_BITS_N = 205; // max bits = 203 but leave slack in array for now. don't reduce this unless you know what you are doing.
int main(int argc, char* argv[])
{
unsigned min_possible_bits_so_far = 0;
unsigned max_possible_bits_so_far = 0;
// in the following table, prob[c][k] is probability that number of bits we have is k when there are c cards remaining in deck
double probs[INITIAL_CARDS_IN_DECK_N + 1][MAX_ARRAY_BITS_N + 1] = {};
probs[INITIAL_CARDS_IN_DECK_N][0] = 1; // before dealing any cards it is certain we have 0 bits
// (we don't deal the last card in the deck since it yields no info)
for (unsigned remaining_cards_n = INITIAL_CARDS_IN_DECK_N; remaining_cards_n > 1; remaining_cards_n--)
{
unsigned min_delta_bits; // min bits gained from dealing this card
unsigned max_delta_bits;
for (unsigned exp = 5; exp > 0; exp--)
{
if (exponents[exp].mask & remaining_cards_n)
{
max_delta_bits = exp;
break;
}
}
for (unsigned exp = 0; exp <= 5; exp++)
{
if (exponents[exp].mask & remaining_cards_n)
{
min_delta_bits = exp;
break;
}
}
// defensive
if (max_delta_bits + max_possible_bits_so_far > MAX_ARRAY_BITS_N)
{
fprintf(stderr, "Internal error array overflow\n");
return 99;
}
for (unsigned exp = 0; exp <= 5; exp++)
{
unsigned range = exponents[exp].mask; // range is a power of two
// a bit set/clear in the binary representation of the number of remaining cards indicates
// the presence/absence of the corresponding power-of-two range in the cards on the table
if (remaining_cards_n & range)
{
double range_prob = static_cast(range)/remaining_cards_n; // probability of card falling in this range
unsigned delta_bits_n = exp; // number of bits we get if it does
for (unsigned bits_i = min_possible_bits_so_far; bits_i <= max_possible_bits_so_far; bits_i++)
{
probs[remaining_cards_n - 1][delta_bits_n + bits_i] += probs[remaining_cards_n][bits_i]*range_prob;
}
}
}
min_possible_bits_so_far += min_delta_bits;
max_possible_bits_so_far += max_delta_bits;
}
printf("min possible bits = %u; max possible bits = %u;\n", min_possible_bits_so_far, max_possible_bits_so_far);
// Now convert from probability of k bits to probability of less than k bits
double accumulator = 0;
for (unsigned bits_i = min_possible_bits_so_far - 1; bits_i <= max_possible_bits_so_far; bits_i++)
{
accumulator += probs[1][bits_i];
printf("k = %u, p(bits