Dit artikel analyseert de methode die Windows XP gebruikt om een standaard gebruikersfoto te selecteren. De software maakt gebruik van de functie RtlRandomEx, waarbij GetTickCount() dient als initiële seed.
Er wordt gebruikgemaakt van een one-pass random selectie-algoritme, een speciaal geval van reservoir sampling (met k=1). De auteur legt uit dat deze methode superieur is aan een two-pass algoritme omdat het efficiënter is (minder aanroepen naar het bestandssysteem) en stabieler blijft wanneer de inhoud van de map tijdens het proces verandert. Om pathologische situaties te voorkomen, is er een veiligheidslimiet ingesteld waarbij de code stopt na het samplen van 100 foto's.
Welk algoritme gebruikte Windows XP om je initiële gebruikersfoto te kiezen?
Heeft iemand geprobeerd uit te zoeken welke RNG (Random Number Generator) Windows XP gebruikt om te bepalen welke profielfoto wordt gebruikt bij het eerste accountgebruik?
— Xeno (@XenoPanther) 11 december 2025
De random number generator die wordt gebruikt is RtlRandomEx, waarbij de huidige waarde van GetTickCount() als initiële seed dient.
De functie maakt gebruik van een one-pass random selectie-algoritme. Ik kan direct twee voordelen van deze beslissing bedenken. Ten eerste is het efficiënter dan het naïeve two-pass algoritme — waarbij je eerst alle items telt, vervolgens een willekeurig getal tussen 1 en n kiest en daarna nogmaals door de lijst loopt om het item op die index te vinden. Het one-pass algoritme vermindert het aantal aanroepen naar het bestandssysteem, wat de bottleneck is. Bovendien voorkomt het one-pass algoritme complicaties als het aantal bestanden in de map verandert terwijl de code wordt uitgevoerd.
Het one-pass algoritme is een speciaal geval van reservoir sampling, waarbij k gelijk is aan 1. Dit specifieke geval staat toe dat er een aangepast algoritme wordt gebruikt dat veel eenvoudiger is:
selectRandomFromIterator(iterator)
{
var count = 0;
var winner = null;
while (iterator.moveNext()) {
++count;
if (uniform_random(min: 1, max: count) == count) {
winner = iterator.current();
}
}
return winner;
}
De manier waarop dit algoritme werkt, is gebaseerd op de observatie dat in een verzameling van n items het laatste item een kans van 1/n heeft om willekeurig geselecteerd te worden. Als het niet wordt geselecteerd, moet er willekeurig worden gekozen uit de eerste n − 1 items, wat recursief kan worden opgelost.
Wanneer we deze recursie vooruitspelen, begin je met de basiscase: als je een lijst hebt van 1 item, dan is je enige keuze dat item. Als je echter een lijst hebt van n items, kies je eerst willekeurig een item uit de eerste n − 1, en schakel je daarna over naar het n-de item met een waarschijnlijkheid van 1/n.
Als laatste veiligheidscontrole stopt de code na het samplen van 100 foto's. Dit voorkomt pathologisch gedrag in het geval dat iemand een miljoen bestanden in de map Default Pictures plaatst.
Welk algoritme gebruikte Windows XP om je initiële gebruikersfoto te kiezen?
Heeft iemand geprobeerd uit te zoeken welke RNG (Random Number Generator) Windows XP gebruikt om te bepalen welke profielfoto wordt gebruikt bij het eerste accountgebruik?
— Xeno (@XenoPanther) 11 december 2025
De random number generator die wordt gebruikt is RtlRandomEx, waarbij de huidige waarde van GetTickCount() als initiële seed dient.
De functie maakt gebruik van een one-pass random selectie-algoritme. Ik kan direct twee voordelen van deze beslissing bedenken. Ten eerste is het efficiënter dan het naïeve two-pass algoritme — waarbij je eerst alle items telt, vervolgens een willekeurig getal tussen 1 en n kiest en daarna nogmaals door de lijst loopt om het item op die index te vinden. Het one-pass algoritme vermindert het aantal aanroepen naar het bestandssysteem, wat de bottleneck is. Bovendien voorkomt het one-pass algoritme complicaties als het aantal bestanden in de map verandert terwijl de code wordt uitgevoerd.
Het one-pass algoritme is een speciaal geval van reservoir sampling, waarbij k gelijk is aan 1. Dit specifieke geval staat toe dat er een aangepast algoritme wordt gebruikt dat veel eenvoudiger is:
selectRandomFromIterator(iterator)
{
var count = 0;
var winner = null;
while (iterator.moveNext()) {
++count;
if (uniform_random(min: 1, max: count) == count) {
winner = iterator.current();
}
}
return winner;
}
De manier waarop dit algoritme werkt, is gebaseerd op de observatie dat in een verzameling van n items het laatste item een kans van 1/n heeft om willekeurig geselecteerd te worden. Als het niet wordt geselecteerd, moet er willekeurig worden gekozen uit de eerste n − 1 items, wat recursief kan worden opgelost.
Wanneer we deze recursie vooruitspelen, begin je met de basiscase: als je een lijst hebt van 1 item, dan is je enige keuze dat item. Als je echter een lijst hebt van n items, kies je eerst willekeurig een item uit de eerste n − 1, en schakel je daarna over naar het n-de item met een waarschijnlijkheid van 1/n.
Als laatste veiligheidscontrole stopt de code na het samplen van 100 foto's. Dit voorkomt pathologisch gedrag in het geval dat iemand een miljoen bestanden in de map Default Pictures plaatst.
Groetjes,