Skip to content

Instantly share code, notes, and snippets.

@becked

becked/old_world_rng_analysis_report.md

Last active December 6, 2025 23:24
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save becked/b6068d4bb2c6ad14d0eb873fdd4ed31e to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save becked/b6068d4bb2c6ad14d0eb873fdd4ed31e to your computer and use it in GitHub Desktop.
Download ZIP
Raw
old_world_rng_analysis_report.md

Old World RNG Implementation Analysis

Summary

This report documents an investigation into the random number generator (RNG) implementation used in Old World for character generation, specifically examining whether consecutive characters (such as courtiers granted to multiple players choosing the same family) could have correlated traits.

Key Findings:

  1. The game uses two different RNG algorithms: a Linear Congruential Generator (LCG) for seed derivation and a Park-Miller variant for actual random draws.

  2. Consecutive character seeds are mathematically related through a single LCG step.

  3. The Park-Miller implementation contains a bug where large seeds cause arithmetic underflow, leading to convergence of high-order bits after multiple iterations.

  4. After 3 Park-Miller steps, the top 16 bits become identical between consecutive characters.

  5. Despite this correlation, final trait selection remains statistically independent due to the SeedToInt function discarding the correlated high bits through bit-shifting and modulo operations.

  6. The system is accidentally safe for current use cases, but the underlying RNG weakness could be exploitable if the game used larger die sizes or different bit extraction methods.

Background: How Character Seeds Are Generated

When a new character is created (including courtiers from family seat bonuses), the game assigns a deterministic seed based on the character's ID:

// From Game.cs
public virtual ulong getSeedForId(int iID)
{
    RandomStruct pRandom = new RandomStruct(getFirstSeed());
    for (int i = 0; i <= iID; ++i)
    {
        pRandom.NextAltSeed();
    }
    return pRandom.GetSeed();
}

This means:

  • Character 0's seed = LCG(FirstSeed)
  • Character 1's seed = LCG(LCG(FirstSeed))
  • Character N's seed = LCG^(N+1)(FirstSeed)

Consecutive characters have seeds related by exactly one LCG step.

The Two RNG Algorithms

Algorithm 1: Linear Congruential Generator (NextAltSeed)

// From Random.cs
public ulong NextAltSeed()
{
    mulSeed = (mulSeed * 1103515245) + 12345;
    return mulSeed;
}

This is the classic glibc/ANSI C rand() formula operating on 64-bit unsigned integers. It's used exclusively for getSeedForId() to derive character seeds.

Algorithm 2: Park-Miller Variant (NextSeed)

// From Random.cs
private const int IA = 16807;
private const long IM = long.MaxValue;  // 9223372036854775807 - NEVER USED
private const int IQ = 127773;
private const int IR = 2836;

private ulong NextSeedNoUpdate()
{
    ulong k = mulSeed / IQ;
    return IA * (mulSeed - k * IQ) - IR * k;
}

public ulong NextSeed()
{
    mulSeed = NextSeedNoUpdate();
    return mulSeed;
}

This is used for all actual random draws: Next(), NextFloat(), RandomPercent(), etc.

The SeedToInt Function

// From Random.cs
static public int SeedToInt(ulong ulSeed, int iRange)
{
    return (int)((ulSeed >> 16) % (ulong)iRange);
}

public int Next(int iRange)
{
    if (iRange == 0)
        return 0;
    return SeedToInt(NextSeed(), iRange);
}

Issue 1: Park-Miller Implementation Bug

The Park-Miller constants (IQ=127773, IR=2836) were designed for a 31-bit modulus (2^31 - 1 = 2147483647). However:

  1. The code operates on 64-bit unsigned integers
  2. The modulus IM is defined but never actually used
  3. The subtraction IA * (mulSeed - k * IQ) - IR * k can produce negative results

When the result is negative, it underflows to a massive unsigned value:

Empirical Verification

Seed:               127773 (0x000000000001F31D)
  k = seed // IQ = 1
  Raw result: -2836
  After mod 2^64: 18446744073709548780 (0xFFFFFFFFFFFFF4EC)
  *** UNDERFLOW OCCURRED ***

