Ver o código fonte de «Resto»

En [[aritmética]] o resto ou '''residuo''' dunha [[División (matemáticas)|división]] de dous [[Número enteiro|números enteiros]] é o número que se lle debe '''restar''' ao [[División (matemáticas)|dividendo]] para que sexa igual a un determinado número de veces o [[divisor]].<ref>{{harvnb|Ore|1988|loc=p. 32}}</ref> Equivalentemente, é o número resultante da diferenza do dividendo co [[Multiplicación|produto]] do divisor polo [[División (matemáticas)|cociente]]. <center> <math>\mbox{Resto=Dividendo} - \mbox{(divisor}\times \mbox{cociente)}</math> </center>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 <math>\textstyle x \mbox{ mod }y</math>. Por exemplo <math>\textstyle 2 = 17 \mbox{ mod }5</math>.

En [[aritmética modular]] escríbese <math>x  \equiv  r  \pmod y</math>, onde {{Mvar|x}} é o residuo e lese "x é equivalente a r módulo y". Por exemplo <math>17 \equiv 2 \pmod 5</math>, 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óns chan e teito|función chan]] <math>\lfloor x\rfloor</math>, o resto pódese definir como:

: <math>x \mbox{ mod } y := x-y\left\lfloor \frac x y\right\rfloor</math>
Por exemplo, <math>4 \mbox{ mod } 5 := 4-5\left\lfloor \frac 4 5\right\rfloor = 4 - 5 \cdot 0 = 4</math>.

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 Ba''r''rett aproveita o feito de que e''x''isten números ''q'' e r, de maneira que x = mq+r e 0 ≤ r < m (véxase [[División euclidiana|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:'''

<math>x=\left(x_{2k-1}\cdots x_1x_0\right)_b</math> (<math>x</math> en forma de lista de díxitos).
<math>m=\left(m_{k-1}\cdots m_1,m_0\right)_b</math> con <math>m_{k-1}\neq0</math> (<math>m</math> en forma de lista de díxitos).

<math>\mu=\left\lfloor\frac{b^{2k}}{m}\right\rfloor</math>.

'''Saída: '''<math>x \mbox{ mod } m \,</math>
----
#<math>q_1\gets\left\lfloor x/b^{k-1}\right\rfloor</math>
#<math>q_2\gets q_1\times\mu</math>
#<math>q_3\gets\left\lfloor q_2/b^{k-1}\right\rfloor</math>
#<math>r_1\gets x \mbox{ mod } b^{k+1}</math>
#<math>r_2\gets q_3\times m \mbox{ mod } b^{k+1}</math>
#<math>r\gets r_1-r_2</math>
#'''Se''' <math>r<0\,</math> '''entón:'''
##<math>r\gets r+b^{k-1}</math>
#'''Mentres''' <math>r\geq m</math> '''faga o seguinte:'''
##<math>r\gets r-m</math>
#'''Devolva''' <math>r</math>

== Notas ==
{{reflist|30em}} 
== Véxase tamén ==
{{Commonscat}} 
=== Bibliografía ===
* {{cita libro|first=Oystein|last=Ore|year=1988|orig-year=1948|title=Number Theory and Its History|publisher=Dover|isbn=978-0-486-65620-5|url=https://archive.org/details/numbertheoryitsh0000orey}}
=== Outras lecturas ===
* {{cita libro |author=Davenport, Harold |title=The higher arithmetic: an introduction to the theory of numbers |publisher=Cambridge University Press |location=Cambridge, UK |year=1999 |page=25 |isbn=0-521-63446-6}}
* {{cita libro|editor-last=Katz|editor-first=Victor|title=The mathematics of Egypt, Mesopotamia, China, India, and Islam : a sourcebook|url=https://archive.org/details/mathematicsofegy0000unse|year=2007|publisher=Princeton University Press|location=Princeton|isbn=9780691114859}}
* {{cita libro |author=Zuckerman, Martin M |title=Arithmetic: A Straightforward Approach |date=December 1998 |publisher=Rowman & Littlefield Publishers, Inc |location=Lanham, Md |isbn=0-912675-07-1}}
=== Outros artigos ===
* [[aritmética modular]].
* [[División (matemáticas)#Algoritmo da división. Exemplo|división longa]].

=== Ligazóns externas ===
*{{MathWorld|Remainder|Remainder}}

{{control de autoridades}}
[[Categoría:Aritmética]]
[[Categoría:Teoría de números]]