/* 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