Resto

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