Wstęp do Informatyki

Wykład 8

Arytmetyka komputera

Autor: Dr hab. Marek J. Greniewski

Podział na części architektoniczną i

układową współczesnego komputera

Układy we-wy

Procesor
[

ALU

]

Kompilator

System

operacyjny

(np. Windows 2K)

Aplikacje (np. Netscape)

Układy cyfrowe

Obwody

scalone

Lista rozkazów

określająca architekturę

Ścieżki danych i sterowanie

Bramki i

elementy

pamięci

Pamięć

Hardware

Software

Assemble
r

Magistrala

Jednostka arytmetyczno-

logiczna ALU

ALU

Sygnały sterujące

Flagi stanu

Rejestry

Rejestry

Jednostka arytmetyczno-logiczna jest częścią procesora realizującą operacje
arytmetyczne i logiczne. Zarówno dane, jak i wyniki operacji ALU są lokowane
w rejestrach procesora, do których są przesyłane np. z pamięci i z których są
np. zapamiętywane w pamięci. Sygnały sterujące określają rodzaj operacji oraz
rejestry źródłowy i docelowy dla danych.

System dziesiętny a system

binarny

• W używanym na co dzień systemie dziesiętnym mamy dziesięć

cyfr: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

• Liczba całkowita 4728 = 4 x 1000 + 7 x 100 + 2 x 10 + 8 czyli

4 x 10

3

+ 7 x 10

2

+ 2 x 10

1

+ 8 x 10

0

.

• Liczby ułamkowe są reprezentowane w podobny sposób

472,83 = 4 x 10

2

+ 7 x 10

1

+ 2 x 10

0

+ 8 x 10

-1

+ 3 x 10

-2

.

• W systemie binarnym (dwójkowym) mamy tylko dwie cyfry: 0, 1.
• Pamiętać należy, że 0

10

= 0

2

oraz, że 1

10

= 1

2

.

• Liczby binarne są reprezentowane podobnie jak liczby dziesiętne:

10

2

= 1 x 2

1

+ 0 x 2

0

= 2

10

11

2

= 1 x 2

1

+ 1 x 2

0

= 3

10

100

2

= 1 x 2

2

+ 0 x 2

1

+ 0 x 2

0

= 4

10

• Podobnie liczby ułamkowe są reprezentowane jak:

1101,01

2

= 1 x 2

3

+ 1 x 2

2

+ 0 x 2

1

+ 1 x 2

0

+ 0 x 2

-1

+ 1 x 2

-2

=

13,25

10

Reprezentacje liczb całkowitych

• Używanie liczb całkowitych bez znaku jest niewystarczające w

wielu przypadkach. Istnieje kila konwencji reprezentowania

liczb ujemnych. W dalszym ciągu ograniczymy się do

omówienia dwóch takich konwencji.

• Przyjmiemy, że słowo n – bitowe jest używane do

reprezentowania liczb całkowitych: a

n-1

, a

n-2

, ... a

1

, a

0

– gdzie a

i

– cyfry binarne mnożone przez 2

i

, zaś i = 0, 1, ..., n-2, n-1.

• Reprezentacja znak-moduł: cyfra binarna a

n-1

wykorzystana

jest do zakodowania znaku liczby (0 oznacza +, 1 oznacza -).

Wadą reprezentacji znak-moduł jest występowanie +0 oraz –0.

• Reprezentacja uzupełnienia do dwóch: liczba dodatnia

A = a

n-2

x 2

n-2

+ ... + a

1

x 2

1

+ a

0

x 2

0

; zaś liczba ujemna ma

postać

A = -a

n-1

x 2

n-1

+ a

n-2

x 2

n-2

+ ... + a

1

x 2

1

+ a

0

x 2

0

;

jeśli przyjmiemy dla liczb ujemnych a

n-1

= 1, zaś dla dodatnich

a

n-1

=0

to mamy jednolitą reprezentację liczb dodatnich i ujemnych.

Porównanie reprezentacji 4-bitowych liczb

całkowitych

+7

0111

0111

+6

0110

0110

+5

0101

0101

+4

0100

0100

+3

0011

0011

+2

0010

0010

+1

0001

0001

+0

0000

0000

-0

1000

-

-1

1001

1111

-2

1010

1110

-3

1011

1101

-4

1100

1100

-5

1101

1011

-6

1110

1010

-7

1111

1001

Tablice konwersji

1

-128

1

2

4

8

16

32

64

1

1

0

0

0

0

0

-128

+1

+2

= -125

-128

1

2

4

8

16

32

64

1

0

0

0

1

0

