A grande utilidade do operador % (Módulo)
Na maioria das linguagens de programação, temos o operador módulo, que normalmente é representado pelo símbolo de "%". De início muitos tem estranhesa com esse operador, já que não é tão claro para que serve apenas pelo nome (diferente dos operadores de divisão, multiplicação, potenciação e etc.), eu mesmo não fazia ideia do porquê estavam me ensinando isso quando comecei a aprender a programar.
Normalmente o seu uso acaba se limitando a testar se um número é par, denotar o intervalo em que números aleatórios vão estar e etc. Mas a sua utilidade é muito maior do que isso, já adianto que, dentre as suas utilidades, uma das que se destaca é o fato de a operação conseguir gerar conjuntos enumeráveis de números naturais a partir de qualquer conjunto numérico enumerável ou não.
Mas afinal, o que seria o módulo?
Resto da divisão
De forma simples e rápida Módulo é o resto da divisão. Isso tem a ver com o algorítimo da divisão e é um concento bem simples.
Pense que você comprou uma pizza de 16 fatias e deseja distribuir as fatias igualmente entre 3 amigos. Naturalmente nós sabemos que 16 não tem uma divisão inteira por 3, mas 15 tem. Assim, você pode separar uma das fatias e terá agora 15 fatias para distribuir igualmente entre 3 pessoas, cada uma recebendo 5 fatias da pizza. Mas e a 16º fatia? Esse é o resto.
Na matemática temos uma propriedade muito importante chamada reversibilidade em algumas funções e operações, esse conceito é mais conhecido popularmente por nós como prova real, onde aplicando uma função ou operação inversa em um número que passou pela transformação por meio de uma função ou operação ela nos retorna o número original.
Mas que p*** é essa?
Pense que você executou a operação de somar um número n por 1: n + 1.
Tomemos n como sendo 2: 2 + 1 = 3. Pela propriedade da reversabilidade, ao fazermos a operação inversa (subtrair 1 de um número n) devemos ter o mesmo n de antes. Assim: 3 - 1 = 2. E isso é a propriedade da reversabilidade.
O grande ponto é que a divisão possui essa propriedade, onde podemos incorporar também o resto da divisão. É basicamente isso: Dividendo = Quociente * Divisor + Resto.
Lembrando:
- Dividendo: número que será dividido
- Divisor: número que divide
- Quociente: resultado da divisão
- Resto: resto da divisão
Em termos de números: 5 = 2*2 + 1
Desse conceito vêm alguns teoremas importantes na matemática como o teorema do resto no estudo de polinômios e a congruência de módulo m.
Por que módulo?
Dentro do campo da Álgebra estudamos a relação entre números, variáveis, funções e conjuntos. Uma das relações mais conhecidas é a de congruência, que pode aparecer de várias maneiras. Congruência de Módulo m é uma das primeiras que aprendemos em todo curso de matemática, que basicamente significa que, caso dois números sejam congruentes em relação a um módulo m eles tem o mesmo resto de divisão. Por exemplo:
3 = 5 módulo(2) [Leia "=" como "conguente a"].
Isso pois o resto da divisão de 3 e 5 por 2 é o mesmo (1). Daí vem também o nome módulo para essa operação, que calcula o resto da divisão de um número por outro. Isso em alguns casos pode ser bem importante, por exemplo: Qual é o último algarismo do número 7²³³? Esse problema nós resolvemos com congruência de módulo m, afinal, quem em sã consciência calcularia essa expressão?
É claro que na computação poderíamos fazer essa conta, mas perderiamos muita performance utilizando uma solução analógica ao invés de analítica.
Onde se aplica?
Aqui vem o motivo da qual eu escrevi esse post. Eu sou estudante de Matemática Aplicada Computacional na UFRGS, mas também estudo programação e pretendo iniciar uma carreira como desenvolvedor. O que acontece é que a base matemática que tenho faz com que eu possa resolver vários problemas de forma mais analítica, o que em alguns casos torna o meu programa mais legível, performático ou menos complexo. Essa é a grande importância da matemática para a programação que muitos deixam para traz.
Ontem, estudando sobre estruturas de dados fiz uma implementação de uma CircleLinkedList, que é uma lista ligada onde o último nó se liga com o primeiro, fazendo com que não existam referências nulas e seja possível fazer uma busca por absolutamente qualquer índice na lista.
Um exemplo de implementação em C:
Tipos utilizados:
typedef struct node {
int value;
struct node *next;
} Node;
typedef struct circleLinkedList {
node *head;
node *tail;
} CircleLinkedList;
Precisamos de duas funções: add e getNode:
void add(int value, CircleLinkedList* list) {
Node *newNode = malloc(sizeof(Node));
newNode->value = value;
newNode->next = NULL;
if(list->length == 0) {
list->head = newNode;
list->tail = newNode;
} else {
newNode->next = list->head;
list->tail->next = newNode;
list->tail = newNode;
}
list->length++;
}
Essa função apenas adiciona um novo nó no final da lista. Agora o principal: a função getNode. Como princípio básico da estrutura, temos que o último elemento aponta para o primeiro, implicando que podemos encontrar qualquer elemento da lista com um índice inteiro positivo, independente do número. Isso significa que não importa o tamanho da lista, qualquer índice positivo é válido.
Node getNode(int index, CircleLinkedList *list) {
int i;
Node *current = list->head;
for(i = 0; i < index; i++)
current = current->next;
return *current;
}
Pronto! Temos a nossa função pronta e exercício resolvido! Óbvio que não né, olha para essa função, se eu colocar um índice 1 milhão, a função irá iterar 1 milhão de vezes mesmo que a lista tenha apenas dois elementos. Essa implementação faz com que a nossa função getNode precise sempre iterar o número total do índice, independentemente do tamanho da lista. Listas ligadas no geral possuem complexidade O(x) para buscas, o que significa, basicamente, que na pior das hipóteses, teremos que percorrer toda a nossa lista para encontrar um elemento. O que acontece é, que na forma atual da função getNode a nossa complexidade pode ser aumentada. Veja a seguinte situação:
int main() {
CircleLinkedList mylist = {NULL, NULL, 0};
Node result;
add(0, &mylist);
add(1, &mylist);
add(2, &mylist);
result = getNode(6, &mylist);
printf("getNode(6) = %d\n", result.value); // getnode(6) = 0
}
Nesse caso a complexidade do nosso algoritmo foi O(x²), pois iteramos sobre a lista duas vezes. Isso significa que, a complexidade do algoritmo aumenta proporcionalmente com o quão menor é o tamanho da lista em relação ao índice. Isso é péssimo para o desempenho da nossa função, pois para índices muito grandes teremos uma perda desnecessária em listas pequenas.
Como resolvemos isso? Utilizando o operador módulo!. Como o módulo é o resto da divisão, ao dividirmos um número temos um número limitado de valores possíveis, no caso de 3 são apenas 0, 1 e 2, pode testar aí :). Vamos imaginar que a nossa lista é uma array, ela seria assim: {0, 1, 2} e se fizéssimos mylist[0] = 0, mylist[1] = 1 e mylist[2] = 2, caso fosse uma array índices maiores causariam erros. Ótimo! Já sabemos quais índices realmente importam e são exatamente os retornos possíveis de index % 3. De forma mais resumida, os índices que realmente importam são aqueles que vão de 0 até mylist.index, implementando isso:
Node getNode(int index, CircleLinkedList *list) {
int i, finalIndex = index % list->length;
Node *current = list->head;
for(i = 0; i < finalIndex; i++)
current = current->next;
return *current;
}
Pronto! Agora se fizermos getNode(10000000000, &mylist) a função irá iterar no máximo 3 vezes, sem perda de performance significativa como anteriormente. O principal uso do operador módulo se dá quando queremos limitar um certo intervalo positivo de números, com ele podemos garantir que todos os valores estarão nesse intervalo.
Conclusão
Quando tiver um problema parecido lembre-se dessa poderosa ferramenta que praticamente todas as linguagens de programação têm e também que soluções analíticas são muito melhores e performáticas quando precisamos de escalabilidade, soluções analógicas, embora simples e equiparáveis em problemas pequenos, costumam causar problemas conforme as nossas necessidades aumentam.
