Operação Módulo - Modulo operation

Na computação , a operação do módulo retorna o resto ou o resto com sinal de uma divisão , depois que um número é dividido por outro (chamado de módulo da operação).

Dados dois números positivos um e n , um modulo n (abreviado como um mod n ) é o resto da divisão euclidiano de um por n , em que uma é o dividendo e n é o divisor . A operação do módulo deve ser distinguida do símbolo mod , que se refere ao módulo (ou divisor) a partir do qual se está operando.

Por exemplo, a expressão "5 mod 2" seria avaliada como 1, porque 5 dividido por 2 tem um quociente de 2 e um resto de 1, enquanto "9 mod 3" seria avaliada como 0, porque a divisão de 9 por 3 tem um quociente de 3 e um restante de 0; não há nada a subtrair de 9 depois de multiplicar 3 por 3.

Embora normalmente executado com a e n sendo ambos inteiros , muitos sistemas de computação agora permitem outros tipos de operandos numéricos. O intervalo de valores para uma operação de módulo inteiro de n é 0 a n - 1 inclusive ( um mod 1 é sempre 0; um mod 0 é indefinido, possivelmente resultando em uma divisão por erro zero em algumas linguagens de programação ). Consulte Aritmética modular para uma convenção mais antiga e relacionada aplicada na teoria dos números .

Quando exatamente um de a ou n é negativo, a definição ingênua falha e as linguagens de programação diferem na forma como esses valores são definidos.

Variantes da definição

Em matemática , o resultado da operação do módulo é uma classe de equivalência e qualquer membro da classe pode ser escolhido como representante ; entretanto, o representante usual é o menor resíduo positivo , o menor inteiro não negativo que pertence àquela classe (isto é, o restante da divisão euclidiana ). No entanto, outras convenções são possíveis. Computadores e calculadoras têm várias maneiras de armazenar e representar números; portanto, sua definição da operação do módulo depende da linguagem de programação ou do hardware subjacente .

Em quase todos os sistemas de computação, o quociente q e o restante r de a dividido por n satisfazem as seguintes condições:

${\ displaystyle {\ begin {alinhado} q \, & \ in \ mathbb {Z} \\ a \, & = nq + r \\ | r | & <| n | \ end {alinhado}}}$

( 1 )

No entanto, isso ainda deixa uma ambigüidade de sinal se o resto for diferente de zero: duas escolhas possíveis para o resto ocorrem, uma negativa e outra positiva, e duas escolhas possíveis para o quociente ocorrem. Na teoria dos números, o resto positivo é sempre escolhido, mas na computação, as linguagens de programação escolhem dependendo da linguagem e dos sinais de a ou n . Pascal padrão e ALGOL 68 , por exemplo, fornecem um resto positivo (ou 0) mesmo para divisores negativos, e algumas linguagens de programação, como C90, deixam para a implementação quando n ou a é negativo (consulte a tabela em § Em linguagens de programação para detalhes). um módulo 0 é indefinido na maioria dos sistemas, embora alguns o definam como um .

Conforme descrito por Leijen,

Boute argumenta que a divisão euclidiana é superior às outras em termos de regularidade e propriedades matemáticas úteis, embora a divisão por piso, promovida por Knuth, também seja uma boa definição. Apesar de seu uso generalizado, a divisão truncada mostra-se inferior às outras definições.

-  Daan Leijen, Divisão e Módulo para Cientistas da Computação

No entanto, a divisão truncada satisfaz a identidade . ${\ displaystyle (-a) / b = - (a / b) = a / (- b)}$

Notação

Algumas calculadoras têm um botão de função mod () e muitas linguagens de programação têm uma função semelhante, expressa como mod ( a , n ) , por exemplo. Alguns também oferecem suporte a expressões que usam "%", "mod" ou "Mod" como um módulo ou operador de resto , como a % nou a mod n.

Para ambientes sem uma função semelhante, qualquer uma das três definições acima pode ser usada.

Armadilhas comuns

Quando o resultado de uma operação de módulo tem o sinal do dividendo (definição de truncamento), pode levar a erros surpreendentes.

