Saltar ao contido

Resto

Na Galipedia, a Wikipedia en galego.

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.[1] 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 x é 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

[editar | editar a fonte]

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:


  1. Se entón:
  2. Mentres faga o seguinte:
  3. Devolva
  1. Ore 1988, p. 32

Véxase tamén

[editar | editar a fonte]

Bibliografía

[editar | editar a fonte]

Outras lecturas

[editar | editar a fonte]

Outros artigos

[editar | editar a fonte]

Ligazóns externas

[editar | editar a fonte]