1

Jan Kniat

http://www.cs.put.poznan.pl/jkniat

NIF222.3

PAKIETY MATEMATYCZNE

„ W obliczeniach był błąd. ”

·

reprezentacja i przetwarzanie danych

·

pakiet

Octave

·

pakiet

Matematica

·

edytor

Latex

2

Mnożenie macierzy

#include <stdio.h>

// język C

#define Aw 2 // liczba wierszy A

#define Ak 3 // liczba kolumn A
#define Bw 3 // liczba wierszy B

#define Bk 2 // liczba kolumn B

void main ()

{

int i, j, m;

double s = 0.0;

double A[Aw][Ak], B[Bw][Bk], C[Aw][Bk];

if (Aw != Bk)

{

printf("Nieprawidłowe rozmiary.\n");

return;

}

c

a

b

ik

ij

jk

j

n

=

*

å

=

1

3

else

{

for (i=0 ; i<Aw ; i++)

{

for (j=0 ; j<Ak ; j++)

{

printf("A[%d][%d] = ", i,j);

scanf("%lf",&A[i][j]);

}

}

for (i=0 ; i<Bw ; i++)

{

for (j=0 ; j<Bk ; j++)

{

printf("B[%d][%d] = ", i,j);

scanf("%lf",&B[i][j]);

}

}

4

for (i=0 ; i<Aw ; i++)

for(j=0 ; j<Bk ; j++)

{

s = 0.0;

for (m=0 ; m<Ak ; m++)

{

s += (A[i][m] * B[m][j]);

}

C[i][j] = s;

}

for (i=0 ; i<Aw ; i++)

{

for (j=0 ; j<Bk ; j++)

printf("C[%d][%d] =

%5.2lf\n",i,j,C[i][j]);

}

}

}

5

A[0][0] = 1

A[0][1] = 2

A[0][2] = 3
A[1][0] = 10

A[1][1] = 11

A[1][2] = 12

B[0][0] = 5

B[0][1] = 6

B[1][0] = 15

B[1][1] = 16

B[2][0] = 25
B[2][1] = 26

C[0][0] = 110.00

C[0][1] = 116.00

C[1][0] = 515.00

C[1][1] = 548.00

6

octave:1> A = [ 1 , 2 , 3 ; 10 , 11 , 12 ]

A =

1 2 3

10 11 12

octave:2> B = [ 5 , 6 ; 15 , 16 ; 25 , 26 ]

B =

5 6

15 16

25 26

octave:3> C = A * B
C =

110 116

515 548

7

#include <matrix.h>

void main()

{

MTX *A, *B, *C;

MRead (A, 2, 3);

MRead (B, 3, 2);

MMult (C, A, B);

MPrint (C, 2, 2);

}

·

zalety PM

–

wiele wbudowanych operacji i funkcji

–

dokładniejsza reprezentacja danych

–

graficzna postać wyników

–

tryb interakcyjny, proste polecenia (początkowo)

·

wady PM

–

interpretacja programu

–

uproszczona składnia

8

REPREZENTACJA DANYCH

A. znaki alfabetu C. dźwięki

B. liczby D. obrazy

A. Znaki alfabetu

·

za pomocą liczb binarnych najczęściej 8-bitowych

1 bajt = 8 bitów 0

¸ 255

·

kod ASCII – 8-bitowy

·

000

¸ 127 standard

·

128

¸ 255 znaki narodowe, specjalne

·

przestarzały, brak NL, strzałek itp.

·

UNICODE – 16-bitowy (www.unicode.org)

B. Liczby

Liczby całkowite bez znaku

·

ciągi binarne n-elementowe 0

¸ (2

n

– 1)

8 b – 1 B – 0

¸ 255

16 b – 2 B – 0

¸ 65 535

32 b – 4 B – 0

¸ 4 294 967 295

9

·

przeliczanie

BIN è DEC : ze wzoru na wartość liczby

L

p

= a

0

p

0

+ a

1

p

1

+ a

2

p

2

+ ...

p = 2

L

2

= 1a

0

+ 2a

1

+ 4a

2

+ 8a

3

+ 16a

4

+ 32a

5

+ 64a

6

+

128a

7

+ 256a

8

+ 512a

9

+ 1024a

10

+ ...

np.

101100

2

= 1*0 + 2*0 + 4*1 + 8*1 + 16*0 + 32*1 = 44

10

DEC è BIN : dzielenie przez 2

44 0

22 0 44

10

= 101100

2

11 1

5 1

2 0

1 1

0

10

·

łatwiej przeliczać gdy p = 2

m

m = 3 system ósemkowy cyfry 0

¸ 7

OCT BIN

0

000

1

001

2

010

3

011

4

100

5

101

6

110

7

111

1 011 101 001 010 001 110

2

= 1351216

8

5403

8

= 101 100 000 011

2

11

m = 4 system heksadecymalny (hex) (szesnastkowy)

cyfry 0

¸ 9, A, B, C, D, E, F

HEX BIN DEC

8

1000

8

9

1001

9

A

1010

10

B

1011

11

C

1100

12

D

1101

13

E

1110

14

F

1111

15

1001 1110 0000 1111

2

= 9E0F

16

AB7DE

16

= 1010 1011 0111 1101 1110

2

·

im mniejsza podstawa tym mniej różnych cyfr ale

więcej pozycji w liczbie o takiej samej wartości

·

system jedynkowy

12

Liczba całkowita bez znaku w rejestrze

1 bajt

Arytmetyka liczb binarnych całkowitych bez znaku

·

dodawanie i odejmowanie jak dla dziesiętnych

001110 14 101000 40

+ 011010 + 26 – 011010 – 26

0 101000 40 0 001110 14

przeniesienie pożyczka

( nadmiar lub bit ( niedomiar lub bit

dodawany do odejmowany od

starszej części starszej części

liczby ) liczby )

7 6 5 4 3 2 1 0

2

7

........................... 2

0

13

·

np. każda liczba zapisana w 2 rejestrach 4–bitowych

91 47

+

+

1011

0101 + 1111

0010 1 1010

0001

0 1000

138

·

mnożenie jak dla dziesiętnych

011 3

* 101 * 5

011 15

000

011

001111

0 1 0 1 1 0 1 1

0 0 1 0 1 1 1 1

1 0 0 0 1 0 1 0

14

·

dzielenie metodą wielokrotnego odejmowania

10100 : 100 20 : 4 = 5

10100

– 100

001 1

0010

– 100

1 1110 0

+ 100

00100

– 100

000 1 101

Liczby całkowite ze znakiem

·

znak – moduł

– 127

¸ + 127

100...0 – 0

znak moduł 000...0 + 0

0

1

+ –

7 6 ..................... 0

15

§

znak – moduł rzadko stosowany bo trudne + –

a + b è Z(a) | M(a) + Z(b) | M(b)

1. Z(a) = Z(b) è Z(a) | ( M(a) + M(b) )

2. Z(a)

¹ Z(b)

M(a) > M(b) M(a)

£ M(b)

Z(a) | ( M(a) – M(b) ) Z(b) | ( M(b) – M(a) )

§

bardziej użyteczny dla

* i / è wtedy niekiedy

stosowany wewnętrznie w arytmometrze

·

uzupełnienie do 2 (Uzp2)

0000 0001 . . . 0111 1000 . . . 1111 10000

liczby + liczby

–

16

0 0 0 1

+ 1

1 0 0 1

– 7

0 0 1 0

+ 2

1 0 1 0

– 6

0 0 1 1

+ 3

1 0 1 1

– 5

0 1 0 0

+ 4

1 1 0 0

– 4

0 1 0 1

+ 5

1 1 0 1

– 3

0 1 1 0

+ 6

1 1 1 0

– 2

0 1 1 1

+ 7

1 1 1 1

– 1

0 0 0 0 è 0 1 0 0 0 – 8

§

liczba 4–bitowa Uzp2 è – 8

¸ + 7

§

obliczanie liczby przeciwnej dla Uzp2

0101 + 5

~ 1010

+ 1

1011 – 5

1011 – 5

~ 0100

+ 1

0101 + 5

17

§

dodawanie i odejmowanie niezależne od znaków è

wynik poprawny, gdy nie ma nadmiaru

0111 7

+ 1011 + (– 5 )

1 0010 2

przeniesienie (pomijamy)

§

zamiast odejmowania dodawanie liczby przeciwnej

4 – 6 = 4 + (– 6 )

0100 4

+ 1010 + (– 6 )

0 1110 – 2

§

mnożenie – algorytm Booth’a (Uzp2)

1) wpisz mnożnik do rejestru o podwójnej długości

