Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice



Acasa » referate » matematica
Operatii aritmetice; conceptul de depasire

Operatii aritmetice; conceptul de depasire



Operatii aritmetice; conceptul de depasire

1. De ce codul complementar?

Spuneam intr-o sectiune precedenta ca implementarile operatiilor peste intregi trebuie, pe de o parte sa fie eficiente, iar pe de alta parte sa se foloseasca, pe cat posibil, algoritmi comuni de evaluare a operatiilor fundamentale peste numere intregi, indiferent de conventia de reprezentare.

Pana in prezent reprezentarea in cod complementar raspunde cel mai bine cerintelor de mai sus. Principalele motive sunt urmatoarele doua:

Operatia de adunare se executa la fel, indiferent de faptul ca avem de-a face cu conventia de reprezentare fara semn sau cea de reprezentare cu semn. Operatia executata este o adunare simpla, pe n biti (n – dimensiunea locatiei), cu ignorarea ultimului transport.

Operatia de scadere se reduce la operatia de adunare a descazutului cu complementul scazatorului.



Dupa cum se apreciaza, procentul operatiilor aditive – adunari si scaderi este mult mai mare in aplicatii decat cel al operatiilor multiplicative. De aici si preferinta proiectantilor pentru adoptarea codului complementar pentru reprezentarea intregilor cu semn. In schimb, operatiile de inmultire si impartire sunt efectuate cu algoritmi separati pentru reprezentarile fara semn si reprezentarile cu semn.

In consecinta, programatorul isi alege conventia cu semn sau fara semn in functie de specificul problemei. El utilizeaza aceleasi operatii pentru adunari si scaderi si operatii specifice cu semn sau fara semn pentru operatiile de inmultire si impartire.

2. Conceptul de depasire

Asa dupa cum am aratat mai sus, reprezentarea numerelor intregi se face in locatii cu dimensiune fixata apriori. In mod natural, trebuie sa ne punem problema: ce se intampla cand rezultatul nu incape in spatiul care-i este rezervat?

Generic vorbind, depasirea apare atunci cand rezultatul unui calcul nu incape in spatiul care-i este rezervat.

Specific vorbind, conditiile de aparitie a unei depasiri apar in mod diferit in functie de context. Contextul depinde, pe de o parte daca se utilizeaza conventia fara semn sau conventia cu semn. Pe de alta parte, contextul depinde de tipul operatiei: aditiva sau multiplicativa.

Procesoarele sunt astfel construite incat sa semnaleze, in mod specific, fiecare situatie de depasire. Ramane in sarcina utilizatorului daca ia in calcul semnalele procesorului si pe care anume.

In cele ce urmeaza vom aborda, pe rand tipurile de operatii si in cadrul acestora vom semnala situatiile de depasire.

3. Adunari si scaderi

Operatiile de adunare si de scadere sunt efectuate de calculator exact dupa algoritmii cunoscuti din clasa I primara, cu singura deosebire ca operatiile sunt efectuate in baza 2. In schimb, datorita regulilor de dimensionare si a faptului ca operatia este efectuata de masina si nu de om, exista posibilitatea de aparitie a depasirilor.

Pentru cazul operatiilor fara semn, exista doua reguli care provoaca depasire:

R1) Daca rezultatul adunarii nu incape pe n biti, atunci apare depasire la adunare si raman in rezultat numai bitii de la ordinul 0 la ordinul n-1, iar bitul de ordin n se pierde.

R2) Daca intr-o operatie de scadere descazutul este mai mic decat scazatorul, atunci are loc depasire la scadere, dar operatia se executa, facandu-se 'imprumut fictiv' de la un rang inexistent.

Aceste reguli sunt intuitiv clare (justificabile) si se pot aplica si tehnic ca atare.

Dam, in continuare, cateva exemple de operatii de adunare si scadere analizate in conventia fara semn. Pentru fiecare operatie, vom scrie mai intai operanzii in baza 10, apoi in baza 16 si apoi in baza 2. Dimensiunea locatiilor este fie de un octet, fie de doi octeti.

Baza 10

Baza 16

Baza 2

Observatii

18+

18

36

12+

243-

18

225

F3-

E1

243+

18

261

F3+

Depasire la adunare, conform regulii R1!

18-

243

-225

12-

F3

1F

Depasire la scadere, conform regulii R2!

575+

650

1225

023F+

028A

04C9

650-

575

75

028A-

023F

004B

90

FFFF+

005A



Depasire la adunare, conform regulii R1!

575-

650

-75

023F-

028A

FFB5

Depasire la scadere, conform regulii R2!

