Nawigacja po algorytmach numerycznych za pomocą języka Java

Algorytmy numeryczne stanowią podstawę współczesnych obliczeń naukowych i inżynieryjnych, ułatwiając skuteczne rozwiązywanie złożonych problemów matematycznych. W tym artykule wyruszysz ze mną w podróż po krainie algorytmów numerycznych, badając ich znaczenie, zasady i praktyczne implementacje przy użyciu języka programowania Java. Od podstawowych operacji po zaawansowane metody numeryczne – pokazuję, w jaki sposób algorytmy te stanowią podstawę różnych rzeczywistych aplikacji.

Znaczenie algorytmów numerycznych

Algorytmy numeryczne są niezbędnymi narzędziami do rozwiązywania problemów matematycznych, które mogą nie mieć rozwiązań w postaci zamkniętej. Umożliwiają przybliżanie rozwiązań skomplikowanych równań, wykonywanie obliczeń na danych ze świata rzeczywistego i modelowanie złożonych zjawisk. Odgrywają one kluczową rolę w różnych dziedzinach – od symulacji fizycznych po analizę finansową.

Algorytm Euklidesa – największy wspólny dzielnik (NWD)

Algorytm Euklidesa to podstawowy algorytm używany do znajdowania największego wspólnego dzielnika dwóch liczb całkowitych. Największym wspólnym dzielnikiem dwóch liczb jest największa dodatnia liczba całkowita, która dzieli obie liczby bez pozostawiania reszty. Algorytm Euklidesa skutecznie wskazuje NWD, wielokrotnie obliczając resztę dzielenia, aż reszta osiągnie zero.

Implementacja algorytmu euklidesowego w Javie

public class EuclideanAlgorithm {

  public static int gcd(int a, int b) {
    while (b != 0) {
      int remainder = a % b;
      a = b;
      b = remainder;
    }
    return a;
  }

  public static void main(String[] args) {
    int num1 = 35;
    int num2 = 15;

    int result = gcd(num1, num2);
    System.out.println("GCD of " + num1 + " and " + num2 + " is: " + result);
  }
}

Rezultat

GCD of 35 and 15 is: 5

W tym przykładzie metoda gcd implementuje algorytm euklidesowy. Wielokrotnie oblicza resztę dzielenia a przez b, a następnie aktualizuje a jako b i b jako resztę. Proces ten trwa, aż b osiągnie zero. W tym momencie wartość a będzie największym wspólnym dzielnikiem dwóch pierwotnych liczb. Główna metoda pokazuje, jak użyć funkcji gcd do znalezienia GCD dwóch liczb (w tym przypadku 35 i 15).

Kiedy stosuje się algorytm Euklidesa?

Algorytm euklidesowy jest szeroko stosowany w różnych kontekstach matematycznych i algorytmicznych, takich jak kryptografia, upraszczanie ułamków i algorytmy optymalizacyjne. Jego prostota i wydajność czynią go niezbędnym narzędziem w matematyce obliczeniowej.

Generowanie liczb pierwszych (sito Eratostenesa)

Generowanie liczb pierwszych to proces znajdowania wszystkich liczb pierwszych w zadanym zakresie. Sito Eratostenesa jest dobrze znanym algorytmem efektywnego generowania liczb pierwszych. Działa poprzez iteracyjne zaznaczanie wielokrotności każdej liczby pierwszej, zaczynając od 2, a pozostałe nieoznaczone liczby są liczbami pierwszymi.

Implementacja sita Eratostenesa w Javie

public class SieveOfEratosthenes {

  public static void sieveOfEratosthenes(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);

    for (int i = 2; i * i <= n; i++) {
      if (isPrime[i]) {
        for (int j = i * i; j <= n; j += i) {
          isPrime[j] = false;
        }
      }
    }

    System.out.println("Prime numbers in the range 2 to " + n + ":");
    for (int i = 2; i <= n; i++) {
      if (isPrime[i]) {
        System.out.print(i + " ");
      }
    }
  }

  public static void main(String[] args) {
    int n = 100;
    sieveOfEratosthenes(n);
  }
}

Rezultat

Prime numbers in the range 2 to 100:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

W tym przykładzie metoda sieveOfEratostenes implementuje algorytm Sito Eratostenesa. Używa tablicy logicznej isPrime, aby zaznaczyć, czy liczba jest pierwsza, czy nie. Algorytm iteruje po liczbach, zaczynając od 2 aż do pierwiastka kwadratowego z n, oznaczając wielokrotności każdej liczby pierwszej jako inne niż pierwsze. Niezaznaczone liczby pozostałe w tablicy są liczbami pierwszymi. Główna metoda pokazuje, jak używać funkcji sieveOfEratostenes do generowania liczb pierwszych w zakresie od 2 do 100.