2) dopisz 0 z prawej strony

3) na podstawie stanu ostatnich 2 bitów wykonaj:

00 , 11 – nic nie rób

10 – odejmij mnożną

01 – dodaj mnożną

4) przesuń wynik o 1 pozycję w prawo arytmetycznie

(chyba, że jest to ostatni krok)

5) dla liczb n-bitowych mamy n-kroków

18

Np. 6 * ( – 2 ) = – 12

mnożnik = 000110

// + 6

mnożna = 111110

// – 2

0 0 0 0 0 0 0 1 1 0 0

0 0 0 0 0 0 0 0 1 1 0

– 0 0 0 1 0

0 0 0 1 0 0 0 0 1 1 0

0 0 0 0 1 0 0 0 0 1 1

0 0 0 0 0 1 0 0 0 0 1

+ 1 1 1 1 0

1 1 1 1 0 1 0 0 0 0 1

1 1 1 1 1 0 1 0 0 0 0

~ 0 0 0 0 0 1 0 1 1

+ 1

0 0 0 0 0 1 1 0 0 = 12

10

19

·

wykrywanie nadmiaru

§

dla znak – moduł nadmiar,

gdy przeniesienie na bit znaku = 1

0 110 6

+ 0 011 + 3

1 001 9

§

dla Uzp2

