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
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