Kiedy stosować sito Eratostenesa?

Sito Eratostenesa to wysoce wydajny algorytm generowania liczb pierwszych, którego złożoność czasowa wynosi w przybliżeniu O(n*log (log (n))). Dzięki temu nadaje się do generowania liczb pierwszych w dużym zakresie.

Silnia

Obliczenie silni polega na znalezieniu iloczynu wszystkich dodatnich liczb całkowitych od 1 do danej liczby. Jest ona oznaczona symbolem n! i używana w różnych kontekstach matematycznych i kombinatorycznych.

Implementacja obliczania silni w Javie

public class FactorialCalculation {

  public static long factorialRecursive(int n) {
    if (n == 0 || n == 1) {
      return 1;
    }
    return n * factorialRecursive(n - 1);
  }

  public static long factorialLoop(int n) {
    long factorial = 1;
    for (int i = 2; i <= n; i++) {
      factorial = factorial * i;
    }
    return factorial;
  }

  public static long factorialStreams(int n) {
    return LongStream.rangeClosed(1, n)
      .reduce(1, (long x, long y) -> x * y);
  }

  public static void main(String[] args) {
    int n = 5;
    long factorialRecursive = factorialRecursive(n);
    long factorialLoop = factorialLoop(n);
    long factorialStreams = factorialStreams(n);
    System.out.println("Factorial of " + n + " computed recursively is: " + factorialRecursive);
    System.out.println("Factorial of " + n + " computed by loop is: " + factorialLoop);
    System.out.println("Factorial of " + n + " computed by Stream is: " + factorialStreams);
  }
}

Rezultat

Factorial of 5 computed recursively is: 120
Factorial of 5 computed by loop is: 120
Factorial of 5 computed by Stream is: 120

W tym przykładzie klasa FactorialCalculation implementuje trzy metody obliczeń silniowych: przy użyciu rekurencji, pętli i strumieni Java. Przypadki podstawowe mają miejsce, gdy n wynosi 0 lub 1, a silnia 1. Przy innych wartościach n metody obliczają silnię na różne sposoby. Główna metoda pokazuje, jak używać funkcji silni do obliczania silni liczby (w tym przypadku 5).

Kiedy stosować silnię?

Obliczenia czynnikowe są powszechnie stosowane w różnych kontekstach matematycznych i statystycznych takich jak permutacje, kombinacje i obliczenia prawdopodobieństwa. Jest również używany w algorytmach i dowodach matematycznych.

Potęgowanie binarne

Potęgowanie binarne, znane również jako potęgowanie przez kwadraturę, to wydajny algorytm używany do obliczania potęgi liczby podniesionej do wykładnika całkowitego. Jest to szczególnie przydatne w przypadku dużych liczb, ponieważ potrzeba wtedy mniej wymaganych mnożeń w porównaniu z naiwnym potęgowaniem.

Implementacja potęgowania binarnego w Javie

public static long binaryExponentiation(long base, int exponent) {
  if (exponent == 0) {
    return 1;
  }

  long result = binaryExponentiation(base, exponent / 2);

  if (exponent % 2 == 0) {
    return result * result;
  } else {
    return base * result * result;
  }
}

W tym przykładzie metoda binaryExponentiation implementuje algorytm potęgowania binarnego przy użyciu rekurencji. Oblicza moc podstawy podniesioną do wykładnika. Przypadki podstawowe mają miejsce, gdy wykładnik wynosi 0 (wynik to 1) lub gdy jest parzysty, w którym to przypadku wynik jest podnoszony do kwadratu. Jeżeli wykładnik jest nieparzysty, wynik mnoży się przez podstawę.

Kiedy stosuje się potęgowanie binarne?

Potęgowanie binarne jest bardzo wydajne i zmniejsza liczbę mnożeń wymaganych do obliczenia potęgi liczby. Jest powszechnie stosowany w algorytmach obejmujących arytmetykę modułową, kryptografię i problemy optymalizacyjne.

Testowanie pierwszości

Test pierwszości Millera-Rabina to algorytm probabilistyczny umożliwiający sprawdzenie, czy liczba jest prawdopodobnie pierwsza. Opiera się na właściwościach arytmetyki modułowej i wykorzystuje liczby losowe do probabilistycznego określenia pierwszości.

