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.

$\text{Resto=Dividendo}-\text{(divisor}\times \text{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 $x\text{ mod }y$. Por exemplo $2=17\text{ mod }5$.

En aritmética modular escríbese $x\equiv r(\mathrm{mod}y)$, onde Modelo:Mvar é o residuo e lese "x é equivalente a r módulo y". Por exemplo $17\equiv 2(\mathrm{mod}5)$, 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 $\lfloor x\rfloor$, o resto pódese definir como:

$x\text{ mod }y:=x-y\lfloor \frac{x}{y}\rfloor$

Por exemplo, $4\text{ mod }5:=4-5\lfloor \frac{4}{5}\rfloor =4-5\cdot 0=4$.

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:

$x={(x_{2k-1}\cdots x_1{x}_0)}_b$ ($x$ en forma de lista de díxitos). $m={(m_{k-1}\cdots m_1,m_0)}_b$ con $m_{k-1}\ne 0$ ($m$ en forma de lista de díxitos).

$\mu =\lfloor \frac{b^{2k}}{m}\rfloor$.

Saída: $x\text{ mod }m$

---

1. $q_1\leftarrow \lfloor x/b^{k-1}\rfloor$
2. $q_2\leftarrow q_1\times \mu$
3. $q_3\leftarrow \lfloor q_2/b^{k-1}\rfloor$
4. $r_1\leftarrow x\text{ mod }{b}^{k+1}$
5. $r_2\leftarrow q_3\times m\text{ mod }{b}^{k+1}$
6. $r\leftarrow r_1-r_2$
7. Se $r<0$ entón:
   1. $r\leftarrow r+b^{k-1}$
8. Mentres $r\ge m$ faga o seguinte:
   1. $r\leftarrow r-m$
9. Devolva $r$

Véxase tamén

Bibliografía

• Modelo:Cita libro

Outras lecturas

• Modelo:Cita libro
• Modelo:Cita libro
• Modelo:Cita libro

Outros artigos

• aritmética modular.
• división longa.

Ligazóns externas

• Modelo:MathWorld