# Example 873 — The id space was smaller than the records `the_id_space_was_smaller_than_the_records.eml` - Every record is given a random four-character hex identifier, and every identifier is drawn uniformly by the engine's generator and checked for format. How many distinct identifiers four hex characters can hold is computed below. ## EML ```eml # Self-authored for the EML case corpus (no external origin). Every record is # given a random four-character hex identifier, and every identifier is drawn # uniformly by the engine's generator and checked for format. How many distinct # identifiers four hex characters can hold is computed below. # # The assignment is careful. It uses the engine's own random generator, not a # counter someone could guess; every record receives an identifier; every # identifier passes the format check; and the intent is exactly 'every record has # a unique identifier'. # # Four hex characters hold 65536 values, and at one hundred thousand records the # pigeonhole principle forces at least 34464 records to share - while at only a # thousand records the birthday bound already expects seven colliding pairs. 65536 => id_space 100000 => records_at_scale 1000 => records_early records_at_scale - id_space => records_that_must_share_an_id int(records_that_must_share_an_id * 10000 / records_at_scale) => forced_sharing_per_myriad records_early - 1 => early_minus_one 2 * id_space => twice_id_space int(records_early * early_minus_one / twice_id_space) => expected_colliding_pairs_early "identifier space (4 hex chars) : " + str(id_space) ^0 "records at scale : " + str(records_at_scale) ^0 "records that must share an id : at least " + str(records_that_must_share_an_id) ^0 "forced sharing : " + str(forced_sharing_per_myriad) + " per ten thousand" ^0 "" ^0 "records early on : " + str(records_early) ^0 "expected colliding pairs early : " + str(expected_colliding_pairs_early) ^0 "chance of at least one collision at " + str(records_early) + " : 9995 per ten thousand" ^0 "" ^0 # ---- what the assignment verified ---- "the identifier assignment" ^0 " generator : the engine's own, uniform" ^0 " coverage : every record receives an identifier" ^0 " format : every identifier passes the check" ^0 " intent : every record has a unique identifier" ^0 " records without an identifier : 0" ^0 " verdict : EVERY RECORD HAS A WELL-FORMED RANDOM ID" ^0 "" ^0 " drawing every identifier uniformly from the engine's" ^0 " generator is the part done right here, and it is why no" ^0 " identifier is guessable from the one before it" ^0 "" ^0 # ---- how many the space can hold ---- "the size of the space" ^0 " four hex characters : sixteen to the fourth, " + str(id_space) ^0 " records at scale : " + str(records_at_scale) ^0 " pigeonhole : more records than identifiers, so at least" ^0 " " + str(records_that_must_share_an_id) + " must share, however they are drawn" ^0 " birthday, at " + str(records_early) + " records : pairs of records over" ^0 " twice the space, about " + str(expected_colliding_pairs_early) + " colliding pairs expected" ^0 " so uniqueness : impossible at scale, and already unlikely" ^0 " at a thousand" ^0 "" ^0 # ---- what the caller got ---- "the uniqueness assumption" ^0 " relied on : every lookup by identifier returns one record" ^0 " at scale, records sharing an identifier : at least " + str(records_that_must_share_an_id) ^0 " early on, colliding pairs expected : " + str(expected_colliding_pairs_early) ^0 " is the generator biased : no; it is uniform" ^0 " can a uniform draw from 65536 be unique for 100000 : no;" ^0 " there are not enough values to be unique with" ^0 "" ^0 # ---- null control ---- # The same assignment from a space far larger than the square of the record # count (a 128-bit identifier), or from a sequence that never repeats. 34464 => nc_forced_sharing_in_four_hex 0 => nc_forced_sharing_in_128_bits 7 => nc_expected_early_collisions_in_four_hex 0 => nc_expected_early_collisions_in_128_bits "null control - a space larger than records squared" ^0 " forced sharing, four hex : at least " + str(nc_forced_sharing_in_four_hex) ^0 " forced sharing, 128 bits : " + str(nc_forced_sharing_in_128_bits) ^0 " expected early collisions, four hex : " + str(nc_expected_early_collisions_in_four_hex) ^0 " expected early collisions, 128 bits : " + str(nc_expected_early_collisions_in_128_bits) ^0 " no record and no generator changed; the space stopped" ^0 " being smaller than the set it had to name" ^0 "" ^0 # ---- the rule ---- "what a uniform random identifier guarantees" ^0 " each identifier is an unbiased draw from the space :" ^0 " exactly, the engine's own generator over every record" ^0 " each identifier is unique : not addressed; the space is" ^0 " " + str(id_space) + " and the records " + str(records_at_scale) + ", so at least " + str(records_that_must_share_an_id) + " must" ^0 " share, and even at " + str(records_early) + " the birthday bound expects " + str(expected_colliding_pairs_early) ^0 " colliding pairs" ^0 "" ^0 "randomness does not create room; a draw can only be unique among draws when the" ^0 "space is large against the square of their number, and no generator, however" ^0 "fair, can fit more pigeons than holes" ^0 "" ^0 "It draws every identifier uniformly from the engine's generator - none is" ^0 "guessable. But four hex characters hold " + str(id_space) + " values against " + str(records_at_scale) + " records," ^0 "so at least " + str(records_that_must_share_an_id) + " must share, " + str(forced_sharing_per_myriad) + " per ten thousand, and at only " + str(records_early) ^0 "records " + str(expected_colliding_pairs_early) + " colliding pairs are already expected, until the space outgrows the records squared." ^0 ``` ## Python (deterministic transpilation) ```python id_space = 65536 records_at_scale = 100000 records_early = 1000 records_that_must_share_an_id = records_at_scale - id_space forced_sharing_per_myriad = int(records_that_must_share_an_id * 10000 / records_at_scale) early_minus_one = records_early - 1 twice_id_space = 2 * id_space expected_colliding_pairs_early = int(records_early * early_minus_one / twice_id_space) print("identifier space (4 hex chars) : " + str(id_space)) print("records at scale : " + str(records_at_scale)) print("records that must share an id : at least " + str(records_that_must_share_an_id)) print("forced sharing : " + str(forced_sharing_per_myriad) + " per ten thousand") print("") print("records early on : " + str(records_early)) print("expected colliding pairs early : " + str(expected_colliding_pairs_early)) print("chance of at least one collision at " + str(records_early) + " : 9995 per ten thousand") print("") print("the identifier assignment") print(" generator : the engine's own, uniform") print(" coverage : every record receives an identifier") print(" format : every identifier passes the check") print(" intent : every record has a unique identifier") print(" records without an identifier : 0") print(" verdict : EVERY RECORD HAS A WELL-FORMED RANDOM ID") print("") print(" drawing every identifier uniformly from the engine's") print(" generator is the part done right here, and it is why no") print(" identifier is guessable from the one before it") print("") print("the size of the space") print(" four hex characters : sixteen to the fourth, " + str(id_space)) print(" records at scale : " + str(records_at_scale)) print(" pigeonhole : more records than identifiers, so at least") print(" " + str(records_that_must_share_an_id) + " must share, however they are drawn") print(" birthday, at " + str(records_early) + " records : pairs of records over") print(" twice the space, about " + str(expected_colliding_pairs_early) + " colliding pairs expected") print(" so uniqueness : impossible at scale, and already unlikely") print(" at a thousand") print("") print("the uniqueness assumption") print(" relied on : every lookup by identifier returns one record") print(" at scale, records sharing an identifier : at least " + str(records_that_must_share_an_id)) print(" early on, colliding pairs expected : " + str(expected_colliding_pairs_early)) print(" is the generator biased : no; it is uniform") print(" can a uniform draw from 65536 be unique for 100000 : no;") print(" there are not enough values to be unique with") print("") nc_forced_sharing_in_four_hex = 34464 nc_forced_sharing_in_128_bits = 0 nc_expected_early_collisions_in_four_hex = 7 nc_expected_early_collisions_in_128_bits = 0 print("null control - a space larger than records squared") print(" forced sharing, four hex : at least " + str(nc_forced_sharing_in_four_hex)) print(" forced sharing, 128 bits : " + str(nc_forced_sharing_in_128_bits)) print(" expected early collisions, four hex : " + str(nc_expected_early_collisions_in_four_hex)) print(" expected early collisions, 128 bits : " + str(nc_expected_early_collisions_in_128_bits)) print(" no record and no generator changed; the space stopped") print(" being smaller than the set it had to name") print("") print("what a uniform random identifier guarantees") print(" each identifier is an unbiased draw from the space :") print(" exactly, the engine's own generator over every record") print(" each identifier is unique : not addressed; the space is") print(" " + str(id_space) + " and the records " + str(records_at_scale) + ", so at least " + str(records_that_must_share_an_id) + " must") print(" share, and even at " + str(records_early) + " the birthday bound expects " + str(expected_colliding_pairs_early)) print(" colliding pairs") print("") print("randomness does not create room; a draw can only be unique among draws when the") print("space is large against the square of their number, and no generator, however") print("fair, can fit more pigeons than holes") print("") print("It draws every identifier uniformly from the engine's generator - none is") print("guessable. But four hex characters hold " + str(id_space) + " values against " + str(records_at_scale) + " records,") print("so at least " + str(records_that_must_share_an_id) + " must share, " + str(forced_sharing_per_myriad) + " per ten thousand, and at only " + str(records_early)) print("records " + str(expected_colliding_pairs_early) + " colliding pairs are already expected, until the space outgrows the records squared.") ``` ## stdout (executed) ```text identifier space (4 hex chars) : 65536 records at scale : 100000 records that must share an id : at least 34464 forced sharing : 3446 per ten thousand records early on : 1000 expected colliding pairs early : 7 chance of at least one collision at 1000 : 9995 per ten thousand the identifier assignment generator : the engine's own, uniform coverage : every record receives an identifier format : every identifier passes the check intent : every record has a unique identifier records without an identifier : 0 verdict : EVERY RECORD HAS A WELL-FORMED RANDOM ID drawing every identifier uniformly from the engine's generator is the part done right here, and it is why no identifier is guessable from the one before it the size of the space four hex characters : sixteen to the fourth, 65536 records at scale : 100000 pigeonhole : more records than identifiers, so at least 34464 must share, however they are drawn birthday, at 1000 records : pairs of records over twice the space, about 7 colliding pairs expected so uniqueness : impossible at scale, and already unlikely at a thousand the uniqueness assumption relied on : every lookup by identifier returns one record at scale, records sharing an identifier : at least 34464 early on, colliding pairs expected : 7 is the generator biased : no; it is uniform can a uniform draw from 65536 be unique for 100000 : no; there are not enough values to be unique with null control - a space larger than records squared forced sharing, four hex : at least 34464 forced sharing, 128 bits : 0 expected early collisions, four hex : 7 expected early collisions, 128 bits : 0 no record and no generator changed; the space stopped being smaller than the set it had to name what a uniform random identifier guarantees each identifier is an unbiased draw from the space : exactly, the engine's own generator over every record each identifier is unique : not addressed; the space is 65536 and the records 100000, so at least 34464 must share, and even at 1000 the birthday bound expects 7 colliding pairs randomness does not create room; a draw can only be unique among draws when the space is large against the square of their number, and no generator, however fair, can fit more pigeons than holes It draws every identifier uniformly from the engine's generator - none is guessable. But four hex characters hold 65536 values against 100000 records, so at least 34464 must share, 3446 per ten thousand, and at only 1000 records 7 colliding pairs are already expected, until the space outgrows the records squared. ``` ## Round-trip `ok: true` — round-trip fixpoint reached (python1 == python2) ## Trace event types eml:run:start · eml:assign · eml:output · eml:run:done