Przegląd działania algorytmu Millera-Rabina

1. Obróbka wstępna:
   • wyraź podaną liczbę jako (2^r) * d + 1, gdzie d jest nieparzystą liczbą całkowitą.
2. Testowanie świadków:
   • wybierz losową liczbę całkowitą a z zakresu od 2 do n – 2, gdzie n to testowana liczba;
   • oblicz x = a^d mod n.
3. Sprawdź warunki:
   • jeśli x wynosi 1 lub n – 1, przejdź do następnej iteracji;
   • dla każdego r z zakresu [1, r – 1];
   • oblicz x = x^2 mod n;
   • jeśli x wynosi n – 1, przejdź do następnej iteracji;
   • jeśli żaden warunek nie jest spełniony, liczba jest złożona.
4. Powtórz powyższe kroki dla żądanej liczby iteracji (świadków):
   • jeśli liczba przejdzie pomyślnie test dla wszystkich świadków, prawdopodobnie będzie liczbą pierwszą (w przeciwnym razie jest to liczba złożona).

Implementacja testu pierwszości Millera-Rabina w Javie

public class MillerRabinPrimalityTest {

  public static boolean isProbablePrime(int n, int k) {
    if (n <= 1) {
      return false;
    }
    if (n <= 3) {
      return true;
    }

    // Write n as (2^r) * d + 1
    int r = 0;
    int d = n - 1;
    while (d % 2 == 0) {
      r++;
      d /= 2;
    }

    // Witness loop
    for (int i = 0; i < k; i++) {
      int a = 2 + new Random().nextInt(n - 3);
      int x = power(a, d, n);

      if (x == 1 || x == n - 1) {
        continue;
      }

      for (int j = 0; j < r - 1; j++) {
        x = (x * x) % n;
        if (x == n - 1) {
          break;
        }
      }

      if (x != n - 1) {
        return false;
      }
    }

    return true;
  }

  public static int power(int x, int y, int p) {
    int res = 1;
    x = x % p;

    while (y > 0) {
      if (y % 2 == 1) {
        res = (res * x) % p;
      }
      y = y >> 1;
      x = (x * x) % p;
    }

    return res;
  }

  public static void main(String[] args) {
    int num = 11;
    int iterations = 5;

    boolean isPrime = isProbablePrime(num, iterations);
    if (isPrime) {
      System.out.println(num + " is likely prime.");
    } else {
      System.out.println(num + " is not prime.");
    }
  }
}

Rezultat

11 is likely to be prime.

W tym przykładzie metoda isProbablePrime implementuje test pierwszości Millera-Rabina. Wykorzystuje określoną liczbę iteracji (k), aby przeprowadzić test probabilistycznie. Metoda potęgowa skutecznie oblicza potęgowanie modułowe. Główna metoda pokazuje, jak używać funkcji isProbablePrime do sprawdzania, czy liczba (w tym przypadku 11) prawdopodobnie będzie pierwsza po określonej liczbie iteracji (w tym przypadku 5).

Warto wiedzieć o teście pierwszości Millera-Rabina

Test pierwszości Millera-Rabina jest algorytmem probabilistycznym, co oznacza, że może czasami zaklasyfikować liczbę złożoną jako pierwszą (fałszywie dodatni), ale nigdy nie klasyfikuje liczby pierwszej jako złożonej (żadnych wyników fałszywie ujemnych). Dokładność testu rośnie wraz z liczbą wykonanych iteracji.

Podsumowanie

Algorytmy numeryczne stanowią podstawę matematyki obliczeniowej, umożliwiając rozwiązywanie złożonych problemów z implikacjami w świecie rzeczywistym. Od podstawowej arytmetyki po zaawansowane symulacje algorytmy te torują drogę dokładnym rozwiązaniom w różnych dziedzinach. Analiza algorytmów numerycznych w języku Java w tym artykule ukazuje ich praktyczne znaczenie i wyposaża programistów w narzędzia umożliwiające skuteczne radzenie sobie ze złożonymi wyzwaniami matematycznymi.

Odnośniki

• https://en.wikipedia.org/wiki/Euclidean_algorithm
• https://www.geeksforgeeks.org/java-program-for-sieve-of-eratosthenes/
• https://www.baeldung.com/java-calculate-factorial
• https://www.codingninjas.com/studio/library/binary-exponentiation
• https://www.baeldung.com/cs/miller-rabin-method