Seed:  9223372036854775808 (0x8000000000000000)
  k = 72185610706915
  Raw result: -204718389855313949
  After mod 2^64: 18242025683854237667 (0xFD28B1B585AF1FE3)
  *** UNDERFLOW OCCURRED ***

For typical game seeds (large 64-bit values), underflow occurs frequently.

Issue 2: High-Bit Convergence

The underflow behavior causes consecutive seeds to converge toward identical high-order bits after multiple Park-Miller iterations.

Empirical Data: Bit-Level Correlation

Testing 1000 consecutive character pairs with FirstSeed=12345:

After 0 Park-Miller steps (initial LCG seeds):

Bits 48-63: 50% 49% 49% 50% 50% 52% 53% 51% 50% 50% 49% 53% 52% 50% 52% 49%
Bits 32-47: 50% 49% 49% 48% 51% 51% 50% 50% 52% 48% 53% 49% 50% 47% 48% 47%
Bits 16-31: 49% 47% 50% 50% 48% 47% 50% 51% 48% 49% 50% 49% 48% 47% 51% 48%
Bits 0-15:  49% 50% 50% 50% 51% 50% 50% 50% 50% 51% 47% 56% 62% 75% 50% 0%

All bits approximately 50% correlated (random/independent).

After 1 Park-Miller step:

Bits 48-63: 100% 100% 100% 100% 100% 57% 58% 48% 51% 49% 51% 53% 52% 52% 49% 49%
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^
            5 bits now 100% correlated

After 2 Park-Miller steps:

Bits 48-63: 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 52% 51% 50% 51% 52% 49%
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            10 bits now 100% correlated

After 3 Park-Miller steps:

Bits 48-63: 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 86%
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            Top 16 bits almost entirely correlated

Concrete Example

Characters 100 and 101 after 3 Park-Miller steps:

Char 100:   0xFA7129B960238F23
Char 101:   0xFA7142CE86BEA67C
              ^^^^
              Top 16 bits IDENTICAL (0xFA71)

XOR:        0x00006B77E69D295F
            30 bits differ (should be ~32 for independent)

Why Trait Selection Remains Independent

Despite the high-bit correlation, the SeedToInt function accidentally neutralizes it:

return (int)((ulSeed >> 16) % (ulong)iRange);
  1. Right shift by 16: Moves bits 16-63 into positions 0-47
  2. Correlated bits relocate: The correlated top bits (48-63) now occupy positions 32-47
  3. Modulo operation: For small ranges like 50 (archetype die), only the low ~6 bits matter
  4. Correlated bits discarded: The modulo operation effectively ignores positions 32-47

Empirical Verification

Testing 10,000 consecutive character pairs:

Die Size Same Result Rate Expected (Independent) Ratio
50 2.06% 2.00% 1.03x
100 1.04% 1.00% 1.04x
5 20.02% 20.00% 1.00x
3 32.99% 33.33% 0.99x

All results fall within expected statistical variance for independent draws.

Chi-Square Independence Test

For archetype selection (5 outcomes, 10,000 pairs):

FirstSeed Chi-Square Critical Value (p=0.05) Independent?
12345 25.72 26.30 Yes
98765432 12.89 26.30 Yes
0xDEADBEEF 19.48 26.30 Yes
1 15.50 26.30 Yes

All tests pass the independence criterion.

Courtier Trait Generation Flow

For context, here's how courtier traits are generated:

// From Character.cs
public virtual void generateRatingsCourtier(CourtierType eCourtier)
{
    // Step 1: Rating (e.g., Discipline 2-4 for Merchants)
    for (RatingType eLoopRating = 0; eLoopRating < infos().ratingsNum(); eLoopRating++)
    {
        setRating(eLoopRating,
            infos().courtier(eCourtier).maiRatingBase[eLoopRating] +
            randomNext(infos().courtier(eCourtier).maiRatingRand[eLoopRating]));
    }

    // Step 2: Archetype trait
    using (var randomMapScoped = CollectionCache.GetListScoped<(TraitType, int)>())
    {
        for (TraitType eLoopTrait = 0; eLoopTrait < infos().traitsNum(); ++eLoopTrait)
        {
            randomMapScoped.Value.Add((eLoopTrait,
                infos().courtier(eCourtier).maiArchetypeDie[eLoopTrait]));
        }
        TraitType eTrait = infos().utils().randomDieMap(randomMapScoped.Value, nextRandomSeed());
        if (eTrait != TraitType.NONE)
        {
            addTrait(eTrait);
        }
    }

    // Step 3: Adjective trait (similar pattern)
    // Step 4: doAdultTrait()
}

