Strona główna » Algorytmy » Artykuły » Dokładne Dzielenie
 

Dokładne Dzielenie

Cel

Komputery, choć mogą dużo obliczeń bardzo szybko obliczyć, borykają się z precyzją obliczeń. Wyniki obliczeń bardzo często są jedynie przybliżeniem, a nie faktycznym wynikiem operacji arytmetycznej. W tym artykule zostanie przedstawiony sposób jak tego uniknąć i wypisać wynik z praktycznie dowolną dokładnością.

Algorytm

Komputer jest w stanie wyliczyć wynik dzielenie praktycznie z dowolną dokładnością, ale ogranicza go metoda przechowywania danych w komputerze. Oznacza to, że chcą obliczyć wynik dzielenia z dowolną dokładnością należy zapomnieć o przechowywaniu wyniku w standardowych typach danych. Istnieje możliwość, aby kolejno wyliczone cyfry wypisywać na konsolę, albo do pliku.

Algorytm, który pozwala na dzielenie z dowolną dokładnością jest implementacją dzielenia pisemnego. Otóż w pętli należy nonstop obliczać aktualny wynik dzielenie poprzednią resztę przez dzielnik, aby dopisać kolejną cyfrę. Nową resztę do kolejnej iteracji oblicza się poprzez pomnożenie aktualnej przez 10, a następnie podzieleniu przez dzielnik.

Przykład

Na początek weźmy prosty przykład - podzielimy 1 przez 8. W tym celu kolejno należy wykonać:

ResztaNowa cyfraNowa resztaKomentarz
10.1 · 10W celu obliczenia pierwszej reszty wykonujemy 1 mod 8
101(10 - 8·1)·10 = 20Pierwsza cyfra po przecinku to 1
202(20 - 8·2)·10 = 40Kolejna cyfra to 2
405(40 - 8·5)·10 = 0Reszta wyniosła 0, można zakończyć obliczenia

Używając algorytmu udało się wyznaczyć, że 1/8 = 0.125.

Implementacja

Funkcja dzielPrecyzja() przyjmuje 3 argumenty: n - liczbę do podzielenia, d - dzielnik oraz k - ile miejsc po przecinku wypisać. Wynik jest wypisywany bezpośrednio na konsolę.

  1. void dzielPrecyzja(int n, int d, int k) {
  2.   cout << n / d << ".";
  3.   int reszta = n % d;
  4.   for (int i = 0; i < k; i++) {
  5.     cout << (10 * reszta) / d;
  6.     reszta = (10 * reszta) % d;
  7.   }
  8. }

Przed rozpoczęciem pętli algorytm oblicza resztę początkową, a następnie w pętli oblicza kolejne cyfry rozwinięcia dziesiętnego wyniku. Każda kolejna cyfra jest wypisywana na konsolę.

Testowanie funkcji

Poniższy fragment kodu wczytuje od użytkownika liczbę do podzielenia, dzielnik oraz ile cyfr po przecinku wypisać.

  1. int main() {
  2.   int n, d, k;
  3.   cout << "Podaj liczbe do podzielenia:\n a = ";
  4.   cin >> n;
  5.   cout << "Podaj dzielnik\n d = ";
  6.   cin >> d;
  7.   cout << "Ile miejsc po przecinku wypisac?\n k = ";
  8.   cin >> k;
  9.   dzielPrecyzja(n, d, k);
  10.   system("pause");
  11.   return 0;
  12. }

Zadania

Zadanie 1

Napisz funkcję dzielPrecyzja(), która wypisze maksymalnie k miejsc po przecinku. Jeśli od pewnego momentu wszystkie kolejne cyfry to 0 to program nie powinien ich wypisać przykładowo wypisanie wyniki 1/8 z dokładnością do 10 miejsc po przecinku powinno wypisać jedynie 0.125 zamiast 0.1250000000.