
Este cálculo é muito importante nas civilizações de tradição católica, visto que três feriados
(em Portugal – noutros países até podem ser mais) dependem do dia do Domingo de Páscoa: o Carnaval
é 47 dias antes; a Sexta-feira Santa é dois dias antes; e o Corpo de Deus é 60 dias depois.

Antes de passarmos ao cálculo do dia, é preciso introduzir alguns conceitos.

#### Ciclo metónico

O ciclo metónico é um múltiplo comum entre anos solares e meses lunares, correspondente a 19 anos.
Foi observado pela primeira vez pelo astrónomo grego Meton. Na realidade, o ciclo não é exactamente
o mesmo: 19 anos solares são 6.939,602 dias e os 235 meses lunares correspondentes são 6.939,688
dias; isto é, existe um desfasamento de 0,086 dias, ou 2 horas, 3 minutos e 50 segundos (e 4
décimas, já agora).

Cada ano tem um número correspondente a este ciclo, chamado **Número Dourado**. É calculado
efectuando o resto da divisão entre o ano actual e o número 19, e somando 1 ao resultado dessa
operação (antigamente, não gostavam nem um bocadinho do zero – daí este mais um). Este ano, por
exemplo, o Número Dourado é o 15.

#### Diferença entre os anos julianos e gregorianos

A diferença entre o calendário juliano (até finais do século XVI, dependendo dos países – alguns
vieram quase até ao séc. XX) e gregoriano, ao nível da quantidade de dias, é apenas nos anos de
século não bissextos, isto é, nos anos que são divisíveis por 100, mas não por 400. O calendário
juliano tinha um ano bissexto de 4 em 4 anos, certinho. O gregoriano também, mas exclui os anos de
século, excepto se forem divisíveis por 400. Este cálculo é também chamado **Equação Solar**.

#### Diferença entre o calendário juliano e o ciclo metónico

Este cálculo é também chamado **Equação Lunar**, e calcula o número de dias de desvio do mês lunar
a partir do calendário juliano. Este número aumenta 8 vezes a cada 2500 anos.

#### Epacta

Dia do mês lunar no dia 1 de Janeiro do ano a calcular. O mês lunar decorre entre duas luas novas.
Em 2010, a Epacta foi 14, isto é, estava quase lua cheia no dia 1 de Janeiro. O cálculo da Epacta
é todo um tratado: assume-se que a lua avança 11 dias de ano para ano dentro do ciclo metónico,
e que tem de se levar em linha de conta com a Equação Solar (a subtrair) e com a Equação Lunar
(a somar).

Dois ajustes são necessários: em primeiro lugar, uma constante, 20, para acertar o dia lunar; em
segundo, duas condições de acerto, se a Epacta for 25 e o Número Dourado for maior do que 11, é
preciso acrescentar 1 à Epacta, procedendo-se de igual modo se a Epacta for 24. Como não podia
deixar de ser, estas condições destinam-se a acertar a lua com possíveis condições de
bissextalidade, no caso, dos anos precedentes.

#### Então, como calcular a data da Páscoa?

O pseudo-código seguinte baseia-se em todos os conceitos anteriores, e é o mesmo algoritmo, com
algumas correcções, apresentado por Donald E. Knuth em _The Art of Computer Programming, Vol. 1_
[Addison-Wesley, 1969]. Todas as divisões devem ser consideradas como truncagens, isto é, o resto
é descartado. O símbolo `%` representa o resto da divisão.

