Algoritme de divisió

Un algoritme de divisió és un procediment que, daus dos número entero N i D (respectivament el numerador i el denominador), calcula el seu cocient i/o restant, el resultat de la divisió euclídea. Alguns d'estos procediments estan ideats per a realisar el càlcul manualment, mentres que uns atres formen part de programes d'ordenador o estan incorporats al disseny de circuits digitals.

Els algoritmes de divisió es classifiquen en dos categories principals: divisió llenta i divisió ràpida. Els algoritmes de divisió llenta produïxen un dígit del cocient final per iteración. Eixemples de divisió llenta inclouen la restauració, la restauració improductiva, la no restauració i la divisió SRT. Els métodos de divisió ràpida comencen en una aproximació propenca al cocient final i produïxen el doble de dígits del cocient final en cada iteración.^[1] Els algoritmes de Newton–Raphson i de Goldschmidt entren en esta categoria.

Les variants d'estos algoritmes permeten utilisar algoritmes de multiplicació ràpits. Resulta que, per a número entero grans, el temps de computació necessari per a una divisió és el mateix, fins a un factor constant, que el temps necessari per a una multiplicació, qualsevol que siga l'algoritme de multiplicació utilisat.

La discussió es referirà a la fòrmula $N / D = (Q, R)$ , a on

N = numerador (divident)
D = denominador (divisor)

són l'entrada, i

Q = cocient
R = restant

són el resultat.

Divisió per resta repetida

L'algoritme de divisió més simple, històricament incorporat en un algoritme per a obtindre el màxim comú divisor presentat en els Elements de Euclides, Llibre VII, Proposició 1, troba el restant donats dos número entero positius usant solament restes i comparacions:

function dividix_unsigned(N, D)
    if D= 0 then error(DivisionByZero) end
    R := N
    Q := 0
    while R ≥ D do
        R := R − D
        Q := Q + 1
    end
    return (Q, R)
end

La prova de que el cocient i el restant existixen i són únics (descrita en la divisió euclídea) dona lloc a un algoritme de divisió complet, aplicable tant a números negatius com a positius, que utilisa sumes, restes i comparacions:

function dividix(N, D)
  if D= 0 then error(DivisionByZero) end
  if D < 0 then 
    (Q, R) := dividix(N, −D)
     return (−Q, R) 
  end
  if N < 0 then
    (Q, R) := dividix(−N, D)
    if R= 0 then 
        return (−Q, 0)
    else
        -- Eixemple: N= -7, D= 3
        -- dividix(-N, D)= dividix(7, 3)= (2, 1)
        -- R ≠ 0, baix return (-2 - 1, 3 - 1)= (-3, 2)
        -- Check: (-3)*3 + 2= -7
        return (−Q − 1, D − R) 
    end
  end
  -- En este punt, N ≥ 0 i D > 0
  return dividix_unsigned(N, D)
end

Este procediment sempre produïx R ≥ 0. Encara que és molt simple, requerix Ω(Q) passos, per lo que és exponencialment més llent que inclús els algoritmes de divisió llenta com la divisió llarga. És útil si se sap que Q és chicotet (sent un algoritme sensible al resultat) i pot servir com a especificació eixecutable.

Implementació alternativa

Una implementació alternativa incrementa un restant i ho restablix quan alcança el divisor.

Per a $x, y \in ℕ_{0}$ , l'algoritme calcula $q, r$ de modo que $x = q y + r$ , en $0 \leq r < y$ :

div (x, y) = ⌊ x / y ⌋

x mod y = x - y ⌊ x / y ⌋

Considere's este còdic en Python:

def dividix_unsigned2(numerator: int, denominator: int) -> tuple[int, int]
    quotient: int= 0
    remainder: int= 0
    for _ in range(numerator):
        remainder += 1
        if remainder== denominator:
            quotient += 1
            remainder= 0
    return quotient, remainder

Notes

Casos especials:

x mod 1 = 0

i
,

x mod 0 = x

,^[2]

La variable quotient mai es llig. Per lo tant, quan les seues assignació (resaltades) s'eliminen del còdic i quotient s'elimina de la llista d'eixida, dividix_unsigned2, de la mateixa manera que dividix_unsigned, seguirà calculant $x mod y$ .

Implementació alternativa com a màquina de contadors
Una implementació alternativa simple com màquina de contadors (CM) pot basar-se en esta implementació alternativa. Les instruccions de la màquina de contadors són:

Z (n): Reemplaça r_n per 0.
S (n): Suma 1 a r_n.