Sa ne ocupam in continuare de operatiile de adunare si scadere in conventia cu semn. Toate numerele se vor considera ca fiind reprezentate in cod complementar.

Mai intai trebuie sa reamintim faptul ca in cod complementar scaderea inseamna, de fapt, adunarea descazutului cu complementul scazatorului (vezi sectiunea 1.). Pentru a surprinde situatiile de depasire este suficient sa studiem efectuarea de sume ale unor numere din intervalul [-2n-1 , 2n-1-1] si de a depista aici situatiile in care poate sa apara depasire, adica neincadrarea sumei in intervalul admis [-2n-1 , 2n-1-1] pentru suma pe n biti.

Sa consideram doua numere x , y din intervalul [-2n-1 , 2n-1-1] si sa consideram suma lor algebrica x + y. Este suficient sa studiem urmatoarele trei cazuri:

x <0 si y ≥ 0. Din apartenenta la interval avem ca -2n-1 ≤ x < 0 si 0 ≤ y ≤ 2n-1-1.

x ≥ 0 si y ≥ 0. Din apartenenta la interval avem ca 0 ≤ x ≤ 2n-1-1 si 0 ≤ y ≤ 2n-1-1.

x < 0 si y < 0. Din apartenenta la interval avem ca -2n-1 ≤ x < 0 si -2n-1 ≤ y < 0.

Inegalitatile din cazul 1) ne asigura ca in primul caz suma algebrica apartine aceluiasi interval. Intr-adevar, din inegalitatile: -2n-1 ≤ x < 0 si 0 ≤ y ≤ 2n-1-1 avem, pe de o parte, ca x ≤ x + y, deci -2n-1 ≤ x + y. Pe de alta parte, din aceleasi inegalitati rezulta ca x + y ≤ y, deci x + y ≤ 2n-1-1. In concluzie, x + y apartine intervalului [-2n-1 , 2n-1-1]. De aici se deduce ca daca doua numere sunt de semne contrare, atunci suma lor nu poate produce depasire. Asa cum se va vedea din exemplele care urmeaza, atunci cand se face suma codurilor complementare este posibil sa apara transport de cifra semnificativa, dar acest fapt este ignorat, deoarece nu produce depasire.

In cazurile 2) si 3) este posibila aparitia depasirii. In cazul 2) x + y poate avea valoarea maxima 2n-2, iar depasire apare daca x + y > 2n-1-1. Deoarece codurile complementare se aduna ca si numere fara semn, rezulta ca depasire apare atunci cand pe pozitia bitului de semn apare cifra 1, ceea ce in cod complementar inseamna numar negativ!

In cazul 3) x + y poate avea valoarea minima -2n, iar depasire apare daca x + y < -2n-1. Analog ca mai sus, rezulta depasire daca pe pozitia bitului de semn apare cifra 0, ceea ce in cod complementar inseamna numar pozitiv!

Din studiul celor trei cazuri rezulta o regula simpla a depasirii la adunare in cod complementar:

R3) Suma a doua numere reprezentate in cod complementar provoaca depasire daca si numai daca sunt de acelasi semn si rezultatul sumei lor este de semn contrar.

Din aceasta regula se poate deduce si regula depasirii la scaderea cu semn. Avand in vedere faptul ca o scadere a – b = c este echivalenta cu adunarea a = b + c, din regula R3 rezulta ca:

R4) Diferenta a doua numere reprezentate in cod complementar provoaca depasire daca si numai daca scazatorul si diferenta sunt de acelasi semn si descazutul este de semn contrar.

Practic, putem identifica doua tipuri de situatii ce vor semnala depasire la scaderea cu semn, in situatia b) fiind necesar un 'imprumut fictiv'.

a)

1 - - - - - - - - -

0 - - - - - - - -

0 - - - - - - - -

b)

0 - - - - - - - - -

1 - - - - - - - -

1 - - - - - - - -

Intuitiv, in cazul a) depasirea se justifica prin imposibilitatea obtinerii unui numar pozitiv ca rezultat al scaderii unui numar pozitiv dintr-unul negativ. In cazul b) depasirea se justifica intuitiv daca facem referire la adunarea echivalenta (a-b = c a = b+c); aici diferenta si scazatorul negative nu pot furniza descazut pozitiv.

Asa cum se va vedea din exemplele care urmeaza, atunci cand se face diferenta codurilor complementare este posibil sa apara imprumut fictiv de cifra semnificativa, dar acest fapt este ignorat, deoarece nu produce depasire.

In continuare prezentam cateva exemple de adunari si scaderi ale unor numere reprezentate in cod complementar. Pentru simplitatea expunerii, vom utiliza operanzii reprezentati in cod complementar pe 4 biti. Conform celor de mai sus, pentru patru biti intervalul de reprezentare este [-23 , 23-1], adica [-8 , 7]. Operanzii ii vom transcrie din baza 10 direct in cod complementar. Vom semnala cazurile de transport, imprumut fictiv si depasire.

