Reprezentacja stałoprzecinkowa
- Na wcześniejszych zajęciach mówiliśmy o tym, że wartość liczby binarnej liczymy następująco:
0 | 1 | 1 | 0 | 1 | |
b4 | b3 | b2 | b1 | b0 | |
{$$ 0 \cdot 2^4 $$} | {$$ 1 \cdot 2^3 $$} | {$$ 1 \cdot 2^2 $$} | {$$ 0 \cdot 2^1 $$} | {$$ 1 \cdot 2^0 $$} | {$$ 13 $$} |
- Można jednak indeksować bity inaczej (czyli nadać też inne wartości wykładnika potęgi przy liczbie 2) co pozwoli na użycie tej samej liczby bitów do reprezentacji zupełnie innej liczby:
0 | 1 | 1 | 0 | 1 | |
b2 | b1 | b0 | b-1 | b-2 | |
{$$ 0 \cdot 2^2 $$} | {$$ 1 \cdot 2^1 $$} | {$$ 1 \cdot 2^0 $$} | {$$ 0 \cdot 2^{-1} $$} | {$$ 1 \cdot 2^{-2} $$} | {$$ 3.25 $$} |
- Jest to jednak nienajlepszy pomysł. Mając do dyspozycji np. 8 bitów, mogliśmy wcześniej zapisać liczby z przedziału od 0 do {$ 2^8 - 1 = 255 $}. Przeznaczając 4 bity na część całkowitą, a 4 na ułamkową, ogranicza to możliwość zapisu liczby jedynie do przedziału od 0 do {$ 2^3 + 2^2 + 2^1 + 2^0 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} = 15.9375 $}. Co więcej, dwie liczby rzeczywiste tak zapisane różniłyby się co najwyżej o {$ \frac{1}{16} $}. Żadnych mniejszych różnic nie moglibyśmy przedstawić.
Reprezentacja zmiennoprzecinkowa
- W zmiennoprzecinkowej reprezentacji, liczby rzeczywiste przedstawiane są następująco: {$$ x = -1^s \cdot 2^c \cdot m $$}
- x - wejściowa liczba rzeczywista
- s - bit znaku (wartość 0 lub 1)
- c - cecha, odpowiada za część całkowitą
- m - mantysa, odpowiada za część ułamkową
- Zauważyć trzeba, że cecha opisuje wykładnik potęgi liczby 2, a nie część całkowitą bezpośrednio. Jeśli więc cecha przyjmowałaby wartości 0, 1, 2, 3, ... to część całkowita liczby będzie kolejno równa 1, 2, 4, 8, ...
- Mantysa jest jednak ułamkowa, a w reprezentacji zmiennoprzecinkowej poszczególne części są mnożone. Dlatego też można przedstawić np. {$ 3 = 2^2 \cdot \frac{3}{4} $} (cecha = 2, mantysa = {$ \frac{3}{4} $}) albo {$ 7 = 2^3 \cdot \frac{7}{8} $} (cecha = 3, mantysa = {$ \frac{7}{8} $}).
- Podobnie przedstawia się dowolne liczby rzeczywiste np. {$ 6.5 = 2^3 \cdot \frac{13}{16} $} (cecha = 3, mantysa = {$ \frac{13}{16} $})
- Oczywiście nie wszystkie liczby rzeczywiste da się tak przedstawić. Są one wówczas reprezentowane jako przybliżenia np. wpisanie liczby 6.1 tak naprawdę wpisze do rejestru wartość 6.09999990463256835936
- Jak dokładnie reprezentowana jest dowolna liczba rzeczywista w komputerze można zobaczyć na tym formularzu oraz można podejrzeć kod źródłowy w asemblerze
Liczby rzeczywiste w języku C
- Deklaracja zmiennych:
float f;
double d; - Wczytanie/wypisanie tych zmiennych:
scanf("%f", &f);
scanf("%lf", &d);
printf("%f\n", f);
printf("%lf\n", d);
Rekurencja
- Funkcja rekurencyjna to taka, która wywołuje samą siebie np.
int f(int n) {
if (n == 0) {
return 1; // warunek graniczny wyjścia z rekurencji
} else {
return 1 + f(n - 1); // wywołanie rekurencyjne
}
} - W niektórych sytuacjach ułatwia to zaprojektowanie rozwiązania np. przeszukiwanie drzewa BST można zaimplementować rekurencyjnie
- Trzeba bezwzględnie pamiętać o prawidłowym umieszczeniu warunku wyjścia z rekurencji. Bez tego, funkcja raz wywołana będzie nieskończenie wywoływać samą siebie (w praktyce skończą się zasoby typu przydzielona pamięć i program się zakończy z błędem)
- Rekurencja bywa kosztowna szczególnie jeśli funkcja ma wiele argumentów i/lub zmiennych lokalnych
- Przykład zależności rekurencyjnej odwołującej się do dwóch elementów wstecz to ciąg Fibonacciego:{$$ F_n = \begin{cases}0 & \mbox{dla } n = 0 \\ 1 & \mbox{dla } n = 1 \\ F_{n-1} + F_{n-2} & \mbox{dla } n > 1 \end{cases} $$}
int fib(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fib(n - 1) + fib(n - 2);
}
}
Zadania na laboratorium
- Symbol Newtona: {$$ {n \choose k} = \begin{cases}1 & \mbox{dla } k = 0 \mbox{ lub } k = n \\ {n - 1 \choose k - 1} + {n - 1 \choose k} & \mbox{dla } 0 < k < n\end{cases} $$}
#include <stdio.h>
int newton(int n, int k) {
...
}
int main() {
int n, k;
scanf("%d %d", &n, &k);
int y = newton(n, k);
printf("%d\n", y);
return 0;
} - Wielomian Legendre'a: {$$ P_{n}(x) = \begin{cases}1 & \mbox{dla } n = 0 \\ x & \mbox{dla } n = 1 \\ \frac{2n+1}{n+1}P_{n-1}(x) - \frac{n}{n+1}P_{n-2}(x) & \mbox{dla } n > 1\end{cases} $$}
#include <stdio.h>
double legendre(double n, double x) {
...
}
int main() {
double n, x;
scanf("%lf %lf", &n, &x);
double y = legendre(n, x);
printf("%lf\n", y);
return 0;
} - Wielomian Hermite'a: {$$ H_{n}(x) = \begin{cases}1 & \mbox{dla } n = 0 \\ 2x & \mbox{dla } n = 1 \\ 2x H_{n-1}(x) - 2(n-1) H_{n-2}(x) & \mbox{dla } n > 1\end{cases} $$}
#include <stdio.h>
double hermite(double n, double x) {
...
}
int main() {
double n, x;
scanf("%lf %lf", &n, &x);
double y = hermite(n, x);
printf("%lf\n", y);
return 0;
}