Por exemplo, para testar se um número inteiro é ímpar , pode-se estar inclinado a testar se o resto por 2 é igual a 1:

bool is_odd(int n) {
    return n % 2 == 1;
}

Mas em uma linguagem onde o módulo tem o sinal do dividendo, isso é incorreto, porque quando n (o dividendo) é negativo e ímpar, n mod 2 retorna -1, e a função retorna falso.

Uma alternativa correta é testar se o resto não é 0 (porque o resto 0 é o mesmo, independentemente dos sinais):

bool is_odd(int n) {
    return n % 2 != 0;
}

Outra alternativa é usar o fato de que, para qualquer número ímpar, o resto pode ser 1 ou -1:

bool is_odd(int n) {
    return n % 2 == 1 || n % 2 == -1;
}

Problemas de desempenho

As operações de módulo podem ser implementadas de forma que uma divisão com um resto seja calculada a cada vez. Para casos especiais, em alguns hardwares, existem alternativas mais rápidas. Por exemplo, o módulo de potências de 2 pode ser expresso alternativamente como uma operação AND bit a bit (assumindo que x é um número inteiro positivo ou usando uma definição não truncada):

x % 2n == x & (2n - 1)

Exemplos:

x % 2 == x & 1

x % 4 == x & 3

x % 8 == x & 7

Em dispositivos e softwares que implementam operações bit a bit com mais eficiência do que o módulo, essas formas alternativas podem resultar em cálculos mais rápidos.

As otimizações do compilador podem reconhecer expressões da forma expression % constantonde constanté uma potência de dois e implementá-las automaticamente como expression & (constant-1), permitindo ao programador escrever um código mais claro sem comprometer o desempenho. Esta otimização simples não é possível para idiomas nos quais o resultado da operação do módulo tenha o sinal do dividendo (incluindo C ), a menos que o dividendo seja de um tipo inteiro sem sinal. Isso porque, se o dividendo for negativo, o módulo será negativo, expression & (constant-1)mas sempre será positivo. Para essas linguagens, a equivalência deve ser usada, expressa usando operações bit a bit OR, NOT e AND. x % 2n == x < 0 ? x | ~(2n - 1) : x & (2n - 1)

Otimizações para operações gerais de módulo constante também existem calculando a divisão primeiro usando a otimização de divisor constante .

Propriedades (identidades)

Algumas operações de módulo podem ser fatoradas ou expandidas de forma semelhante a outras operações matemáticas. Isso pode ser útil em provas de criptografia , como a troca de chaves Diffie – Hellman .

• Identidade:
  • ( a mod n ) mod n = a mod n .
  • n ^x mod n = 0 para todos os valores inteiros positivos de x .
  • Se p é um número primo que não é divisor de b , então ab ^{p −1} mod p = a mod p , devido ao pequeno teorema de Fermat .
• Inverso:
  • [(- a mod n ) + ( a mod n )] mod n = 0 .
  • b ⁻¹ mod n denota o inverso multiplicativo modular , que é definido se e somente se b e n são relativamente primos , que é o caso quando o lado esquerdo é definido: [( b ⁻¹ mod n ) ( b mod n ) ] mod n = 1 .
• Distributiva:
  • ( a + b ) mod n = [( a mod n ) + ( b mod n )] mod n .
  • ab mod n = [( a mod n ) ( b mod n )] mod n .
• Divisão (definição): uma/bmod n = [( a mod n ) ( b ⁻¹ mod n )] mod n , quando o lado direito é definido (isto é, quando b e n são coprimos ), e indefinido caso contrário.
• Multiplicação inversa: [( ab mod n ) ( b ⁻¹ mod n )] mod n = a mod n .

Em linguagens de programação

Além disso, muitos sistemas de computador fornecem uma divmodfuncionalidade que produz o quociente e o restante ao mesmo tempo. Exemplos incluem a arquitetura x86 de IDIVinstrução, da linguagem de programação C div()função, e Python 's divmod()função.

Generalizações

Módulo com deslocamento