Suma

in baza 10

Suma in cod

complementar

Transport

sau

depasire

Diferenta

in baza 10

Diferenta in

cod complementar

Imprumut

sau

depasire

Transport


Imprumut

Transport

Imprumut

Nu se poate scrie 7-8 pe 4 biti, deoarece 8 nu apartine intervalului [-8,7].

Depasire!

Depasire!



Depasire!

Depasire!

Depasire!

Depasire!

Depasire!

Inmultiri si impartiri

Inmultirea si impartirea pe n biti impun urmatoarele restrictii de dimensiune a locatiilor:

Inmultirea pe n biti presupune ca ambii factori sunt reprezentati pe cate n biti, iar produsul lor va fi reprezentat pe 2 * n biti. In cazul conventiei cu semn, factorii inmultirii vor fi reprezentati in cod complementar. Produsul va fi reprezentat tot in cod complementar si va respecta regula semnelor.

Ca o consecinta imediata a acestei dimensionari, rezulta ca operatia de inmultire nu provoaca depasire! Intr-adevar, in conventia fara semn cea mai mare valoare posibila pe n biti este 2n-1, patratul acestei valori este 22n- 2n+1+1, numar care incape pe 2n biti. In conventia cu semn, numarul -2n-1 are valoarea absoluta cea mai mare, iar patratul acesteia este 22n-2, numar care se poate reprezenta pe 2n-1 biti, deci in cod complementar acest numar se poate reprezenta pe 2n biti.

Impartirea pe n biti (oarecum invers fata de inmultire), impune conditia ca deimpartitul sa fie reprezentat pe 2 * n biti, iar impartitorul pe n biti. Operatia furnizeaza doua rezultate: catul reprezentat pe n biti si restul reprezentat tot pe n biti. In cazul conventiei cu semn, deimpartitul si impartitorul se vor reprezenta in cod complementar. Atat catul, cat si restul vor fi, de asemenea, reprezentate in cod complementar. Catul impartirii va respecta regula semnelor. Important! Restul impartirii va fi, in valoare absoluta mai mic decat valoarea absoluta a impartitorului si va avea acelasi semn ca si deimpartitul! De exemplu, -7 : 3 da catul -2 si restul -1, adica -7 = (-2) * 3 + (-1). Rugam cititorul sa compare acest rezultat cu cel impus de teorema impartirii cu rest din aritmetica, care impune ca restul sa fie un numar pozitiv, deci in aritmetica avem (-7) = (-3) * 3 + 2, deci catul -3 si restul 2!

Operatia de impartire semnaleaza eroare la impartitor zero (Divide by zero!). In cazul neincadrarii in dimensiuni semnaleaza depasire! Spre exemplu, impartirea fara semn 1000 : 3 se poate, formal, efectua, deoarece deimpartitul se poate reprezenta pe 16 biti si impartitorul se poate reprezenta pe 8 biti. La aceasta operatie va apare depasire, deoarece catul este 333 si nu se poate reprezenta pe 8 biti. Restul impartirii este 1 si se poate reprezenta pe un octet. Pentru a evita o astfel de situatie, programatorul poate decide sa faca operatia pe 16 biti, adica sa reprezinte deimpartitul pe 32 de biti si impartitorul pe 16 biti, urmand sa obtina catul si restul pe cate 16 biti (333 incape pe 16 biti si astfel nu vom mai avea depasire).

Sa exemplificam mai intai operatiile de inmultire si impartire fara semn.

Inmultirea fara semn a numerelor intregi reprezentate binar se desfasoara conform algoritmului cunoscut, doar ca se foloseste baza 2. Pentru comoditate, vom considera n = 4. Sa consideram factorii 11 si 13. Inmultirea lor in baza 2 este:

1011

1101

1011

0000

1011

1011

10001111

Intr-adevar, 11

Plecand de la acest exemplu, se poate observa ca:

Inmultirea genereaza o serie de produse partiale care sunt adunate. Exista cate un produs partial pentru fiecare cifra a inmultitorului.

Produsele partiale sunt fie deinmultitul, fie 0.

Produsele partiale nenule pot fi adunate unul cate unul. Ele sunt obtinute deplasand deinmultitul spre stanga cu cate o pozitie.

Inmultirea a doua numere de cate n biti genereaza un produs care ocupa 2*n biti (motiv pentru care s-a impus restrictia de dimensiune amintita mai sus).