0110 6 1010 –6 0110 6 1010 –6

+0100 4 +1100 –4 +1100 –4 +0100 +4

0 1010 1 0110 1 0010 0 1110

OV OV OK. OK.

C

z

= 0 C

z

= 1 C

z

= 1 C

z

= 0

C

s

= 1 C

s

= 0 C

s

= 1 C

s

= 0

C

z

+ C

s

= 1 è nadmiar

20

Przetwarzanie liczb całkowitych ze znakiem

·

rejestry procesora

·

zapis danych w pamięci

(little endian)

AH AL

BH BL

CH

CL

DH

DL

EAX
EBX
ECX

EDX

31 16 15 8 7 0

REJESTRY UNIWERSALNE INTEL

BX

AX

CX
DX

0


k


n

n+1


m

m+1

m+2

m+3

M

7 0

RX

RH RL

BAJT

LOW
HIGH

RH RL

RX

LOW

HIGH

AX

DX

AH AL

DH DL

21

·

rozkazy arytmetyczne Intel

ADD ARG1, ARG2

; ARG1 ç ARG1 + ARG2

ARG2 ( źródło )

R8

R16

R32

PAO

stała

R8

+

–

–

+

+

R16

–

+

–

+

+

R32

–

–

+

+

+

PAO

+

+

+

–

+

( znaczniki arytmetyczne )

ADC ARG1, ARG2 ; ARG1 ç ARG1 + ARG2 + CF

ADD EAX, ECX

; ustawia CF

ADC EBX, EDX

SUB ARG1, ARG2

; ARG1 ç ARG1 – ARG2

SBB ARG1, ARG2

; ARG1 ç ARG1 – ARG2 – CF

INC ARG1

; ARG1 ç ARG1 + 1

DEC ARG1

; ARG1 ç ARG1 – 1

ARG1
( cel )

LOW

HIGH

EAX
EBX

ECX
EDX

LOW

HIGH

22

NEG ARG1

; ARG1 ç – ARG1 (Uzp2)

CMP ARG1, ARG2

; ARG1 – ARG2

MUL ARG1

; R8, R16, PAO

IMUL ARG1

; R8, R16, PAO

DIV ARG1

; R8, R16, PAO

IDIV ARG1

; R8, R16, PAO

