Restant

Archiu:Integer division with remainder.jpg

Algoritme de divisió. Dalt s'observa el cocient (2) i el restant (3) de dividir 11÷ 4

En aritmètica el restant o residu d'una divisió de dos número entero és el número que se li ha de restar al divident per a que siga igual a un determinat número de voltes el divisor. Equivalentemente, és el número resultant de la diferència del divident en el producte del divisor pel cocient. O siga:

$\text{Resto=Dividendo}-\text{(divisor}\times \text{cociente)}$

Segons el seu restant les divisions es classifiquen com a exactes, si el seu restant és zero, o sanceres, quan no ho és.

Generalment el restant de dividir x entre i se sol expressar com $x\text{ mod }y$.

En la pràctica, el restant d'una divisió pot calcular-se usant equacions, en térmens d'atres funcions. En térmens de la funció partix sancera $\lfloor x\rfloor$, el restant es pot definir com:

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

L'expressió x mod 0 queda sense definir en la majoria dels sistemes numèrics, encara que alguns la definixen com a igual a x.

Per eixemple, 4 / 5 = 0.8, si es pren la part inexacta el restant d'esta divisió seria zero. Pero en térmens de la funció sancera 4 mod 5 seria 4, ya que restant = 4 - 5 * 0 = 4, és dir el restant és 4.

Implementació per al càlcul del restant

Per a números menuts se sol implementar la funció indicada anteriorment, que és molt senzilla. Per a l'implementació en números grans, existixen métodos molt més eficients, com l'algoritme de reducció de Montgomery i la reducció de Barrett. La reducció de Barrett pren el fet de que existixen números q i r, de manera que x = mq+r i 0 ≤ r < m (vore Algoritme de la divisió), i ho utilisa per a estimar q utilisant només operacions de recorrimiento en lloc de divisions.

Vore també

• producte
• divisió
• Divisores
• Aritmètica modular
• Algoritme de Euclides