The randomDieMap function:

// From Utils.cs
public virtual T randomDieMap<T>(List<(T, int)> mapDice, ulong seed, T defaultValue = default(T))
{
    int iDieSize = 0;
    foreach ((T, int weight) pair in mapDice)
    {
        iDieSize += pair.weight;
    }

    if (iDieSize > 0)
    {
        RandomStruct pRandom = new RandomStruct(seed);
        int iRoll = pRandom.Next(iDieSize);

        foreach ((T val, int weight) pair in mapDice)
        {
            if (iRoll < pair.weight)
                return pair.val;
            iRoll -= pair.weight;
        }
    }
    return defaultValue;
}

Probability of Coincidental Matching

For two players both selecting Traders family, their Merchant courtiers have independent outcomes with these coincidental match probabilities:

Attribute Options Match Probability
Archetype 5 (equal weight) 20%
Adjective 10 (equal weight) 10%
Discipline Rating 3 values (2, 3, or 4) 33%
Traits only 5 × 10 2%
Full match 5 × 10 × 3 0.67%

These represent random chance, not systematic correlation.

Implications and Risk Assessment

Current Safety

The system is safe for current use cases because:

  1. Archetype dice use small total weights (50 for 5×10)
  2. Adjective dice use small total weights (100 for 10×10)
  3. The >> 16 shift and small modulo discard correlated high bits

Potential Vulnerabilities

The RNG weakness could become exploitable if:

  1. Large die sizes: If iDieSize > 65536, the modulo would preserve correlated bits
  2. High-bit extraction: Any code using seed >> 48 would see identical values for consecutive characters
  3. Direct seed comparison: Game logic comparing raw seeds would find spurious matches

Code Smell Summary

  1. Dead constant: IM = long.MaxValue is defined but never used
  2. Algorithm mismatch: 31-bit Park-Miller constants used with 64-bit arithmetic
  3. Missing underflow handling: Standard Park-Miller adds the modulus when result is negative
  4. Predictable seed relationship: Consecutive character seeds differ by one deterministic LCG step

Test Code

The following Python script reproduces these findings:

#!/usr/bin/env python3
"""Old World RNG correlation test - replicates game's Random.cs"""

MOD_64 = 2**64
IA, IQ, IR = 16807, 127773, 2836

class RandomStruct:
    def __init__(self, seed):
        self.seed = seed if seed != 0 else (2**64 - 1)

    def next_alt_seed(self):
        self.seed = (self.seed * 1103515245 + 12345) % MOD_64
        return self.seed

    def next_seed(self):
        k = self.seed // IQ
        result = IA * (self.seed - k * IQ) - IR * k
        self.seed = result % MOD_64
        return self.seed

    @staticmethod
    def seed_to_int(seed, range_):
        return ((seed >> 16) % range_) if range_ else 0

    def next(self, range_):
        return self.seed_to_int(self.next_seed(), range_) if range_ else 0

def get_seed_for_id(first_seed, char_id):
    rng = RandomStruct(first_seed)
    for _ in range(char_id + 1):
        rng.next_alt_seed()
    return rng.seed

# Test consecutive character correlation
first_seed = 12345
matches = 0
for char_id in range(10000):
    seed_a = get_seed_for_id(first_seed, char_id)
    seed_b = get_seed_for_id(first_seed, char_id + 1)

    # Simulate 3 PM steps + archetype roll
    rng_a, rng_b = RandomStruct(seed_a), RandomStruct(seed_b)
    for _ in range(3):
        rng_a.next_seed()
        rng_b.next_seed()

    arch_a = RandomStruct.seed_to_int(rng_a.seed, 50) // 10
    arch_b = RandomStruct.seed_to_int(rng_b.seed, 50) // 10
    if arch_a == arch_b:
        matches += 1

print(f"Match rate: {matches/10000:.2%} (expected: 20.00%)")

Conclusion