0

0

-128

+8

- 120 =

-128

1

2

4

8

16

32

64

1

Ośmiopozycyjna tablica wartości uzupełnienia do dwóch

Konwersja liczby binarnej 10000011 na dziesiętną

Konwersja liczby dziesiętnej –120 na binarną

Reprezentacja stałoprzecinkowa

• Reprezentacje dotychczas omawiane są nazywane

reprezentacjami stałoprzecinkowymi liczb binarnych.

• Nazwa wynika z faktu, że położenie przecinka

pozycyjnego (oddzielającego część całkowitą liczby od
części ułamkowej) jest ustalone.

• Dla liczb całkowitych przecinek pozycyjny znajduje się na

prawo od cyfry binarnej położonej najbardziej na prawo.

• Programista może używać tej samej reprezentacji dla

ułamków binarnych, posługując się skalowaniem liczb,
tak że przecinek pozycyjny znajdzie się w wyniku w
innym położeniu.

Arytmetyka liczb całkowitych

• Algorytm zmiany znaku dla liczb binarnych

reprezentowanych jako uzupełnienie do
dwóch.

• Algorytm mnożenia:

– Bez znakowe liczby całkowite
– Mnożenie w notacji uzupełnienia do dwóch, w

szczególności algorytm Bootha

• Algorytm dzielenia:

– Bez znakowe liczby całkowite
– Dzielenie w notacji uzupełnienia do dwóch

Schemat blokowy układu

dodawania i odejmowania

Układ uzupełnienia

Rejestr B

Sumator

Nadmiar

Rejestr A

Schemat blokowy

mnożenia

liczb binarnych bez znaku

Mnożna

M

n-1

. . . M

0

Układ sterowania

przesuwaniem

i dodawaniem

Sumator n - bitowy

Mnożnik

Q

n-1

. . . Q

0

Akumulator

A

n-1

. . . A

0

C

Dodaj

Przesuń w prawo

Sieć działań

mnożenia

liczb binarnych

bez znaku

Start

Stop

Q

0

= 1?

Licznik_

bitów = 0?

C, A  A + M

Przesunięcie C, A, Q

Licznik_bitów  Licznik_bitów - 1

C, A  0

M  Mnożna

Q  Mnożnik

Licznik_bitów  n

Tak

Nie

Nie

Tak

Iloczyn znajduje się w A, Q

M zawiera 0111

A Q Q

-1

0000 0011 0 stan

początkowy

1001 0011 0 A  A –

M

1000 1001 1

Przesunięcie

1110 0100 1 A  A +

M

0101 0100 1 A  A +

M

0010 1010 0

Przesunięcie

0001 0101 0 A  A –

M

Algorytm

Bootha

mnożenia liczb

w notacji

uzupełnienia do

dwóch

Licznik_bitów = 0?

Q

0

, Q

-1

?

Stop

Start

Przesunąć arytmetycznie w prawo A, Q, Q

-1

Licznik_bitów  Licznik_bitów -1

A  A + M

A  A - M

A  0, Q

-1

 0

M  Mnożna

Q  Mnożnik

Licznik_bitów  n

Tak

Nie

= 10

= 01

= 11
= 00

1

2

3

4

Sieć działań

dzielenia

liczb

binarnych

bez znaku

Stop

Start

Licznik_bitów  Licznik_bitów - 1

Q

0

 1

Q

0

 0

A  A + M

A  A - M

Przesunięcie

w lewo A, Q

A  0

M  Dzielnik

Q  Dzielna

Licznik_bitów  n

Licznik_bitów

= 0?

A < 0?

Nie

Tak

Tak

Nie

Iloraz a Q
Reszta w A

Reprezentacja

zmiennoprzecinkowa

• Reprezentacja stałoprzecinkowa ma istotne

ograniczenie.

Nie pozwala na jednoczesną reprezentację liczb bardzo

dużych oraz liczb ułamkowych – bardzo małych.

• W przypadku liczb dziesiętnych obchodzimy to

ograniczenie stosując notację potęgową. Np. 976 000

000 000 000 może być reprezentowana jako 9,76 x 10

14

,

zaś liczba ułamkowa 0,000000000000976 jako 9,76 x

10

-14

.

• To samo podejście możemy zastosować do liczb

binarnych, reprezentując liczbę jako: ± S x B

±E

, gdzie:

– Znak mantysy ± (plus albo minus)
– Mantysa S
– Wykładnik E.

Typowy 32-bitowy format

zmiennoprzecinkowy

Bit: 0 1 8 9 31

znak przesunięty mantysa
mantysy wykładnik