```clike
Seja ano = ano a calcular;

Seja NumDourado = (ano % 19) + 1;
Seja Século = (ano / 100) + 1;  // na realidade, este cálculo de século
                                // está errado, visto que o "ano de século"
                                // pertence ao século precedente, e não ao
                                // seguinte - mas é assim que é preciso
                                // para este cálculo da data da Páscoa
Seja EqSolar = ( (3 x Século) / 4) - 12;
Seja EqLunar = ( ( 8 x Século + 5) / 25) - 5;

Seja Epacta = 11 x NumDourado + EqLunar - EqSolar + 20;
Epacta = Epacta - 30 x (Epacta / 30);   // porquê, quando podia ter sido
                                        // feito com um resto da divisão?
                                        // porque, para anos muito grandes,
                                        // existe a possibilidade da Epacta
                                        // ser negativa, pelo que a
                                        // multiplicação por um número
                                        // negativo se impõe nessas condições

Se ( (Epacta = 25 E NumDourado > 11) OU (Epacta = 24) )
    Epacta = Epacta + 1;

Seja LuaCheia = 44 - Epacta;    // porquê 44? Porque é o suficiente para chegar
                                // a Março. São 30 dias para um ciclo lunar
                                // completo, mais 14 para chegar à lua cheia

Se (LuaCheia < 21) // o 21 representa o 21 de Março da data Pascal
    LuaCheia = LuaCheia + 30;

Seja CorrecçãoDomingo = ( ( 5 x Ano) / 4) - EqSolar - 10;
// mais uma vez, a diferença entre calendários a fazer das suas...

DiaPáscoa = LuaCheia + 7 - ( (CorrecçãoDomingo + LuaCheia) % 7);
// isto é, na semana subsequente à lua cheia (+7), menos o resto da própria lua
// cheia - porque o Domingo assume-se como o dia 7 da semana, dando resto 0,
// depois dos devidos acertos. No entanto, ainda é possível que este dia seja
// superior a 31, o que quer dizer que a Páscoa passou para Abril
Se (DiaPáscoa > 31)
    DiaPáscoa = DiaPáscoa - 31;
    MêsPáscoa = Abril
Senão
    MêsPáscoa = Março
```

_That's it_. Parece mais complicado do que, na realidade, é.



Aqui há dias relembraram-me o quanto eu gosto de datas. Um tipo – que eu não conheço de lado
nenhum – pediu ajuda num fórum para fazer uma função em C que calculasse o número de dias entre
duas datas; provavelmente, e tendo em consideração o pedido, para um trabalho da escola, ou coisa
que o valha. Devo dizer que fui um bocadinho totó e disponibilizei logo ali a função inteira,
quando a ideia de um fórum não é _fazer por_, mas sim _ajudar a fazer_.

Seja como for, só me decidi ajudá-lo por considerar o problema interessante; não é algo que seja
muito comum hoje em dia, até porque a maior parte das linguagens de programação tem bibliotecas
específicas para trabalhar com datas, e esta função é disponibilizada de forma directa. Além
disso, vi que as orientações que já lhe tinham dado não eram, nem de perto, nem de longe, o mais
eficaz que se podia ser.

O problema no meio disto tudo, como não podia deixar de ser, é a existência ou não de anos
bissextos no intervalo. Como Arthur C. Clarke colocou de forma hilariante em
_3001 – Odisseia Final_, “um dia, um dos menores erros de Deus será corrigido e o ano terá 12
meses de 30 dias exactamente iguais”.

Vamos recordar, como aquecimento, como se detecta se um ano é bissexto ou não.

Duma forma básica, um ano é bissexto se o resto da sua divisão por quatro for zero. E esta regra
tem-nos servido razoavelmente. No entanto, como o leitor com mais de 120 anos se recordará, 1900
não foi bissexto; é que há outra regra: um ano **não é bissexto** se o resto da sua divisão por
100 for zero. Porém, ainda agora tivemos a viragem de século, e 2000 _foi_ bissexto! Certo – ainda
falta a terceira regra: um ano **é mesmo bissexto** (e desta, é mesmo para cumprir), se o resto da
sua divisão por 400 for zero.

Resumindo e baralhando: um ano é bissexto se o resto da sua divisão por 400 for zero ou se o resto
da sua divisão por quatro for zero e, por 100, diferente de zero.

Mas vamos ao cálculo da diferença, então.

A pior sugestão que alguma vez ouvi foi a um colega, com
quem mantive uma discussão há uns anos sobre datas e programação, cuja sugestão envolvia o uso e
manutenção de um vector com todos os anos bissextos existentes.