Às vezes é útil que o resultado de um módulo n não esteja entre 0 e n - 1 , mas entre algum número d e d + n - 1 . Nesse caso, d é chamado de deslocamento. Não parece haver uma notação padrão para esta operação, portanto, vamos usar um mod _d n . Temos, portanto, a seguinte definição: x = a mod _d n apenas no caso de d ≤ x ≤ d + n - 1 e x mod n = a mod n . Claramente, a operação usual do módulo corresponde ao deslocamento de zero: a mod n = a mod ₀ n . A operação do módulo com deslocamento está relacionada à função de piso da seguinte forma:

${\ displaystyle a \ operatorname {mod} _ {d} n = an \ left \ lfloor {\ frac {ad} {n}} \ right \ rfloor.}$

(Para ver isso, vamos . Primeiro mostramos que x mod n = a mod n . Em geral, é verdade que ( a + bn ) mod n = a mod n para todos os inteiros b ; portanto, isso também é verdadeiro no caso caso em que ; mas isso significa que , que é o que queríamos provar. Resta ser mostrado que d ≤ x ≤ d + n - 1. Sejam k e r os inteiros tais que a - d = kn + r com 0 ≤ r ≤ n - 1 (ver divisão euclidiana ). Então , assim . Agora pegue 0 ≤ r ≤ n - 1 e adicione d a ambos os lados, obtendo d ≤ d + r ≤ d + n - 1. Mas nós vimos que x = d + r , então terminamos. □) ${\ textstyle x = an \ left \ lfloor {\ frac {ad} {n}} \ right \ rfloor}$${\ textstyle b = - \! \ left \ lfloor {\ frac {ad} {n}} \ right \ rfloor}$${\ textstyle x {\ bmod {n}} = \ left (an \ left \ lfloor {\ frac {ad} {n}} \ right \ rfloor \ right) \! {\ bmod {n}} = a {\ bmod {n}}}$${\ textstyle \ left \ lfloor {\ frac {ad} {n}} \ right \ rfloor = k}$${\ textstyle x = an \ left \ lfloor {\ frac {ad} {n}} \ right \ rfloor = a-nk = d + r}$

O módulo com deslocamento a mod _d n é implementado no Mathematica como Mod[a, n, d] .

Implementar outras definições de módulo usando truncamento

Apesar da elegância matemática da divisão de Knuth e da divisão euclidiana, é geralmente muito mais comum encontrar um módulo baseado em divisão truncado em linguagens de programação. Leijen fornece os seguintes algoritmos para calcular as duas divisões, dada uma divisão inteira truncada:

/* Euclidean and Floored divmod, in the style of C's ldiv() */
typedef struct {
  /* This structure is part of the C stdlib.h, but is reproduced here for clarity */
  long int quot;
  long int rem;
} ldiv_t;

/* Euclidean division */
inline ldiv_t ldivE(long numer, long denom) {
  /* The C99 and C++11 languages define both of these as truncating. */
  long q = numer / denom;
  long r = numer % denom;
  if (r < 0) {
    if (denom > 0) {
      q = q - 1;
      r = r + denom;
    } else {
      q = q + 1;
      r = r - denom;
    }
  }
  return (ldiv_t){.quot = q, .rem = r};
}

/* Floored division */
inline ldiv_t ldivF(long numer, long denom) {
  long q = numer / denom;
  long r = numer % denom;
  if ((r > 0 && denom < 0) || (r < 0 && denom > 0)) {
    q = q - 1;
    r = r + denom;
  }
  return (ldiv_t){.quot = q, .rem = r};
}

Observe que, para ambos os casos, o resto pode ser calculado independentemente do quociente, mas não vice-versa. As operações são combinadas aqui para economizar espaço na tela, pois as ramificações lógicas são as mesmas.

Veja também

• Módulo (desambiguação) e módulo (jargão) - muitos usos da palavra módulo , todos originados da introdução da aritmética modular de Carl F. Gauss em 1801.
• Módulo (matemática) , uso geral do termo em matemática
• Exponenciação modular
• Vire (unidade)

Notas

Referências

links externos

• Modulorama , animação de uma representação cíclica de tabuada (explicação em francês)