a) Format

b) Przykłady
0,11010001 x 2

10100

= 0 10010100 10100010000000000000000

-0,11010001 x 2

10100

= 1 10010100 10100010000000000000000

0,11010001 x 2

-10100

= 0 01101100 10100010000000000000000

-0,11010001 x 2

-10100

= 1 01101100 10100010000000000000000

Liczby przedstawione w

typowych formatach 32-

bitowych

-2

31

0

2

31

- 1

a) Liczby całkowite w notacji uzupełnienia do dwóch

b) Liczby zmiennoprzecinkowe

Przepełnienie Wyrażalne Niedomiar
Wyrażalne Przepełnienie
ujemne liczby ujemny dodatni
liczby dodatnie
ujemne Zero
dodatnie

Wyrażalne liczby całkowite

- (1 – 2

-24

) x 2

127

- 0,5 x 2

-128

0 0,5 x 2

-128

(1 – 2

-24

) x 2

127

IEEE Standard 745 dla

formatów

zmiennoprzecinkowych

1-bit 8-bitów 23-bity

1-bit 11-bitów 52-bity

znak przesunięty

mantysa
mantysy wykładnik

znak przesunięty
mantysa
mantysy wykładnik

a) Format pojedynczy

b) Format podwójny

Parametry formatu IEEE

Standard 754

Parametr

Format

pojedynczy

Format

podwójny

Długość słowa w
bitach

32

64

Długość wykładnika
w bitach

8

11

Przesunięcie
wykładnika

127

1023

Maksymalny
wykładnik

127

1023

Minimalny wykładnik

-126

-1022

Zakres liczb

(podstawa 10)

10

-38

, 10

+38

10

-308

, 10

+308

Długość podstawy w
bitach

23

52

Liczba wykładników

254

2048

Liczba ułamków

2

32

2

64

Liczba wartości

1,98 x 2

31

1,99 x 2

63

Arytmetyka

zmiennoprzecinkowa

• Liczby zmiennoprzecinkowe

x = x

s

B

xe

; y = y

s

B

ye

• Operacja dodawania

x + y = (x

s

B

(xe – ye)

+ y

s

) * B

ye

dla xe < ye

• Operacja odejmowania

x - y = (x

s

B

(xe - ye)

- y

s

) * B

ye

dla xe < ye

• Operacja mnożenia

x * y = (x

s

* y

s

) * B

(xe + ye)

• Operacja dzielenia

x ÷ y = (x

s

÷ y

s

) * B

(xe - ye)

Problemy powstające w wyniku

operacji

• Przepełnienie wykładnika

: dodatni wykładnik przekracza

maksymalną dopuszczalną wartość. Może to być traktowana

jako:

plus nieskończoność oraz minus nieskończoność.

• Niedomiar wykładnika

: Ujemny wykładnik przekracza

maksymalną dopuszczalną wartość. Oznacza to, że liczba jest

zbyt mała, aby mogła być reprezentowana. Może być

traktowana jako zero.

• Niedomiar mantysy

: w procesie wyrównywania wykładników

cyfry mantysy mogą „wypłynąć” poza prawy koniec mantysy.

Wymagana jest wówczas pewna forma zaokrąglania.

• Przepełnienie mantysy

: Wynikiem dodawania mantys o

takim samym znaku może być wyprowadzenie najbardziej

znaczącego bitu. Można to naprawić przez powiększenie o

jeden wartości wykładnika oraz ponowne wyrównanie mantys.

Operacje

zmiennoprzecinkowe

• W arytmetyce zmiennoprzecinkowej operacje

dodawania oraz odejmowania są bardziej złożone niż
operacje mnożenia oraz dzielenia.

• Algorytmy dodawania i odejmowania mają cztery

podstawowe etapy wykonywania:

– Sprawdzanie znaków i wartości zerowych argumentów
– Wyrównanie mantys i wyznaczenie wspólnego wykładnika
– Dodanie albo odjęcie mantys
– Normalizowanie wyniku.

• W przypadku operacji dodawania i odejmowania oba

argumenty muszą być umieszczone w rejestrów ALU.
Jeśli format przewiduje domyślny bit mantysy, to dla
wykonania operacji zmiennoprzecinkowej musi być
ujawniony.

Dodawanie i odejmowanie

I

• Operacje dodawania i odejmowania przebiegają

identycznie z wyjątkiem zmiany znaku, proces więc

rozpoczyna się w przypadku odejmowania od zmiany

znaku odjemnika.

• Jeśli którykolwiek z argumentów jest zerem, pozostały