Quando lhe fiz notar a imensidade a que se propunha, dando-lhe datas de interesse histórico, como
o ano da fundação de Portugal, atirou-me à cara, não sem razão, que era um absurdo, visto que a
bissextalidade da forma como a conhecemos hoje em dia, só foi instiuida no calendário Gregoriano,
em vigor desde 1582. Contra-argumentei com possível interesse histórico e académico na diferença
entre as datas usadas no calendário Juliano e Gregoriano e, finalmente, com os anos futuros.

Retirei-me da conversa quando a resposta dele foi “quando se chegar ao limite do que está no
vector, acrescenta-se mais umas centenas de anos bissextos”…

Outra sugestão, que era a tal que deram no fórum, seria percorrer todos os anos, desde o ano da
data mais antiga até ao ano da data mais recente, e testá-los um a um pela sua bissextalidade;
uma melhoria óbvia seria testar um a um até encontrar o primeiro e depois testar apenas de 4 em 4.

Com ou sem melhorias, esta metodologia envolverá sempre iterações, o que não abona nada em favor
da _performance_, e que fará com que intervalos maiores demorem mais tempo a ser calculados.

Qual é a solução que proponho? Calcular, de forma matemática, o número de dias correspondente a
cada data, desde 1 de Janeiro de 0 (sim, ano 0). Sem iterações, apenas operações matemáticas.
O maior problema para isso, é que o dia da bissextalidade é num mês horrível. Sério,
[Júlio César](https://pt.wikipedia.org/wiki/Calend%C3%A1rio_Juliano), em que raio estavas a
pensar? Fevereiro? Porque não no fim do ano? Esse tem de ser o nosso primeiro passo, passar o dia
problemático para o final do ano, e ajustar o ano da data para reflectir essa alteração. Então:

```clike
mesRecalculado = RestoDaDivisao((mes + 9) / 12);
// a seguinte divisão deve ser calculada com recurso a truncagem
// a parte decimal, se houver, é descartada - NÃO É um arredondamento
anoRecalculado = ano - mesRecalculado / 10;
```

Com este cálculo, Março passa a ser o primeiro mês do ano (na realidade, é o mês zero) e Fevereiro
o último. Devido à divisão inteira, quando o mês pedido é Janeiro ou Fevereiro (que assumem como
novo número, respectivamente, 10 e 11), o ano é reajustado como sendo o ano anterior. Com estes
dois cálculos, todos os possíveis dias 29 de Fevereiro estão agora no final de cada ano.

Vamos então calcular o número de dias sem olhar a bissextalidade (365 dias num ano), depois somar
1 por cada 4 anos, subtrair 1 por cada 100 anos e somar de novo 1 por cada 400 anos. A
bissextalidade está agora sob controlo.

Agora que temos os dias todos calculados em relação aos anos, vamos enfiar os meses na ordem
certa; o número de ordem do mês que calculamos anteriormente é multiplicado pelos dias de um ano,
retirando os meses de Janeiro e Fevereiro (isto é, 306 dias), a dividir por 10 (que são os meses
que ficaram à frente de Janeiro e Fevereiro, lembram-se?). Finalmente, vamos somar um dia por
cada mês de 31 dias existente no ano (são 7), e compensar para os 28 dias que Fevereiro,
normalmente, tem, visto que a bissextalidade já foi acertada lá atrás. Como este acerto de 5 dias
tem de entrar no reordenamento dos meses, tem de ser, também, dividido por 10, sendo somado ao
resultado da multiplicação prévia.

Com os meses também já fora do caminho, resta-nos somar o dia da data e pronto… Será?

O que é certo é que estas contas todas, embora aparentem estar correctas à primeira vista, têm
sempre um dia a mais do que é suposto.

Nem queiram saber o que eu passei para chegar a esta conclusão – tive que fazer uma versão mais
intuitiva do cálculo dos dias (percorrendo todos os anos para calcular a bissextalidade) e
comparar uma com a outra em milhares de datas. Mas é isso. No final, é só subtrair um dia.
Resulta sempre.

```clike
// todas as divisões são calculadas com recurso a truncagem
// a parte decimal, se houver, é descartada - NÃO É um arredondamento

mesRecalculado = RestoDaDivisao((mes + 9) / 12);
anoRecalculado = ano - mesRecalculado / 10;

// calcular sem anos bissextos
dias = 365 * anoRecalculado;

// 1ª regra da  bissextalidade
dias = dias + anoRecalculado / 4;

// 2ª regra da bissextalidade
dias = dias - anoRecalculado / 100;

// 3ª regra da bissextalidade
dias = dias + anoRecalculado / 400;

// reordenação e contabilização dos meses
// inclui acerto para os meses de 31 dias menos 2 de Fevereiro
dias = dias + (mesRecalculado * 306 + 5) / 10

// dias da data
dias = dias + dia;

// acerto final
dias = dias - 1;

// estas contas podem ser todas "encomboiadas" numa linha
// aqui estão separadas a bem da clareza
```

Para resolver o nosso problema inicial – calcular a diferença em dias entre duas datas, ainda se
lembram? – é tão simples como efectuar este cálculo para ambas e subtrair uma pela outra. Nem
sequer interessa qual é a mais antiga, desde que devolvam o valor absoluto do resultado.

Para finalizar, vamos verificar as limitações.

Em primeiro lugar, como deve ser óbvio, anos negativos vão dar valores negativos. Para o caso em
concreto, diferença entre datas, até se come, visto que vai dar correcto. Por exemplo, 1 de
Janeiro de 1 AC dará –365 dias, e 1 de Janeiro de 1 DC dará 365 dias. Logo, a mais antiga menos a
mais recente dará –730 dias. Ah, e tal, dirão, mas costuma ser ao contrário, isto é, a mais
recente menos a mais antiga – o que daria zero. Certo, mas tal como disse atrás, se devolverem o
valor em absoluto estão sempre safos, e basta controlarem qual é a mais antiga para ultrapassarem
esta limitação dos anos negativos.

Em segundo lugar, temos a limitação dos inteiros. Ao implementar isto, o mais normal é usar-se um
tipo inteiro, o que normalmente quer dizer 32 _bit_, com sinal, o que vem a dar um limite máximo
de 2.147.483.647. Mas chega e sobra. Esta função vai dar o seu último resultado válido precisamente
no dia 8 de Dezembro do ano cinco milhões, oitocentos e setenta e nove mil, seiscentos e dez. Que,
por incrível que possa parecer, **é bissexto**! E, sim, escrevi por extenso de propósito.

De qualquer forma, usem as bibliotecas disponíveis para lidarem com datas. Isto foi só uma
curiosidade, _just for fun_&hellip;



Uma forma de calcular os CSN, e vice-versa, seria simplesmente construir todo o desdobramento até
ao CSN pretendido, ou até à chave pretendida. _Don’t_. É estúpido, é um desperdício de ciclos de
processamento e é péssima programação. Sobretudo, se já alguém pensou no assunto e se os
algoritmos são do domínio público.

Vamos então aos ditos&hellip;

O algoritmo para calcular a combinação a partir do CSN é um engenhosa obra prima de
**B. P. Buckles** e **M. Lyabanon**, publicada em 1974.

```clike
função csnParaCombinacao(csn, n, k)
    seja limite_inferior = 0;
    seja r = 0;
    seja combinação = [0...k-1]

    para cada i, sendo i = 0, enquanto i < k - 1, incrementar i
        combinação[i] = 0;
        se(i != 0) combinação[i] = combinação[i - 1];

        fazer
            combinação[i] =  combinação[i] + 1;
            // lembram-se desta função?
            r = numeroDeCombinacoes(n - combinação[i], (k - 1) - i);
            limite_inferior = limite_inferior + r;
        enquanto (limite_inferior < csn);

        limite_inferior = limite_inferior - r;
    fim de para;

    combinação[k - 1] = combinação[k - 2] + csn - limite_inferior;

    devolve combinação;
fim de função;
```

Para começar, quero-vos dizer que parece bem mais complicado do que, na realidade, é.

Depois, reparem como a última posição da combinação é tratada à parte, duma maneira perfeitamente
elegante, usando os valores do CSN pedido e do último limite inferior calculado.

Mas passemos, então, à manobra inversa, calcular o CSN a partir da combinação. O seguinte algoritmo
não tem, que eu saiba, autores oficiais. A sua simplicidade decorre de ser um _negativo_ quase
perfeito da função anterior.

```clike
função combinacaoParaCsn(combinação, n)
    seja k = combinação.tamanho();
    seja limite_inferior = 0;
    seja r= 0;

    para cada i, sendo i = 1, enquanto i <= k, incrementar i
        r = n - combinação[k - i];
        se (r >= i)
            limite_inferior = limite_inferior + númeroDeCombinações(r, i);
        fim de se;
    fim de para;

    devolve numeroDeCombinacoes(n, k) - limite_inferior;
fim de função;
```

Podem ver, na segunda instrução do `para`, que a combinação está a ser percorrida de trás para a
frente, e o limite inferior está a ser contado como _o que falta até ao fim_, sendo finalmente
subtraído ao número de combinações total para nos dar o CSN.



A forma habitual de calcular combinações, que nos ensinaram na escola, é a seguinte:

$$
C_k^n = \frac{n!}{k! \times (n - k)}
$$

No entanto, calcular desta forma numa aplicação informática levanta desde logo dois problemas:

1. A maior parte das linguagens de programação não tem uma função para calcular factoriais, embora
seja muito fácil fazer uma, simplística, é certo, de forma recursiva:

```clike
função factorial(n)
  devolve (n * factorial(n - 1));
fim de função factorial
```

2. Mesmo os mais modestos factoriais atingem rapidamente o limite dos tipos inteiros. Por exemplo,
usando `Int32`, o limite é 2.147.483.647, ou 4.294.967.295 (sem sinal); o reles $13!$ já rebenta
com qualquer um deles. OK, podíamos usar inteiros de 64 _bits_, afinal, quase todos os
processadores actuais são de 64 _bits_ (mas o sistema operativo também tem que ser, não se
esqueçam); ficávamos com limites de 9.223.372.036.854.780.000 ou 18.446.744.073.709.600.000 (sem
sinal). Pois, mas basta um $21!$ para ficarmos logo sem pé outra vez.

Posto isto, que fazer?

Desmontando a fórmula das combinações, poderíamos chegar a uma fórmula recursiva, e respectivo
algoritmo:

$$
\begin{aligned}
C_k^n = [(n - 0) / (k - 0)]
\newline
\times [(n - 1) / (k - 1)]
\newline
\times \dots
\newline
\times ([n - (k - 1)] / [k - (k - 1)])
\end{aligned}
$$

```clike
função numeroDeCombinacoes(n, k, dif)
  se (dif = k - 1) então:
    devolve ((n - dif) / (k - dif));
  senão:
    devolve (((n - dif) / (k - dif)) * numeroDeCombinacoes(n, k, dif - 1));
fim de função numeroDeCombinacoes
```

As funções recursivas, porém, não são lá muito amigas da performance… mesmo com _tail optimization_
(que este exemplo nem tem). Para alguns factoriais mais _musculados_, esta função cedo ia
arrastar-se nos cálculos.

O algoritmo que vou apresentar de seguida foi publicado em 1963 (não, não é gralha, é mesmo
seis-três) por **M. L. Wolfson** e **H. V. Wright**.

```clike
função numeroDeCombinacoes(n, k)
  seja dif = n - k;

  se (k < dif) então:
    seja dif = k;
    seja k = n - dif;

  seja combinações = k + 1;

  se (dif = 0) então:
    seja combinações = 1;
  senão: se (dif >= 2) então:
    para (i = 2; i <= dif; i = i + 1)
      seja combinações = (combinações * (k + i)) / i;
    fim de para;

  devolve combinações;
fim de função numeroDeCombinacoes
```

Reparem como ainda podemos reconhecer a fórmula explicada acima neste formato não recursivo.
É maravilhosamente elegante e (ainda) é o algoritmo mais rápido para se calcular o número de
combinações.