Liczby całkowite kodowane dziesiętnie (BCD

·

operacje programu sumującego liczby całkowite

125 + 378 = 503

§

wczytanie znaków 1, 2, 5

§

konwersja znakowo – binarna

§

wczytanie znaków 3, 7, 8

§

konwersja znakowo – binarna

§

dodawanie binarne

§

konwersja binarno – znakowa

§

wyprowadzenie znaków 5, 0, 3

23

·

konwersje

§

CHAR – BIN

1. zeruj wynik

2. dla każdej kolejnej cyfry oblicz

wynik * 10 + ( kod_cyfry – 30H )

§

BIN – CHAR

1. podziel liczbę przez 10

n

( n = liczba cyfr – 1 )

2. iloraz + 30H è kolejny kod_cyfry wyniku

3. odejmij od liczby 10

n

* iloraz

4. n = n – 1 i powtarzaj aż do n = 0

·

dlatego liczby BCD, w kolejnych bajtach :

(liczba 125

10

= 01111101

2

)

§

kody ASCII cyfr

125

§

kody ASCII – 30H

125

31H 32H 35H

1 2 5

00110001 00110010 00110101

00000001 00000010 00000101

24

§

dwa kody ASCII – 30H (format upakowany)

125

·

procesory posiadają rozkazy realizujące + i –

oraz dla niektórych formatów * i /

·

zazwyczaj niedostępne w uniwersalnych

językach programowania

Liczby niecałkowite

·

zapis stałopozycyjny

·

liczba całkowita ułamek

. . . a

2

p

2

+ a

1

p

1

+ a

0

p

0

+ a

-1

p

-1

+ a

-2

p

-2

. . .

§

konwersja binarno – dziesiętna

101.01 = 1*2

2

+ 0*2

1

+ 1*2

0

+ 0*2

-1

* 1*2

-2

=

4 + 0 + 1 + 0 + ¼ = 5¼ = 5.25

1 2 5 0

. . .

. . .

00010010 01010000

25

§

konwersja dziesiętno – binarna 0.43 =

0 43 * 2

0 86

1 72

1 44

0 88 0.43 = 0.0110111 ...

1 76

1 52

1 04

0 08

§

zapis stałopozycyjny

§

dodawanie i odejmowanie jak dla liczb całkowitych

bez znaku (znaki ew. jako odrębne bity)

§

mnożenie i dzielenie è algorytmy iteracyjne

prostsze niż dla liczb zmiennopozycyjnych

.
.
.

liczba całkowita ułamek

16b 16b

4 cyfry

.

4 cyfry

dziesiętne dziesiętne

26

·

zapis zmiennopozycyjny

±m * p

±c

§

p = 10 1.57*10

12

1.57E12 157xxx....xxx

13 cyfr

§

normalizacja

125.78E5

12.578E6 0.12578E8

12578E3

§

p = 2 , standard IEEE 754

01...00 è – 3

cecha

01...01 è – 2

przesunięta

01...10 è – 1

01...11 è 0

10...00 è 1

znak liczby

10...01 è 2

0 è +

10...10 è 3

1 è –

10...11 è 4

s c m

63 62 52 51 0

27

§

mantysa znormalizowana (m) ma zawsze postać

1.xxxxxxxx....xxxxx ( 1.0...0

¸ 1.1..1 )

początkowa jedynka nie jest pamiętana

1.0

10

≤ m < 2.0

10

§

przykłady

0

10

è 0 00000000000 00..00

1.0

10

è 0 01111111111 00...00

–1.0

10

è

1 01111111111 00...00

10

10

è 0 10000000010 0100..00

–10

10

è 1 10000000010 0100..00

15.5 è 0 10000000010 111100..00

–15.5 è 1 10000000010 111100..00

§

reprezentowane wartości

1 1..1 1..1 1 0..01 0..0 0 0..0 0..0 0 0..01 0..0 0 1..1 1..1

ujemne zero dodatnie

28

n è liczba cyfr mantysy

§

dla n = 52 odległość pomiędzy reprezentowanymi

liczbami wynosi:

c = 0 è 2.22044604925e-16

c = 1 è 4.440892098501e-16

c = 52 è 1

c = 150 è 3.169126500571e+29

c = 1023 è 1.995840309535e+292

0 2

0

2

1

2

2

2

3

2

n

2

n

2

n

29

·

dodatkowe obiekty zmiennopozycyjne

ciąg binarny

obiekt

s 00...000 00...000

± 0

s 11.....11 00...000

± ¥

s 11.....11 xx...xxx

NaN

·

operacje wytwarzające wynik NaN

operacja

wyrażenia

+

¥ + (- ¥ ) , x + NaN

–

¥ – ¥ , (- ¥ ) – (- ¥ ) , x – NaN

*

0 * (

± ¥ ) , x * NaN

/

0 / 0 ,

¥ / ¥ , x / NaN

REM

x REM 0 , x REM

¥ ,

x REM NaN , NaN REM x

SQRT

SQRT (x) gdy x < 0 , SQRT (NaN)

30

§

typy liczb zmiennopozycyjnych

w językach programowania

float : 32b 1 / 8 / 23

±3.4 E ±38 7 cyfr

double : 64b 1 / 11 / 52

±1.7 E ±308 15 cyfr

long double: 80b 1 / 15 / 64

±1.2 E ±4932 17 cyfr

·

arytmetyka zmiennopozycyjna

§

mnożenie è mnożenie mantys, sumowanie cech,

normalizacja

§

dzielenie è dzielenie mantys, odejmowanie cech,

normalizacja

§

dodawanie è wyrównanie cech, dodawanie,

normalizacja

§

odejmowanie èwyrównanie cech, odejmowanie,

normalizacja

§

dla 3 cyfr dokładnych

0.375 * 10

5

+ 0.25 * 10

-2

=

0.375 * 10

5

+ 0.000000025 * 10

5

=

0.375000025 * 10

5

@ 0.375 * 10

5

31

§

sposób sumowania trzech liczb

zmiennopozycyjnych aby błąd był najmniejszy

§

obliczenia zmiennopozycyjne na odpowiedzialność

programisty

§

arytmetyka interwałowa

–

tryby zaokrąglania :

do najbliższej, w górę, w dół, obcięcie

–

wykonanie operacji 2 razy :

z zaokrągleniem w górę i z zaokrągleniem w dół

–

przedział na pewno zawierający wynik poprawny

–

operacje arytmetyczne, algorytmy numeryczne,

biblioteki

·

reprezentacje dokładne