En aritmética o resto ou residuo dunha división de dous números enteiros é o número que se lle debe restar ao dividendo para que sexa igual a un determinado número de veces o divisor. Equivalentemente, é o número resultante da diferenza do dividendo co produto do divisor polo cociente. Segundo o seu resto as divisións clasifícanse como exactas, se o seu resto é cero, ou enteiras, cando non o é.
Xeralmente o resto de dividir x entre y adóitase expresar como . Por exemplo .
En aritmética modular escríbese , onde é o residuo e lese "x é equivalente a r módulo y". Por exemplo , temos que 17 é equivalente a 2 módulo 5, quere dicir, que se dividimos 17 entre 5 temos 2 como residuo.
En termos da función chan , o resto pódese definir como:
Por exemplo, .
A expresión x mod 0 fica sen definir na maioría dos sistemas numéricos, aínda que algúns a definen como igual a x.
Implementación para o cálculo do resto Para números pequenos adóitase implementar a función indicada anteriormente, que é moi sinxela. Para a implementación con números grandes, existen métodos moito máis eficientes, como o algoritmo de redución de Montgomery e a redución de Barrett. A redución de Barrett aproveita o feito de que existen números q e r, de maneira que x = mq+r e 0 ≤ r < m (véxase Algoritmo da división), e utilízao para estimar q usando só operacións de percorrido en lugar de divisións.
Redución de Barrett:
Entradas:
( en forma de lista de díxitos). con ( en forma de lista de díxitos).
.
Saída:
Se entón:
Mentres faga o seguinte:
Devolva
Notas
Véxase tamén
Bibliografía
Outras lecturas
Outros artigos aritmética modular. división longa.
Ligazóns externas
Categoría:Aritmética Categoría:Teoría de números