Impartirea fara semn se efectueaza, de asemenea, dupa regulile cunoscute ale aritmeticii. Sa impartim pe 147 la 11. Impartirea in baza 2 este:

├────

|1101

1011

=0111

0000

=1111

1011

=100

Intr-adevar, 147 impartit la 11 da catul 13 si restul 4.

Ca si la inmultire, putem face o serie de observatii. Acestea evidentiaza faptul ca, in ultima instanta, impartirea in baza 2 se reduce la o succesiune de scaderi succesive combinate cu operatii de deplasare.

Sa reamintim cateva observatii privind inmultirile si impartirile cu semn.

Toti operanzii implicati in operatii sunt reprezentati in cod complementar, in conformitate cu cerintele de dimensionare expuse mai sus.

Atat la inmultirea cu semn cat si la impartirea cu semn, se respecta regula semnelor.

Pentru operatia de impartire, restul este in modul mai mic decat modulul impartitorului, iar semnul restului este acelasi cu semnul deimpartitului.

Algoritmii de inmultire si impartire in cod complementar nu pot fi preluati natural de la cei fara semn, asa cum stau lucrurile la adunare si scadere. Daca ar fi asa, atunci in exemplul de mai sus, interpretand 1011 ca -5 si 1101 ca -3 ar rezulta produsul -113 in loc de -15! Normal, deoarece configuratia de biti 10001111 care este rezultatul inmultirii binare, este reprezentarea in cod complementar a numarului -113! La fel, daca interpretam cu semn exemplul dat la impartirea fara semn, avem 'egalitatea' in cod complementar:

adica -109 = (-5) * (-3) + 4 !

Nu vom detalia algoritmii specifici inmultirii si impartirii cu semn. Cititorii pot obtine detalii din [Boian96].





loading...





Politica de confidentialitate

.com Copyright © 2020 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Proiecte

vezi toate proiectele
 PROIECT DE LECTIE Clasa: I Matematica - Adunarea si scaderea numerelor naturale de la 0 la 30, fara trecere peste ordin
 Proiect didactic Grupa: mijlocie - Consolidarea mersului in echilibru pe o linie trasata pe sol (30 cm)
 Redresor electronic automat pentru incarcarea bateriilor auto - proiect atestat
 Proiectarea instalatiilor de alimentare ale motoarelor cu aprindere prin scanteie cu carburator

Lucrari de diploma

vezi toate lucrarile de diploma
 Lucrare de diploma - eritrodermia psoriazica
 ACTIUNEA DIPLOMATICA A ROMANIEI LA CONFERINTA DE PACE DE LA PARIS (1946-1947)
 Proiect diploma Finante Banci - REALIZAREA INSPECTIEI FISCALE LA O SOCIETATE COMERCIALA
 Lucrare de diploma managementul firmei “diagnosticul si evaluarea firmei”

Lucrari licenta

vezi toate lucrarile de licenta
 CONTABILITATEA FINANCIARA TESTE GRILA LICENTA
 LUCRARE DE LICENTA - FACULTATEA DE EDUCATIE FIZICA SI SPORT
 Lucrare de licenta stiintele naturii siecologie - 'surse de poluare a clisurii dunarii”
 LUCRARE DE LICENTA - Gestiunea stocurilor de materii prime si materiale

Lucrari doctorat

vezi toate lucrarile de doctorat
 Doctorat - Modele dinamice de simulare ale accidentelor rutiere produse intre autovehicul si pieton
 Diagnosticul ecografic in unele afectiuni gastroduodenale si hepatobiliare la animalele de companie - TEZA DE DOCTORAT
 LUCRARE DE DOCTORAT ZOOTEHNIE - AMELIORARE - Estimarea valorii economice a caracterelor din obiectivul ameliorarii intr-o linie materna de porcine

Proiecte de atestat

vezi toate proiectele de atestat
 Proiect atestat informatica- Tehnician operator tehnica de calcul - Unitati de Stocare
 LUCRARE DE ATESTAT ELECTRONIST - TEHNICA DE CALCUL - Placa de baza
 ATESTAT PROFESIONAL LA INFORMATICA - programare FoxPro for Windows
 Proiect atestat tehnician in turism - carnaval la venezia




Descrierea matematica a semnalelor continue deterministe
Cazuri exceptate la calculul limitelor de siruri
Determinarea solutiei aproximative a ecuatiei diferentiale dupa conditia initiala
FORMULE DE GEOMETRIE ANALITICA IN PLAN
Polinom caracteristic
PREMISELE FORMALIZARII RISCULUI
O DEMONSTRATIE A TEOREMEI LUI THALES
APLICAII LINIARE



loading...

Termeni si conditii
Contact
Creeaza si tu