jest podstawiany jako wartość wyniku.

• Następnym krokiem jest takie przekształcenie liczb, tak

aby oba wykładniki były równe [np. 123 * 10

0

+ 456 *

10

-2

, a po przekształceniu (123 + 4,56)*10

0

].

• Zauważmy, że jeśli podstawa jest równa 16, to

przesunięcie o jedną cyfrę jest przesunięciem o 4 bity).

Jeśli wynikiem jest zerowa wartość jednej z mantys, to

drugi argument jest podstawiany jako wartość wyniku.

Jeśli więc obie liczby mają znacznie różniące się

wykładniki, mniejsza z liczb jest tracona.

Dodawanie i odejmowanie

II

•

Następny krok, to sumowanie mantys z uwzględnieniem
znaków. Ponieważ znaki mogą się różnić, wynikiem może
być zero. Istnieje również możliwość przepełnienia
wynikowej mantysy o jedną cyfrę. Jeśli tak się dzieję,
mantysa wyniku jest przesuwana w prawo, a wykładnik
korygowany. Wynikiem może być również przepełnienie
wykładnika; sytuacja taka jest sygnalizowana, a operacja
ulega zatrzymaniu.

•

Kolejnym krokiem jest normalizacja wyniku, która polega
na przesunięciu cyfr mantysy w lewo, aż najbardziej
znacząca cyfra (bit lub 4 bity przy podstawie 16) nie
będzie zerem.

•

Każde przesunięcie powoduje zmniejszenie wykładnika i
dlatego może być przyczyną niedomiaru wykładnika.

•

Ostatni krok to zaokrąglenie wyniku.

Dodawanie

i

odejmowani

e zmienno-

przecinkow

e

Z  X  Y

Wróć

Dodaj

Odejmij

Niedomiar

wykładnika?

Przepełnienie

mantysy?

Przepełnienie

Wykładnika?

Mantysa

= 0?

Wykładniki

równe?

Y = 0?

X = 0?

Zawiadom o

niedomiarze

Z  0

Wstaw

drugą

liczbę do Z

Przesuń

mantysę

w prawo

Inkrementuj

mniejszy

wykładnik

Z  X

Z  Y

Zmień

znak Y

Wróć

Wróć

Wróć

Wróć

Wróć

Mantysa

= 0?

Wyniki

znormalizowane?

Przesuń

mantysę

w prawo

Inkrementuj

wykładnik

Przesuń

mantysę

w lewo

Dekrementuj

wykładnik

Dodaj

mantysy

ze znakiem

Zaokrąglij

wynik

Zawiadom

o nadmiarze

Nie

Tak

Tak

Nie

Nie

Tak

Tak

Tak

Nie

Tak

Nie

Tak

Nie

Tak

Nie

Nie

Tak

Mnożenie i dzielenie

• Mnożenie i dzielenie zmiennoprzecinkowe są procesami o

wiele prostszymi niż dodawanie i odejmowanie.

• Krok początkowy – jeśli którykolwiek z argumentów jest

równy zero, to mamy natychmiast wyznaczony wynik.

• Następnym krokiem jest dodanie (mnożenie) albo odjęcie

(dzielenie) wykładników. Jeśli wykładniki są przechowywane

w postaci przesuniętej, to suma wykładników (mnożenie)

spowodowałaby podwojenie przesunięcia; wobec tego

wartość przesunięcia musi być odjęta od sumy.

• Wynikiem może być nadmiar albo niedomiar wykładnika, co

powinno być zgłoszone i co jest zakończeniem algorytmu.

• Jeśli wykładnik iloczynu (mnożenie) albo ilorazu (dzielenie)

jest we właściwym zakresie, to następnym krokiem jest

działanie na mantysach, z uwzględnieniem znaku.

• Po wykonaniu następuje normalizacja i zaokrąglanie.

Mnożenie

zmienno-

przecinkow

e

Z  X * Y

Wróć

Pomnóż

Niedomiar

wykładnika?

Przepełnienie

Wykładnika?

Y = 0?

X = 0?

Zawiadom o

niedomiarze

Z  0

Dodaj

wykładniki

Pomnóż

mantysy

Odejmij

przesunięcie

Wróć

Wróć

Normalizuj

Zaokrąglij

Zawiadom

o nadmiarze

Nie

Tak

Tak

Nie

Tak

Nie

Nie

Tak

Dzielenie

zmienno-

przecinkow

e

Z  X / Y

Wróć

Podziel

Niedomiar

wykładnika?

Przepełnienie

Wykładnika?

Y = 0?

X = 0?

Zawiadom o