J (m, n, q): Si r_m = r_n, bota a l'instrucció q; de lo contrari, continua en la següent instrucció del programa.

El programa de la màquina de contadors és ^[3] i

1: J(1,5,0)
2: S(4)
3: J(4,2,6)
4: S(5)
5: J(0,0,1)
6: S(3)
7: Z(4)
8: S(5)
9: J(0,0,1)

.

En acabant de que la màquina de contadors finalisa el càlcul en els valors inicials dels registres R1=N i R2=D (els registres restants són 0),

el registre R3 conté el cocient (part sancera) de la divisió N/D, i

el registre R4 conté el restant.

Divisió llarga

Artícul principal → Divisió llarga.

La divisió llarga és l'algoritme estàndar per a dividir números de vàries sifres expressats en notació decimal, utilisant llapis i paper. Es desplaça gradualment des de l'extrem esquerre al dret del divident, restant el major múltiple possible del divisor (a nivell de dígit) en cada pas; estos múltiples es convertixen en els dígits del cocient, i la diferència final és el restant.

Quan s'utilisa en una base binaria, este método constituïx la base de l'algoritme de divisió sancera (sense signe) en restant que es mostra a continuació. La divisió curta és una forma abreviada de la divisió llarga, adequada per a divisores d'una sifra. La divisió en blocs, també coneguda com a método de cocients parcials o método de l'aforcat, és una forma menys eficient de divisió llarga que pot resultar més fàcil de comprendre. En permetre restar més múltiples dels que es tenen actualment en cada etapa, també es pot desenrollar una variant més lliure de la divisió llarga.

Divisió sancera (sense signe) en restant

Vore també: Número binario

El següent algoritme, la versió binaria del conegut método de la divisió llarga, dividirà N entre D, colocant el cocient en Q i el restant en R. En el següent pseudocódigo, tots els valors es tracten com a sancers sense signe.

if D= 0 then error(DivisionByZeroException) end
Q := 0                  -- Inicializa el cocient i el restant a zero.
R := 0                     
for i := n - 1 .. 0 do  -- A on n és el número de bits en N.
  R := R << 1           -- Desplaça R a l'esquerra un bit.
  R(0) := N(i)          -- Establix el bit menys significatiu de R igual al bit i del numerador.
  if R ≥ D then
    R := R − D
    Q(i) := 1
  end
end

Eixemple

Si es prenen N=1100₂ (12₁₀) i D=100₂ (4₁₀)

Pas 1: Establir R=0 i Q=0
Pas 2: Prendre i=3 (un menys que el número de bits en N)
Pas 3: R=00 (desplaçat a l'esquerra en 1)
Pas 4: R=01 (establir R(0) a N(i))
Pas 5: R < D, per lo que s'omet l'instrucció

Pas 2: Establir i=2
Pas 3: R=010
Pas 4: R=011
Pas 5: R < D, instrucció omesa

Pas 2: Establir i=1
Pas 3: R=0110
Pas 4: R=0110
Pas 5: R>=D, instrucció ingressada
Passe 5b: R=10 (R-D)
Passe 5c: Q=10 (establir Q(i) a 1)

Pas 2: Establir i=0
Pas 3: R=100
Pas 4: R=100
Pas 5: R>=D, instrucció ingressada

Passe 5b: R=0 (R-D)
Passe 5c: Q=11 (establint Q(i) en 1)

fi
Q=11₂ (3₁₀) i R=0.

Vore també

Referències

↑ «Software Integer Division».Microsoft Research, Silicon Valley.
↑ Compare's: en el procediment dividix_unsigned, el denominador deu ser estrictament positiu.
↑ El còdic s'eixecuta en «URM Simulator». «Unlimited Register Machine (URM) simulator (emulator) -- a "virtual URM". It is modeled after the URM specification in Nigel J. Cutland's book, Computability, An introduction to recursive function theory, by Cambridge Press.»

Referències

Este artícul conté una traducció derivada de «Algoritmo de división» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] «Software Integer Division».Microsoft Research, Silicon Valley.

[2] Compare's: en el procediment dividix_unsigned, el denominador deu ser estrictament positiu.

[3] El còdic s'eixecuta en «URM Simulator». «Unlimited Register Machine (URM) simulator (emulator) -- a "virtual URM". It is modeled after the URM specification in Nigel J. Cutland's book, Computability, An introduction to recursive function theory, by Cambridge Press.»

[1]

[2]

[3]