Introdução
Acabaste de sair da faculdade e estás a dar uma grande festa para celebrar com amigos e família.
Apareceram mais de 70 pessoas, incluindo o teu tio Ted, um pouco excêntrico.
Numa das suas habituais brincadeiras, aposta contigo 100 £ que pelo menos duas pessoas na sala fazem anos no mesmo dia.
Isso parece ridículo: há muitos mais aniversários possíveis do que convidados, por isso aceitas com confiança.
Para teu espanto, depois de recolheres as datas de aniversário de apenas 32 convidados, já encontraste dois convidados que fazem anos no mesmo dia.
Aceitas a derrota e entregas as 100 £ ao tio Ted, mas algo não bate certo.
No dia seguinte, a curiosidade leva a melhor.
Uma rápida pesquisa na Internet leva-te ao paradoxo do aniversário, que revela que, com apenas 23 pessoas, a probabilidade de dois aniversários coincidirem ultrapassa os 50%.
Ah. Então era por isso que o tio Ted estava tão confiante.
Decidido a virar o jogo, começas a procurar outros paradoxos; da próxima vez, tu é que fazes as apostas.
O paradoxo do aniversário é um paradoxo verídico: embora pareça errado, é verdadeiro.
Instruções
A tua tarefa é estimar as probabilidades do paradoxo do aniversário.
Para isso, tens de:
- Gerar datas de nascimento aleatórias.
- Verificar se uma coleção de datas de nascimento geradas aleatoriamente contém pelo menos duas com o mesmo aniversário.
- Estimar a probabilidade de pelo menos duas pessoas num grupo partilharem o mesmo aniversário, para diferentes dimensões de grupo.
Uma data de nascimento inclui a data completa de nascimento (ano, mês e dia), enquanto um aniversário se refere apenas ao mês e ao dia, que se repetem todos os anos.
Duas datas de nascimento com o mesmo mês e dia correspondem ao mesmo aniversário.
O paradoxo do aniversário parte do princípio de que:
- Há 365 aniversários possíveis (sem anos bissextos).
- Todos os aniversários são igualmente prováveis (distribuição uniforme).
A tua implementação tem de respeitar estes pressupostos.
Notas específicas do Assembly x86-64
A função random_birthdates() deve produzir datas com as seguintes propriedades:
- O ano deve ser válido.
Um ano válido
y não é bissexto e cumpre 1600 <= y < 2129.
- O ano está uniformemente distribuído por todo o intervalo de valores válidos.
- O aniversário está uniformemente distribuído pelos 365 dias do ano, de modo que cada dia do calendário tem a mesma probabilidade.
Repara que isto significa que os meses não têm todos a mesma probabilidade: um mês de 31 dias é mais provável do que um mês de 30 dias, e ambos são mais prováveis do que fevereiro.
Tanto a distribuição do ano como a do aniversário são verificadas por um teste do qui-quadrado, ao nível de p < 0,0001.
Isto significa que, se as datas estiverem a ser geradas de acordo com as instruções, há menos de 0,01% de hipóteses de produzir uma distribuição de valores que falhe o teste.