niedomiarze

Z  0

Odejmij

wykładniki

Podziel

mantysy

Dodaj

przesunięcie

Wróć

Wróć

Normalizuj

Zaokrąglij

Zawiadom

o nadmiarze

Nie

Tak

Tak

Nie

Tak

Nie

Nie

Tak

Z 



Analiza dokładności

• Bity zabezpieczenia: rejestry procesora, w których

umieszczane są argumenty i wyniki operacji

zmiennoprzecinkowych są z zasady dłuższe od

mantysy i eksponentu. Te dodatkowe bity nazywamy

bitami zabezpieczenia, poprawiającymi dokładność

obliczeń zmiennoprzecinkowych.

• Zaokrąglenia:

– Zaokrąglenie do najbliższej: wynik zaokrąglany do najbliższej

dopuszczalnej liczby zmiennoprzecinkowej

– Zaokrąglenie w kierunku plus nieskończoność: wynik

zaokrąglany w górę, w kierunku plus nieskończoności

– Zaokrąglenie w kierunku minus nieskończoność: wynik

zaokrąglany w dół, w kierunku minus nieskończoności

– Zaokrąglenie w kierunku zera: wynik zaokrąglany w kierunku

zera.

Norma IEEE 754 dla binarnej

arytmetyki

zmiennoprzecinkowej

• IEEE Standard 754 poza definicjami formatu, określa specyficzne metody i

procedury służące do tego, aby arytmetyka zmiennoprzecinkowa dawała
jednolite i przewidywalne wyniki, niezależnie od platformy sprzętowej.

• Dodatkowymi tematami regulowanymi przez IEEE Standard 754 są między

innymi trzy zagadnienia:

– Arytmetyka nieskończoności: jest traktowana jako przypadek graniczny

arytmetyki liczb rzeczywistych. Z wyjątkiem szczególnych przypadków (jak
dzielenie przez zero), każda operacja obejmująca nieskończoność daje
oczywiste wyniki.

– Symbole NaN: ciche i sygnalizowane. Sygnalizacja NaN nadaje wartość

niezainicjowanym zmiennym oraz rozszerzeniom quasi-arytmetycznym, które
nie są przedmiotem normy. Cicha NaN propagowana jest przez prawie wszystkie
operacje arytmetyczne, nie sygnalizując wyjątków. NaN sygnalizowane służą
sygnalizowania sytuacji wyjątkowych – operacji, gdy pojawi się argument na
którym nie można wykonać operacji. Oba rodzaje NaN mają taki sam format
ogólny: wykładnik złożony z samych jedynek i niezerowa mantysa. Wartość
mantysy może być używana do rozróżniania cichych NaN od sygnalizowanych
oraz określenia szczegółowego sytuacji wyjątkowych.

– Liczby zdenormalizowane: zostały włączone do normy w celu wykorzystania w

razie powstania nadmiaru wykładnika.

Interpretacja liczb

zmiennoprzecinkowych IEEE

754

znak wykładnik mantysa wartość
Zero dodatnie

0 0 0 0

Zero ujemne

1 0 0 - 0

Plus nieskończoność

0 same jedynki 0 + 

Minus nieskończoność

1 same jedynki 0 - 

Ciche NaN

0 same jedynki  0 NaN

Sygnalizowane NaN

1 same jedynki  0 NaN

Dodatnia znormalizowana

0 e > 0  0 > 0

Ujemne znormalizowana

1 e < 0  0 < 0

Dodatnia nieznormalizowana

0 0  0 > 0

Ujemna nieznormalizowana

1 0  0 < 0

Arytmetyka nieskończoności

IEEE 754

5 +(

+ 

) =

+ 

5 –(

+ 

) =

- 

5 +(

- 

) =

- 

5 -(

- 

) =

+ 

(

+ 

) + (

+ 

) =

+ 

(

- 

) + (

- 

) =

- 

(

- 

) - (

+ 

) =

- 

(

+ 

) - (

- 

) =

+ 

Operacje dające ciche

NaN

IEEE 754

Operacje Ciche i sygnalizowane NaN wytworzone przez

Dowolna dowolna operacja na sygnalizowanych NaN

Dodawanie lub odejmowanie operacje na nieskończonościach

(

+ 

) + (

+ 

)

(

- 

) + (

- 

)

(

- 

) - (

+ 

)

(

+ 

) - (

- 

)

Mnożenie

0 *



Dzielenie

0/0

lub

 /

Reszta

x

reszta

0

lub



reszta

y

Pierwiastek kwadratowy

X

-2

gdzie

X < 0