Blogia
petalofucsia

MATEMÁTICAS2: RESTO. En aritmética, el resto o residuo de una división de dos números enteros es el número que se le ha de restar al dividendo para que sea igual a un determinado número de veces el divisor . Equivalentemente, es el número resultante de la diferencia del dividendo con el producto del divisor por el cociente.

Resto

De Wikipedia, la enciclopedia libre

En aritmética, el resto o residuo de una división de dos números enteros es el número que se le ha de restar al dividendo para que sea igual a un determinado número de veces el divisor . Equivalentemente, es el número resultante de la diferencia del dividendo con el producto del divisor por el cociente. O sea:

mbox{Resto=Dividendo} - mbox{(divisor}times mbox{cociente)}

Según su resto, las divisiones se clasifican como exactas si su resto es cero ó inexactas cuando no lo es.

Generalmente, al resto de dividir x entre y se suele expresar como textstyle x mbox{ mod }y.

En la práctica, el resto de una división puede calcularse usando ecuaciones, en términos de otras funciones. En términos de la función parte entera lfloor xrfloor, el resto se puede definir como:

x mbox{ mod } y := x-yleftlfloor frac x yrightrfloor

La expresión x mod 0 queda sin definir en la mayoría de los sistemas numéricos, aunque algunos la definen como igual a x.

[editar] Implementación para el cálculo del resto

Para números pequeños se suele implementar la función de arriba, que es muy sencilla. Para la implementación con números grandes, existen métodos mucho más eficientes, como el algoritmo de reducción de Montgomery y la reducción de Barrett. La reducción de Barrett toma el hecho de que existen números q y r de manera que x = mq+r y 0 ≤ r < m (véase Algoritmo de la división), y lo utiliza para estimar q utilizando sólo operaciones de recorrimiento en lugar de divisiones.

Algoritmo Reducción de Barrett

Entradas:

x=left(x_{2k-1}cdots x_1x_0right)_b (x en forma de lista de dígitos)m=left(m_{k-1}cdots m_1,m_0right)_b con m_{k-1}neq0 (m en forma de lista de dígitos)mu=leftlfloorfrac{b^{2k}}{m}rightrfloor

Salida: x mbox{ mod } y ,


  1. q_1getsleftlfloor x/b^{k-1}rightrfloor
  2. q_2gets q_1timesmu
  3. q_3getsleftlfloor q_2/b^{k-1}rightlfloor
  4. r_1gets x mbox{ mod } b^{k+1}
  5. r_2gets q_3times m mbox{ mod } b^{k+1}
  6. rgets r_1-r_2
  7. Si r<0, entonces:
    1. rgets r+b^{k-1}
  8. Mientras rgeq m haga lo siguiente:
    1. rgets r-m
  9. Devuelva r

[editar] Véase también

¿Y esta publicidad? Puedes eliminarla si quieres
¿Y esta publicidad? Puedes eliminarla si quieres

0 comentarios

¿Y esta publicidad? Puedes eliminarla si quieres