The Old World RNG implementation contains a flawed Park-Miller variant that causes consecutive character seeds to develop correlated high-order bits. However, the SeedToInt function's bit-shifting and modulo operations inadvertently discard these correlated bits, resulting in statistically independent trait selection.

The 20% archetype match rate and 2% full trait match rate between consecutive characters represent random chance, not exploitable correlation. Players selecting the same family will receive independently randomized courtiers.

The system works correctly by accident rather than by design. The underlying RNG weakness represents technical debt that could manifest as bugs if future code changes alter how random values are extracted from seeds.

Analysis performed: December 2024

Source files examined:

  • Reference/Source/Base/SystemCore/Random.cs
  • Reference/Source/Base/Game/GameCore/Game.cs
  • Reference/Source/Base/Game/GameCore/Character.cs
  • Reference/Source/Base/Game/GameCore/Utils.cs
  • Reference/XML/Infos/courtier.xml
  • Reference/XML/Infos/bonus.xml
Raw
rng_correlation_test
#!/usr/bin/env python3
"""
Test for correlation between consecutive character seeds in Old World RNG.
Reimplements the exact RNG algorithms from the game source:
- NextAltSeed: LCG with multiplier 1103515245, increment 12345
- NextSeed: Park-Miller variant with suspicious 64-bit/31-bit mismatch
"""
from typing import Callable
from collections import Counter
import math
# Constants from the game (Random.cs)
IA = 16807
IQ = 127773
IR = 2836
MOD_64 = 2**64
class RandomStruct:
"""Exact reimplementation of Mohawk.SystemCore.RandomStruct"""
def __init__(self, seed: int):
self.seed = seed if seed != 0 else (2**64 - 1)
def get_seed(self) -> int:
return self.seed
def set_seed(self, seed: int) -> None:
self.seed = seed if seed != 0 else (2**64 - 1)
def next_alt_seed(self) -> int:
"""LCG - used for getSeedForId"""
self.seed = (self.seed * 1103515245 + 12345) % MOD_64
return self.seed
def next_seed(self) -> int:
"""Park-Miller variant - used for Next(), NextFloat(), etc."""
k = self.seed // IQ
# This can underflow in the original - Python handles big ints differently
# We need to simulate 64-bit unsigned arithmetic
result = IA * (self.seed - k * IQ) - IR * k
# Simulate unsigned 64-bit wrap-around
self.seed = result % MOD_64
return self.seed
@staticmethod
def seed_to_int(seed: int, range_: int) -> int:
"""Convert seed to integer in [0, range)"""
if range_ == 0:
return 0
return ((seed >> 16) % range_)
def next(self, range_: int) -> int:
"""Get random int in [0, range)"""
if range_ == 0:
return 0
return self.seed_to_int(self.next_seed(), range_)
def get_seed_for_id(first_seed: int, char_id: int) -> int:
"""Reimplementation of Game.getSeedForId"""
rng = RandomStruct(first_seed)
for _ in range(char_id + 1):
rng.next_alt_seed()
return rng.get_seed()
def simulate_courtier_archetype(initial_seed: int, die_size: int = 50) -> int:
"""
Simulate the RNG path to archetype selection.
In generateRatingsCourtier:
1. randomNext(3) for rating - advances RNG via NextSeed
2. nextRandomSeed() for archetype seed - advances RNG via NextSeed
3. randomDieMap creates new RNG with that seed, calls Next(die_size)
"""
rng = RandomStruct(initial_seed)
# Step 1: Rating roll (randomNext calls Next which calls NextSeed)
rng.next(3) # Advances internal state
# Step 2: Get seed for archetype (nextRandomSeed calls NextSeed)
archetype_seed = rng.next_seed()
# Step 3: randomDieMap creates fresh RNG and calls Next
die_rng = RandomStruct(archetype_seed)
roll = die_rng.next(die_size)
return roll
def test_consecutive_correlation(first_seed: int, num_pairs: int = 10000) -> dict:
"""Test correlation between consecutive character archetype rolls."""
results = []
for char_id in range(num_pairs):
seed_a = get_seed_for_id(first_seed, char_id)
seed_b = get_seed_for_id(first_seed, char_id + 1)
roll_a = simulate_courtier_archetype(seed_a)
roll_b = simulate_courtier_archetype(seed_b)
# For 5 archetypes with weight 10 each, die_size=50
# Archetype index = roll // 10
arch_a = roll_a // 10
arch_b = roll_b // 10
results.append((arch_a, arch_b))
return analyze_correlation(results)
def analyze_correlation(pairs: list[tuple[int, int]]) -> dict:
"""Analyze correlation between paired results."""
n = len(pairs)
# Count exact matches
matches = sum(1 for a, b in pairs if a == b)
match_rate = matches / n
expected_match_rate = 1/5 # 5 archetypes, uniform
# Count each archetype for both positions
first_counts = Counter(a for a, b in pairs)
second_counts = Counter(b for a, b in pairs)
# Chi-square for independence
# Build contingency table
contingency = {}
for a, b in pairs:
contingency[(a, b)] = contingency.get((a, b), 0) + 1
# Calculate chi-square statistic
chi_sq = 0
for a in range(5):
for b in range(5):
observed = contingency.get((a, b), 0)
expected = (first_counts[a] / n) * (second_counts[b] / n) * n
if expected > 0:
chi_sq += (observed - expected) ** 2 / expected
# Degrees of freedom = (5-1) * (5-1) = 16
# Critical value at p=0.05 is ~26.3
# Critical value at p=0.01 is ~32.0
return {
'num_pairs': n,
'matches': matches,
'match_rate': match_rate,
'expected_match_rate': expected_match_rate,
'match_rate_ratio': match_rate / expected_match_rate,
'chi_square': chi_sq,
'chi_sq_critical_0.05': 26.296,
'chi_sq_critical_0.01': 32.000,
'independent': chi_sq < 26.296,
'first_distribution': dict(first_counts),
'second_distribution': dict(second_counts),
'contingency_sample': {k: v for k, v in list(contingency.items())[:10]}
}
def test_raw_seed_correlation(first_seed: int, num_pairs: int = 10000) -> dict:
"""Test if consecutive LCG seeds produce correlated Park-Miller outputs."""
correlations = []
for char_id in range(num_pairs):
seed_a = get_seed_for_id(first_seed, char_id)
seed_b = get_seed_for_id(first_seed, char_id + 1) # = LCG(seed_a)
# Apply same number of Park-Miller steps
rng_a = RandomStruct(seed_a)
rng_b = RandomStruct(seed_b)
# 3 PM steps (rating + archetype seed + die roll)
for _ in range(3):
rng_a.next_seed()
rng_b.next_seed()
# Compare final seeds
final_a = rng_a.get_seed()
final_b = rng_b.get_seed()
# Check various bit positions
correlations.append({
'xor_popcount': bin(final_a ^ final_b).count('1'),
'high_16_match': (final_a >> 48) == (final_b >> 48),
'final_a': final_a,
'final_b': final_b,
})
avg_xor_bits = sum(c['xor_popcount'] for c in correlations) / num_pairs
high_matches = sum(1 for c in correlations if c['high_16_match']) / num_pairs
return {
'avg_xor_bit_diff': avg_xor_bits,
'expected_xor_bits': 32, # For independent 64-bit values
'high_16_match_rate': high_matches,
'expected_high_16_match': 1 / 65536,
}
def main():
print("=" * 70)
print("OLD WORLD RNG CORRELATION TEST")
print("=" * 70)
# Test with a few different first seeds
test_seeds = [12345, 98765432, 0xDEADBEEF, 1]
for first_seed in test_seeds:
print(f"\n{'=' * 70}")
print(f"Testing with FirstSeed = {first_seed} (0x{first_seed:X})")
print("=" * 70)
# Test 1: Archetype correlation
print("\n[Test 1: Consecutive Character Archetype Correlation]")
result = test_consecutive_correlation(first_seed, num_pairs=10000)
print(f" Pairs tested: {result['num_pairs']}")
print(f" Exact matches: {result['matches']}")
print(f" Match rate: {result['match_rate']:.4f} (expected: {result['expected_match_rate']:.4f})")
print(f" Ratio to expected: {result['match_rate_ratio']:.4f}x")
print(f" Chi-square: {result['chi_square']:.2f} (critical @0.05: {result['chi_sq_critical_0.05']:.2f})")
print(f" Independent: {result['independent']}")
print(f" First char distribution: {result['first_distribution']}")
print(f" Second char distribution: {result['second_distribution']}")
# Test 2: Raw seed correlation
print("\n[Test 2: Raw Seed Bit Correlation After Park-Miller]")
raw_result = test_raw_seed_correlation(first_seed, num_pairs=10000)
print(f" Avg XOR bit difference: {raw_result['avg_xor_bit_diff']:.2f} (expected ~32 for independent)")
print(f" High 16-bit match rate: {raw_result['high_16_match_rate']:.6f} (expected ~{raw_result['expected_high_16_match']:.6f})")
print("\n" + "=" * 70)
print("INTERPRETATION")
print("=" * 70)
print("""
If consecutive characters were correlated:
- Match rate would be significantly higher than 20%
- Chi-square would exceed critical value (26.3)
- XOR bit difference would be significantly less than 32
If independent:
- Match rate ≈ 20% (±~1% for 10k samples)
- Chi-square < 26.3
- XOR bit difference ≈ 32
""")
if __name__ == "__main__":
main()
Raw
rng_deep_analysis
#!/usr/bin/env python3
"""
Deep analysis of WHERE the correlation exists and how it's masked.
"""
MOD_64 = 2**64
IA = 16807
IQ = 127773
IR = 2836
class RandomStruct:
def __init__(self, seed: int):
self.seed = seed if seed != 0 else (2**64 - 1)
def get_seed(self) -> int:
return self.seed
def next_alt_seed(self) -> int:
self.seed = (self.seed * 1103515245 + 12345) % MOD_64
return self.seed
def next_seed(self) -> int:
k = self.seed // IQ
result = IA * (self.seed - k * IQ) - IR * k
self.seed = result % MOD_64
return self.seed
@staticmethod
def seed_to_int(seed: int, range_: int) -> int:
if range_ == 0:
return 0
return ((seed >> 16) % range_)
def next(self, range_: int) -> int:
if range_ == 0:
return 0
return self.seed_to_int(self.next_seed(), range_)
def get_seed_for_id(first_seed: int, char_id: int) -> int:
rng = RandomStruct(first_seed)
for _ in range(char_id + 1):
rng.next_alt_seed()
return rng.get_seed()
def analyze_bit_patterns(first_seed: int, num_pairs: int = 1000):
"""Analyze which bits are correlated at each step."""
print(f"\n{'='*70}")
print(f"BIT-LEVEL CORRELATION ANALYSIS (FirstSeed={first_seed})")
print('='*70)
# Track correlation at each PM step
for pm_steps in [0, 1, 2, 3]:
bit_same_count = [0] * 64
for char_id in range(num_pairs):
seed_a = get_seed_for_id(first_seed, char_id)
seed_b = get_seed_for_id(first_seed, char_id + 1)
rng_a = RandomStruct(seed_a)
rng_b = RandomStruct(seed_b)
for _ in range(pm_steps):
rng_a.next_seed()
rng_b.next_seed()
final_a = rng_a.get_seed()
final_b = rng_b.get_seed()
# Check each bit position
for bit in range(64):
bit_a = (final_a >> bit) & 1
bit_b = (final_b >> bit) & 1
if bit_a == bit_b:
bit_same_count[bit] += 1
# Report
print(f"\nAfter {pm_steps} Park-Miller steps:")
print(" Bit positions where consecutive seeds match (% of pairs):")
print(" High bits (48-63): ", end="")
for bit in range(63, 47, -1):
pct = bit_same_count[bit] / num_pairs * 100
print(f"{pct:.0f}% ", end="")
print()
print(" Mid bits (32-47): ", end="")
for bit in range(47, 31, -1):
pct = bit_same_count[bit] / num_pairs * 100
print(f"{pct:.0f}% ", end="")
print()
print(" Mid bits (16-31): ", end="")
for bit in range(31, 15, -1):
pct = bit_same_count[bit] / num_pairs * 100
print(f"{pct:.0f}% ", end="")
print()
print(" Low bits (0-15): ", end="")
for bit in range(15, -1, -1):
pct = bit_same_count[bit] / num_pairs * 100
print(f"{pct:.0f}% ", end="")
print()
def analyze_seed_to_int_effect(first_seed: int, num_pairs: int = 10000):
"""See how SeedToInt transforms correlated seeds."""
print(f"\n{'='*70}")
print("SEED_TO_INT TRANSFORMATION ANALYSIS")
print('='*70)
for die_size in [50, 100, 5, 3]:
same_result = 0
for char_id in range(num_pairs):
seed_a = get_seed_for_id(first_seed, char_id)
seed_b = get_seed_for_id(first_seed, char_id + 1)
# Apply 3 PM steps (like courtier generation)
rng_a = RandomStruct(seed_a)
rng_b = RandomStruct(seed_b)
for _ in range(3):
rng_a.next_seed()
rng_b.next_seed()
final_a = rng_a.get_seed()
final_b = rng_b.get_seed()
# Apply SeedToInt
result_a = RandomStruct.seed_to_int(final_a, die_size)
result_b = RandomStruct.seed_to_int(final_b, die_size)
if result_a == result_b:
same_result += 1
expected = 1 / die_size
actual = same_result / num_pairs
print(f"\n Die size {die_size}:")
print(f" Same result rate: {actual:.4f} (expected for independent: {expected:.4f})")
print(f" Ratio: {actual/expected:.2f}x")
def trace_single_pair(first_seed: int, char_id: int):
"""Trace through one pair in detail."""
print(f"\n{'='*70}")
print(f"DETAILED TRACE: Characters {char_id} and {char_id+1}")
print('='*70)
seed_a = get_seed_for_id(first_seed, char_id)
seed_b = get_seed_for_id(first_seed, char_id + 1)
print(f"\nInitial seeds (from LCG):")
print(f" Char {char_id}: 0x{seed_a:016X}")
print(f" Char {char_id+1}: 0x{seed_b:016X}")
print(f" XOR: 0x{seed_a ^ seed_b:016X}")
print(f" XOR popcount: {bin(seed_a ^ seed_b).count('1')} bits differ")
rng_a = RandomStruct(seed_a)
rng_b = RandomStruct(seed_b)
for step in range(4):
rng_a.next_seed()
rng_b.next_seed()
sa = rng_a.get_seed()
sb = rng_b.get_seed()
print(f"\nAfter PM step {step+1}:")
print(f" Char {char_id}: 0x{sa:016X}")
print(f" Char {char_id+1}: 0x{sb:016X}")
print(f" XOR: 0x{sa ^ sb:016X}")
print(f" XOR popcount: {bin(sa ^ sb).count('1')} bits differ")
# Show what SeedToInt would produce
for die_size in [50, 5]:
res_a = RandomStruct.seed_to_int(sa, die_size)
res_b = RandomStruct.seed_to_int(sb, die_size)
print(f" SeedToInt({die_size}): {res_a} vs {res_b} {'(SAME)' if res_a == res_b else ''}")
def check_park_miller_behavior():
"""Check if the PM implementation behaves as expected."""
print(f"\n{'='*70}")
print("PARK-MILLER IMPLEMENTATION CHECK")
print('='*70)
# Test with values that might cause underflow
test_seeds = [
1,
IQ - 1, # 127772
IQ, # 127773
IQ + 1, # 127774
IQ * 2,
2**31 - 1, # Original PM modulus
2**32,
2**48,
2**63,
2**64 - 1,
]
for seed in test_seeds:
rng = RandomStruct(seed)
next_val = rng.next_seed()
# Check if underflow occurred (result wrapped around)
k = seed // IQ
raw_result = IA * (seed - k * IQ) - IR * k
print(f"\n Seed: {seed:>20} (0x{seed:016X})")
print(f" k = seed // IQ = {k}")
print(f" Raw result (before mod): {raw_result}")
print(f" After mod 2^64: {next_val} (0x{next_val:016X})")
if raw_result < 0:
print(f" *** UNDERFLOW OCCURRED ***")
def main():
first_seed = 12345
# Check PM behavior first
check_park_miller_behavior()
# Analyze bit patterns
analyze_bit_patterns(first_seed, num_pairs=1000)
# Analyze SeedToInt effect
analyze_seed_to_int_effect(first_seed, num_pairs=10000)
# Trace a specific pair
trace_single_pair(first_seed, char_id=100)
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment