Què és la divisió d'ordinadors?

5 respostes 5

Els algoritmes de divisió en dissenys digitals es poden dividir en dues categories principals. Divisió lenta i divisió ràpida.

Us suggereixo que llegiu com de binari i resta treballeu si encara no esteu familiaritzats amb aquests conceptes.

Divisió lenta

Els mètodes més senzills funcionen de la següent manera: Resta el denominador del numerador. Feu això recursivament amb el resultat de cada resta fins que la resta sigui menys que el denominador. La quantitat d'iteracions és el enter quotent, i la quantitat que queda sobre és la resta.

Exemple:

7/3:

$$7- 3=4$
$$443=1$
$$1 < 3$

Així que la resposta és 2 amb una resta de 1. Per fer que aquesta resposta sigui una mica més rellevant, aquí hi ha algun fons. La resta del binari a través de l' afegit de l' negatiu es realitza e.g.7 - 3 = 7 + (-3). Això s'ha aconseguit utilitzant el complement dels seus dos. Cada número binari s' afegeix usant una sèrie d' afegeixs sencers:

A on cada adder d' 1 bit complet s' implementarà el següent:

Divisió ràpida

Mentre que el mètode més lent de la divisió és fàcil d'entendre, requereix iteracions repetitives. Hi ha diversos algorismes de "més ràpid," però tots es basen en la estimació.

Considereu el mètode Goldschmidt:

Faré servir el següent: $$Q = \ frac{ N} {D}$

Aquest mètode funciona de la següent manera:

Multiply N i D amb una fracció F d'aquesta manera que D s'acosta a 1.
Quan D s'acosta 1, N s'acosta a Q

Aquest mètode usa la multiplicació binària mitjançant l' afegit iteratiu, que també s' usa en CPU d' ADM modernes.

El maquinari per a la divisió de punts flotant forma part d' una unitat lògica que també fa multiplicació; hi ha un mòdul de maquinari multiplicador disponible. flotant Números de punt, diguem A i B, es divideix (formant A/ B) per

decomposar els números decimals en signe (+1 o - 1), mantissa ("a" i "b" i (tipus enters)
El signe del resultat és (+1) si ambdós signes són iguals, altrament (-1)
Els exponents es resten (exponent de Bed de l' exponent A) a forma l' exponent del resultat

mantes (els dígits binaris dels nombres) són un número binari de punt fix entre 1/2 i 1; això vol dir que el primer dígit després de la El punt binari és "1," seguit de zeros i u... com a primer pas, una taula de cerca cerca troba el recíproc exacte a sis bits (només n' hi ha 32 possibilitats, és una taula petita)

per començar a calcular a/b, fer dues multiplicació $$ {a\ sobre b} = {{a * recíproc *(b)}\ a més de b * Cíproc(b)} $$ i tingueu present que la precisió de sis bits implica que el denominador del resultat és molt propera a 1 (a cinc o més llocs binaris).

Ara tingueu en compte que per a un denominador, 'd', podem veure que definint $$ d == 1 +\ epsilon $$ $$ d * (2- d) = ( 1+\ epsilon)\ ttimes (1 -\ epsilon) = 1 -\ epsilon $^2$ Això implica que la nostra precisió exacta de 5 bits en el denominador Es tornarà precís en deu bits després d'un parell de multiplicació, Exactitud de vint bits després de dos, i quaranta bits després de tres. Fes tantes iteracions de numerador i denominador per (2 - denominador) Com requereix la vostra precisió de resultat.
El numerador, ara que el denominador és exactament '1', és la mantissa de El resultat, i es pot combinar amb el signe calculat prèviament i l' exponent.
El punt IEEE flotant permet algunes excepcions (sovibles números, NAN; Aquests s'han de gestionar per altres operacions lògiques.

Hi ha mètodes molt diferents per a la divisió, depenent dels números a gestionar. Pels enters, el mètode de torn i subtract donat pels altres funcionarà bé. Per als números de coma flotant, però, pot ser més ràpid calcular primer el recíproc del denominador i multiplicar que multiplicat per el numerador.

La composició de la recíprocitat del denominador no és tan dolenta; es fa refinant les aproximacions successives. Deixa que g sigui la teva suposició per 1/d. Per a una suposició millorada, useu g'=g(2-gd). Aquest convergeix quadràtica, de manera que doblareu els dígits de precisió en cada millora.

Hi ha algunes dreceres. En un punt flotant, pots extreure els poders de deu o poders de dos, depenent de la base número de la teva màquina. I, per a la velocitat de l'ús de la memòria més gran, podeu usar una taula pre-computada pels números en l'abast de 1 a b (on b és la vostra base de número) per a obtenir una suposició que és immediatament propera a la recíproca necessària i desar una o dues passes de millora.

Tingueu present que, com amb la multiplicació i el 1960 de Kologorov la vergonya del seu alumne Anatoly Karatsuba, mai se sap quan es trobarà un mètode més ràpid o millor. Mai rendir la teva curiositat.