mXparser - logo

Ostatni post opublikowałem w dniu 27.02.2017, był to wpis na temat wskaźnika Giniego. Minął już ponad kwartał i być może niektórzy z Was są zainteresowani „dlaczego chwilowo wyciszyłem swoją aktywność”. Otóż – nie wyciszyłem 🙂 Poniżej wyjaśniam o co chodzi.

https://github.com/mariuszgromada

MathParser.org-mXparser - 2017 - commits - GitHub

 

MathParser.org-mXparser

Od ponad 3 miesięcy intensywnie rozwijam projekt MathParser.org-mXparser. Przez ten okres:

  • Przygotowałem release v.4.0.0: cała masa nowych funkcjonalności (w tym: operatory bitowe, notacja naukowa, wsparcie dla jednostek).
  • Przygotowałem release v.4.0.2: port biblioteki wspierając tym samym wiele nowych platform (.NET Core, .NET Standard, .NET PCL, Xamarin.iOS, Xamarin.Android).
  • Pracowałem nad wersją v.4.1-Aeries: głównie wsparcie dla innych (niż z podstawą 10) systemów numerycznych, ale również szereg nowych bardzo przydatnych rozszerzeń API (w tym: praca z wbudowanymi tokenami, rozpoznawanie prawdopodobnych typów dla tokenów niezdefiniowanych). Aeries jest już w 70% zrealizowane – potrzebuję jeszcze około 2 tygodni.

# SLOC

Linie kodu nie są jakimś super wskaźnikiem, ale nic lepszego w tej chwili nie mam. Poniżej tabelka „zmiany stanu” 🙂

# sloc – przed # sloc – obecnie
Java – src 17522 27905
Java – komentarze 9864 12809
C# – src 17605 28193
C# – komentarze 9778 12215

MathParser.org-mXparser w liczbach

  • Do dziś (11.06.2017) – około 12 tys. pobrań, 91 polubień / 24 forki na GitHub,
  • Średnio około 50 pobrań dziennie.
  • Do dziś (11.06.2017)  2351 plików na GitHub, które odnoszą się do mXparser.

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Virtual Reality 3D Graphing Calculator

W ostatnim czasie powstał bardzo ciekawy projekt edukacyjny o nazwie „Virtual Reality 3D Graphing Calculator”, który umożliwia poznawanie matematyki poprzez zabawę i niemal fizyczną interakcję z wykresami różnych funkcji. Oprogramowanie powstało na bazie gogli wirtualnej rzeczywistości (Oculus Rift), sensora ruchu dłoni / palców (Leep Motion Controller) oraz parsera / silnika matematycznego mojego autorstwa (mXparser).

mXparser - mathparser.org

Autorem projektu są studenci z College of Coastal Georgia, inicjatywą opiekuje się German Vargas, Ph.D., Assistant Vice President for Academic Student Engagement, Associate Professor of Mathematics College of Coastal Georgia, One College Drive, Brunswick, GA 31520.

VR 3D Calculator można pobrać tutaj.

Poniżej również filmy prezentujące działanie kalkulatora.

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Witajcie,

W ostatnim czasie pracowałem nad projektem MathParser.org – w efekcie powstała strona w pełni dokumentująca projekt mXparser. Strona zawiera:

Serdecznie zapraszam! Poniżej trochę grafiki mXparsera z linkami do odpowiednich stron 🙂

MathParser.org - mXparser - logo

MathParser.org - mXparser - logo - Tutorial

MathParser.org - mXparser - logo - API

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

W pierwszych trzech częściach „Zabaw z rekurencją” skupialiśmy się na rekurencji bezpośredniej, tzn. na sytuacji, kiedy w ciele funkcji dochodzi do wywołania „siebie samej”. Przebieg rekurencji bezpośredniej jest dość oczywisty, struktura wywołania, argumenty, jak też warunek stopu, są takie same dla wszystkich odwołań.

Rekurencja pośrednia

O rekurencji pośredniej mówimy w sytuacji „łańcucha wywołań”. Przykładowo funkcja f(.) wywołuje funkcję g(.), następnie funkcja g(.) wywołuje f(.), zatem ponowne wywołanie funkcji f(.) realizowane jest bezpośrednio przez funkcję g(.), jednak pośrednio przez f(.), gdyż to f(.) wywołała g(.).

Typy rekurencji

Długość łańcucha nie musi być ograniczona, w rzeczywistości wywołania pośrednie mogą mieć nietrywialną strukturę, mogą „cofać się” do poprzednich elementów, „iść na skróty”, „rozdzielać się”, a w szczególności może dochodzić do wariantów mieszanych – tzn. wywołań bezpośrednich i pośrednich (różnego typu) w ramach jednej procedury. Dobrze to obrazuje poniższy schemat.

Rekurencja pośrednia

Aproksymacja funkcji sin(x) oraz cos(x) przy wykorzystaniu połączenia rekurencji bezpośredniej i rekurencji pośredniej

Przypomnijmy podstawowe tożsamości trygonometryczne dla wielokrotności kątów.

$$\sin(2x)=2\sin(x)\cos(x)$$

$$\cos(2x)=\cos^2(x)-\sin^2(x)$$

Równoważnie powyższe można zapisać jako

$$\sin(x)=2\sin\big(\frac{x}{2}\big)\cos\big(\frac{x}{2}\big)$$

$$\cos(x)=\cos^2\big(\frac{x}{2}\big)-\sin^2\big(\frac{x}{2}\big)$$

Zwróćmy uwagę, że znając rozwiązanie dla argumentu mniejszego $\frac{x}{2}$ możemy podać rozwiązanie dla $x$ – zatem tożsamości trygonometryczne są w istocie rekurencją z odwołaniami bezpośrednimi i pośrednimi! Funkcję $\sin(x)$ w otoczeniu $0$ można przybliżyć przez $x$, natomiast funkcję $\cos(x)$ przez stałą wartość $1$. Im mniejsze otoczenie $0$ wybierzemy tym lepsza aproksymacja w zadanym przedziale, a w konsekwencji mniejszy błąd oszacowania w całości. Przyjęte wartości w otoczeniu $0$ dają również pewny warunek stopu! Mamy więc wszystko co niezbędne do zastosowania strategii rekurencyjnej w aproksymacji.

Ustalmy stałą $a>0$ (reprezentującą otoczenie $0$), następnie definiujemy dwie funkcje rekurencyjne

$$\text{s}(x)=\begin{cases}x&\text{dla}\quad |x|<a\\2\text{s}\big(\frac{x}{2}\big)\text{c}\big(\frac{x}{2}\big)&\text{dla}\quad |x|\geq a\end{cases}$$

$$\text{c}(x)=\begin{cases}1&\text{dla}\quad |x|<a\\\text{c}^2\big(\frac{x}{2}\big)-\text{s}^2\big(\frac{x}{2}\big)&\text{dla}\quad |x|\geq a\end{cases}$$

Podkreślmy ponownie, że funkcja $\text{s}(x)$ wywołuje siebie bezpośrednio oraz wskazuje na funkcję $\text{c}(x)$, która, oprócz bezpośredniego wywołania siebie samej, wskazuje ponownie na $\text{s}(x)$. Jest to zatem ciekawa kombinacja rekurencji bezpośredniej z rekurencją pośrednią. Zapiszmy to w MathParser.org-mXparser.

/* Definicja funkcji rekurencyjncyh */
Constant a = new Constant(&quot;a = 0.1&quot;);
Function s = new Function(&quot;s(x) =&amp;amp;nbsp; if( abs(x) &amp;amp;lt; a, x, 2*s(x/2)*c(x/2) )&quot;, a);
Function c = new Function(&quot;c(x) =&amp;amp;nbsp; if( abs(x) &amp;amp;lt; a, 1, c(x/2)^2-s(x/2)^2 )&quot;, a);

/* Wskazanie, ze 's' korzysta z 'c', a 'c' korzysta z 's' */
s.addDefinitions(c);
c.addDefinitions(s);

Oczekujemy, że im mniejszy parametr $a>0$ tym lepsza aproksymacja funkcji $\sin(x)$ oraz $\cos(x)$ przez odpowiednio $\text{s}(x)$ oraz $\text{c}(x)$. Poniżej wykresy dla $a=0.5$ oraz $a=0.01$.

Rekurencja pośrednia i bezpośrednia - aproksymacja funkcji sin(x) oraz cos(x)

Rekurencja pośrednia i bezpośrednia - aproksymacja funkcji sin(x) oraz cos(x)

Wniosek – proste zapisy rekurencyjne dają złożone wyniki! 🙂

Rekurencja pośrednia i bezpośrednia – animacja

Pozdrowienia,

Mariusz Gromada

Zobacz również:

  1. Polowanie na czarownice – czyli zabawy z rekurencją (część 1)
  2. Prędkość ucieczki do nieskończoności – czyli zabawy z rekurencją (część 2)
  3. Naiwny test pierwszości – czyli zabawy z rekurencją (część 3)

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Liczby pierwsze

Jednym z najprostszych testów pierwszości jest weryfikacja czy dana liczba $n$ posiada dzielnik z przedziału $(2, \sqrt{n})$ – takie podejście nazywane jest metodą naiwną – i niestety charakteryzuje się dużą złożonością obliczeniową. Nawet przy wykorzystaniu Sita Eratostenesa złożoność obliczeniowa sięga $\frac{\sqrt{n}}{\log{n}}$. Jednak w cyklu „Zabawy z rekurencją” nie bardzo zwracamy uwagę na złożoność 🙂 , bardziej chodzi o zobrazowanie jak całe algorytmy mogą być łatwo zapisane w postaci krótkich matematycznych funkcji rekurencyjnych – zatem do dzieła 🙂

Rekurencyjne poszukiwanie dzielników

Naszym zadaniem będzie zdefiniowanie funkcji zwracającej $1$ jeśli podana liczba $n$ jest liczbą pierwszą oraz $0$ w przeciwnym wypadku. Zacznijmy jednak od podania funkcji weryfikującej czy liczba posiada dzielniki.

$${\small\text{CzyDzielnik}(n, a, b)=}$$

$${\small=\begin{cases}0&\text{dla}\quad a>b\\1&\text{dla}\quad n \mod a=0\\ \text{CzyDzielnik}(n, a+1, b)&\text{w inn. przyp.}\end{cases}}$$

Powyższa funkcja zwraca $1$ jeśli liczba $n$ posiada dzielnik z przedziału $(a,b)$, oraz $0$ w przeciwnym wypadku. Następnie definiujemy wyrażenie reprezentujące naiwny test pierwszości.

$${\small\text{CzyPierwsza}(n)=}$$

$${\small=\begin{cases}0&\text{dla}\quad n<2\\ \neg\text{CzyDzielnik}(n,2,\sqrt{n})&\text{dla}\quad n>=2\end{cases}}$$

Rolą funkcji „CzyPierwsza” jest jedynie „wprawienie algorytmu w ruch” oraz zwrócenie negacji wyniki funkcji „CzyDzielnik”. Proste prawda? 🙂 Sprawdźmy więc w mXparser czy to faktycznie działa.

/* Definicja funkcji rekurencyjnych */
Function CzyDzielnik = new Function(&quot;CzyDzielnik(n, a, b) = if( a&amp;amp;gt;b, 0, if( n%a = 0, 1, CzyDzielnik(n, a+1, b) ) )&quot;);
Function CzyPierwsza = new Function(&quot;CzyPierwsza(n) = if( n&amp;amp;lt;2, 0, ~CzyDzielnik(n, 2, sqrt(n)) )&quot;, CzyDzielnik);

/* Obliczenie i wyświetlenie wartości */
mXparser.consolePrintln( &quot;CzyPierwsza(1) = &quot; + CzyPierwsza.calculate(1) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(2) = &quot; + CzyPierwsza.calculate(2) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(3) = &quot; + CzyPierwsza.calculate(3) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(4) = &quot; + CzyPierwsza.calculate(4) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(5) = &quot; + CzyPierwsza.calculate(5) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(6) = &quot; + CzyPierwsza.calculate(6) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(7) = &quot; + CzyPierwsza.calculate(7) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(8) = &quot; + CzyPierwsza.calculate(8) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(9) = &quot; + CzyPierwsza.calculate(9) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );
mXparser.consolePrintln( &quot;CzyPierwsza(10) = &quot; + CzyPierwsza.calculate(10) + &quot;, czas oblicz. = &quot; + CzyPierwsza.getComputingTime() + &quot; s.&quot; );

+ wynik

CzyPierwsza(1) = 0.0, czas oblicz. = 0.08 s.
CzyPierwsza(2) = 1.0, czas oblicz. = 0.03 s.
CzyPierwsza(3) = 1.0, czas oblicz. = 0.026 s.
CzyPierwsza(4) = 0.0, czas oblicz. = 0.022 s.
CzyPierwsza(5) = 1.0, czas oblicz. = 0.038 s.
CzyPierwsza(6) = 0.0, czas oblicz. = 0.015 s.
CzyPierwsza(7) = 1.0, czas oblicz. = 0.028 s.
CzyPierwsza(8) = 0.0, czas oblicz. = 0.015 s.
CzyPierwsza(9) = 0.0, czas oblicz. = 0.053 s.
CzyPierwsza(10) = 0.0, czas oblicz. = 0.011 s.

Wygląda na to, że obliczenia są poprawne! Teraz możemy zweryfikować ile jest liczb pierwszych w podanym przedziale, definiując

$$\pi(n)=\sum_{i=1}^n \text{CzyPierwsza}(i)$$

/* Definicja wyrażenia sumującego wynik funkcji CzyPierwsza */
Expression pi100 = new Expression(&quot;sum(i, 1, 100, CzyPierwsza(i) )&quot;);
pi100.addFunctions(CzyPierwsza);

/* Obliczenie i wyświetlenie wyniku */
mXparser.consolePrintln( &quot;Liczba liczb pierwszych w przedziale (1,100) = &quot; + pi100.calculate());

+ wynik

Liczba liczb pierwszych w przedziale (1,100) = 25.0

Pozdrowienia,

Mariusz Gromada

Pamiętajcie, że uruchamiając kody mXparsera należy dodać w nagłówku:

import org.mariuszgromada.math.mxparser.*;

Kod:

Zobacz również:

  1. Polowanie na czarownice – czyli zabawy z rekurencją (część 1)
  2. Prędkość ucieczki do nieskończoności – czyli zabawy z rekurencją (część 2)
  3. Rekurencja pośrednia – czyli zabawy z rekurencją (część 4)

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Dziś ciekawostka w nawiązaniu do wpisu z dnia 20 października 2015 roku „Liczba PI ukryta w zbiorze Mandelbrota”, ujawniająca nietrywialne powiązanie liczby $\pi$ z prędkością ucieczki do nieskończoności przy zbliżaniu się punktu startu iteracji do „ostrza” zbioru Mandelbrota. Brzmi trochę skomplikowanie? Poniżej wyjaśnienie 🙂

Zbliżanie się do „ostrza” zbioru Mandelbrota

Rozważmy równanie rekurencyjne dla liczb rzeczywistych

$$x_n=\begin{cases}x_{n-1}^2+\frac{1}{4}+\epsilon&\text{dla}\quad n>0\\0&\text{dla}\quad n=0\end{cases}$$

Powyższe wyrażenie powstaje na bazie równania (w liczbach zespolonych) opisującego zbiór Mandelbrota

$$z_n=z_{n-1}^2+c$$

Mandelbrot - Ostrze

Ograniczając się do prostej rzeczywistej (dlatego użyłem zapisu $x_n$) przeanalizujmy zachowanie $x_n$ przy zbliżaniu się elementu $x_1=\frac{1}{4}+\epsilon$ do „ostrza” (ang. „cusp”) zbioru – ostrze to punkt o współrzędnych $(\frac{1}{4},0)$.

Szybkość ucieczki do nieskończoności

Ustalając odpowiednio małe $\epsilon>0$ decydujemy jak bardzo chcemy się zbliżyć do „ostrza”. Teraz zadanie polega na znalezieniu pierwszego $n$, dla którego $x_n>=2$. Takie minimalne $n$ jest dobrą miarą prędkości ucieczki $x_n$ do nieskończoności w zależności od wybranego $\epsilon$. Na marginesie dodam, że zbiór Juli dla równania Mandelbrota (na powyższym obrazku oznaczony kolorem czarnym), reprezentuje punkty „nieuciekające” do nieskończoności w trakcie nieskończonej iteracji . Ta tematyka jest sama w sobie bardzo ciekawa i zapewne kiedyś coś napiszę o atraktorach.

$$x_n=\begin{cases}x_{n-1}^2+\frac{1}{4}+\epsilon&\text{dla}\quad n>0\\0&\text{dla}\quad n=0\end{cases}$$

$$N_\epsilon=\min\big\{n~|~x_n\ge2\big\}$$

Rekurencja na rekurencji

W celu poszukiwania rozwiązania zapisujemy zadanie wykorzystując rekurencję

$$N(n,\epsilon)=\begin{cases}N(n+1,\epsilon)&\text{dla}\quad x_n<2\\n&\text{dla}\quad x_n>=2\end{cases}$$

Nietrudno zauważyć, że zdefiniowaliśmy rekurencję na rekurencji. To zły znak dla wydajności.

Test w MathParser.org-mXparser

/* Definicja funkcji rekurencyjnej */
Function x = new Function(&quot;x(n, eps) = if( n &amp;amp;gt; 0, x(n-1, eps)^2 + 0.25 + eps, 0 )&quot;);
Function N = new Function(&quot;N(n, eps) = if( x(n, eps) &amp;amp;gt;= 2, n, N(n+1, eps) )&quot;, x);

/* Obliczenia i wyświetlenie wyniku */
mXparser.consolePrintln( &quot;eps = 0.01&quot; + &quot;, N(0, eps) = &quot; + N.calculate(0, 0.01) + &quot;, czas = &quot; + N.getComputingTime() + &quot; s&quot; );
mXparser.consolePrintln( &quot;eps = 0.0001&quot; + &quot;, N(0, eps) = &quot; + N.calculate(0, 0.0001) + &quot;, czas = &quot; + N.getComputingTime() + &quot; s&quot; );
mXparser.consolePrintln( &quot;eps = 0.000001&quot; + &quot;, N(0, eps) = &quot; + N.calculate(0, 0.000001) + &quot;, czas = &quot; + N.getComputingTime() + &quot; s&quot; );
mXparser.consolePrintln( &quot;eps = 0.00000001&quot; + &quot;, N(0, eps) = &quot; + N.calculate(0, 0.00000001) + &quot;, czas = &quot; + N.getComputingTime() + &quot; s&quot; );

+ wyczekiwany wynik

eps = 0.01, N(0, eps) = 30.0, czas = 0.224 s
eps = 0.0001, N(0, eps) = 312.0, czas = 1.532 s
eps = 0.000001, N(0, eps) = 3140.0, czas = 37.343 s
eps = 0.00000001, N(0, eps) = 31414.0, czas = 4068.338 s

Wzorzec prędkości ucieczki

$$\epsilon=\frac{1}{10}\Rightarrow N_\epsilon=30$$

$$\epsilon=\frac{1}{1000}\Rightarrow N_\epsilon=312$$

$$\epsilon=\frac{1}{100000}\Rightarrow N_\epsilon=3140$$

$$\epsilon=\frac{1}{10000000}\Rightarrow N_\epsilon=31414$$

WOW! Jaki super wzorzec liczby wymaganych iteracji, aby przekroczyć 2! Dostajemy coś, co przypomina $\pi$, jednak wymaga postawienia „przecinka” w odpowiednim miejscu! Można również zauważyć, że 100-krotne zmniejszenie $\epsilon$ zwiększa niezbędną liczbę iteracji około 10-krotnie. Zmniejszając $\epsilon$ otrzymujemy liczbę coraz bardziej „przypominającą” $\pi$ 🙂

Zbiór Mandelbrota

Pozdrowienia,

Mariusz Gromada

Zobacz również:

  1. Polowanie na czarownice – czyli zabawy z rekurencją (część 1)
  2. Naiwny test pierwszości – czyli zabawy z rekurencją (część 3)
  3. Rekurencja pośrednia – czyli zabawy z rekurencją (część 4)
  4. Liczba PI ukryta w zbiorze Mandelbrota

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

Okres średniowiecza, kobieta winna uprawiania magii, kara straszna – spalenie na stosie! Nadszedł dzień, tłum gawiedzi, czarownica na stosie, płomienie, wiedźma krzyczy – więcej drewna! Więcej drewna! Tłum zdziwiony, mimo wszystko spełnia ostatnie życzenie opętanej. Wiedźma nie przerywa – jeszcze więcej drewna! Więcej drewna! Z oddali dobiega nagły i stanowczy sprzeciw – STOP! Czarownica chce przepełnić stos!

🙂

Czarownica na stosie

Czym jest rekurencja?

Zazwyczaj o rekurencji myślimy jako o procesie podziału zadania na mniejsze, następnie podziału na jeszcze mniejsze, i jeszcze mniejsze … dochodząc do zadań, dla których rozwiązanie jest znane. Od tego momentu zaczyna się składanie „mniejszych” rozwiązań w „większe”, następnie tych większych w jeszcze większe, … i w jeszcze większe … kończąc na rozwiązaniu zadania początkowego. Dla przykładu zapiszmy funkcję n! w postaci rekurencyjnej.

$$n!=\begin{cases}n\cdot(n-1)!&\text{dla}\quad n>0\\1,&\text{dla}\quad n=0\end{cases}$$

W celu zobrazowania reprezentacja powyższego podana w mXparser:

/* Definicja funkcji rekurencyjnej */
Function silnia = new Function(&quot;s(n) = if( n&amp;amp;gt;0, n*s(n-1), 1 )&quot;);

/* Obliczenia i wyświetlenie wyniku */
System.out.println( &quot;n = 0, s(n) = &quot; + silnia.calculate(0) );
System.out.println( &quot;n = 1, s(n) = &quot; + silnia.calculate(1) );
System.out.println( &quot;n = 2, s(n) = &quot; + silnia.calculate(2) );
System.out.println( &quot;n = 3, s(n) = &quot; + silnia.calculate(3) );
System.out.println( &quot;n = 4, s(n) = &quot; + silnia.calculate(4) );
System.out.println( &quot;n = 5, s(n) = &quot; + silnia.calculate(5) );

+ wynik:

n = 0, s(n) = 1.0
n = 1, s(n) = 1.0
n = 2, s(n) = 2.0
n = 3, s(n) = 6.0
n = 4, s(n) = 24.0
n = 5, s(n) = 120.0

Wynik jest zgodny z oczekiwanym. Innym przykład rekurencji to iterowany operator sumowania, niech

$$A_n=a_1+a_2+\ldots+a_n=\sum_{i=1}^n a_i$$

Łatwo zauważyć, że

$$A_n=\begin{cases}a_n+A_{n-1},&\text{dla}\quad n>1\\a_1,&\text{dla}\quad n=1\end{cases}$$

Jak widać, rekurencja jest powszechna, często będąc nieco innym sposobem patrzenia na iteracje.

Formalna definicja rekurencji

O rekurencji mówimy jeśli metoda (funkcja, zachowanie, obiekt) może być opisana przez:

  1. elementy bazowe / rozwiązania bazowe;
  2. zestaw reguł, które redukuję (sprowadzają) każdy inny przypadek do (w kierunku) elementów bazowych.

Rekurencja
Powyższe określenie jest szerokie, ale takie być musi, bo i typów rekurencji jest wiele.

Rekurencja jako złożenie funkcji

Jednym (ale nie jedynym) sposobem zapisu ogólnych równań rekurencyjnych jest złożenie funkcji:

$$f_n=\begin{cases}F\big(f_{n-1},f_{n-2},\ldots,f_{n-k}\big)&\text{dla}\quad n>k\\f_1,f_2,\ldots,f_k&\text{el. baz. dla}\quad n<=k\end{cases}$$

Dobrą ilustracją powyższego jest ciąg Fibonacciego:

$$f_n=\begin{cases}0&\text{dla}\quad n=0\\1&\text{dla}\quad n=1\\f_{n-1}+f_{n-2}&\text{dla}\quad n>1\end{cases}$$

Zapiszmy ciąg Fibonacciego w mXparser:

/* Definicja funkcji rekurencyjnej */
Function fib = new Function(&quot;fib(n) = if( n&amp;amp;gt;1, fib(n-1)+fib(n-2), if(n=1,1,0) )&quot;);

/* Obliczenia i wyświetlenie wyniku */
System.out.println( &quot;fib(0) = &quot; + fib.calculate(0) );
System.out.println( &quot;fib(1) = &quot; + fib.calculate(1) );
System.out.println( &quot;fib(2) = &quot; + fib.calculate(2) );
System.out.println( &quot;fib(3) = &quot; + fib.calculate(3) );
System.out.println( &quot;fib(4) = &quot; + fib.calculate(4) );
System.out.println( &quot;fib(5) = &quot; + fib.calculate(5) );

+ rezultat:

fib(0) = 0.0
fib(1) = 1.0
fib(2) = 1.0
fib(3) = 2.0
fib(4) = 3.0
fib(5) = 5.0

Rekurencja w roli pętli „For”

Podane wyżej przykłady zapisów rekurencyjnych (n!, suma n-pierwszych wyrazów ciągu, ciąg Fibonacciego) są tak naprawdę rekurencyjną realizacją pętli „for” – znamy przecież dokładnie liczbę niezbędnych operacji do wykonania, a i same operacje są raczej łatwe oraz czytelne – zatem zagnieżdżenie ich w pętli „for” nie powinno spowodować utraty przejrzystości kodu.

Poszukiwanie rozwiązania – czyli rekurencja w roli pętli „While/Until”

W metodach numerycznych często stosuje się strategie rekurencyjne – w takiej sytuacji, będąc w kroku $n$, weryfikujemy czy propozycja rozwiązania $n$ spełnia kryterium stopu (np. jakość oszacowania), jeśli tak – kończymy z rozwiązaniem $n$, jeśli nie – przechodzimy do badania propozycji rozwiązania $n+1$. Procedurę rozpoczynamy od kroku 0 (zerowego).

Przykład: znając definicję silni chcemy znaleźć pierwsze $n$, dla którego $n! >= 100$ – takie zadanie formalnie możemy zapisać jako:

$$S_n=\begin{cases}S_{n+1},&\text{dla}\quad n!<100\\n,&\text{dla}\quad n!>=100\end{cases}$$

$$n_{100} = S(0)$$

Reprezentacja w mXparser:

/* Definicja funkcji rekurencyjnej */
Function S = new Function(&quot;S(n) = if( n! &amp;amp;lt; 100, S(n+1), n )&quot;); /* Obliczenia i wyświetlenie wyniku */ System.out.println( &quot;Pierwsze n, że n! &amp;amp;gt;= 100 to n = &quot; + S.calculate(0) );

+ wynik:

Pierwsze n, że n! &amp;amp;gt;= 100 to n = 5.0

Rekurencja bezpośrednia

Wszystkie omawiane wyżej typy rekurencji polegają na wywołaniu z ciała funkcji „siebie samej”, dlatego należą do bardziej ogólnej klasy nazywanej rekurencją bezpośrednią.

Wydajność

Implementacje na bazie rekurencji są bardzo czytelne, o często minimalnym rozmiarze kodu. Jednak coś za coś – tracimy bardzo dużo na złożoności obliczeniowej (powtarzane operacje, dzielenie zadań, operacje na stosie) oraz wymogach pamięci (głównie struktura stosu) – to właśnie dlatego czarownica błagała o drewno – licząc na przerwanie procesu z tytułu przepełnienia stosu 🙂

Cdn 🙂

Pozdrowienia,

Mariusz Gromada

Zobacz również:

  1. Prędkość ucieczki do nieskończoności – czyli zabawy z rekurencją (część 2)
  2. Naiwny test pierwszości – czyli zabawy z rekurencją (część 3)
  3. Rekurencja pośrednia – czyli zabawy z rekurencją (część 4)

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

mXparser – wysoce elastyczny parser (interpreter) wyrażeń matematycznych dla JAVA oraz C# .NET

mXparser - parser matematyczny

mXparser – wersja 1.0.2 dostępna do pobrania

Zmiana w stosunku do 1.0.1 to poprawa kontroli składni w funkcji definiowanej przez użytkownika. Do wersji 1.0.1 użycie argumentu rekurencyjnego w funkcji definiowanej przez użytkownika powodowało zwiększenie liczby oczekiwanych parametrów wywołania funkcji. Wartość argumentu rekurencyjnego jest wyznaczana automatycznie, stąd w kontroli składni (weryfikując liczbę podanych parametrów) taki argument należy pominąć. Od wersji 1.0.2 liczba parametrów funkcji definiowanej przez użytkownika opiera się na bazie liczby argumentów pomniejszonej o argumenty rekurencyjne.

Przykład

Poniżej przykład demonstrujący działanie wprowadzonej zmiany – proszę przesunąć tekst w celu uwidocznienia komentarzy.

</p>
<p>import org.mariuszgromada.math.mxparser.*;</p>
<p>public class mXparserTests {<br />
  public static void main(String[] args) {<br />
    RecursiveArgument z = new RecursiveArgument(&quot;z&quot;,&quot;z(n-1)^2+c&quot;, &quot;n&quot;); /* Definicja argumentu rekurencyjnego */<br />
    z.addBaseCase(0, 0);                                                /* Definicja elementu początkowego */<br />
    Constant c = new Constant(&quot;c&quot;, 0.3);                                /* Deklaracja stałej występującej w równaniu rekurencyjnym */<br />
    z.addConstants(c);                                                  /* Wskazanie argumentowi oczekiwanej stałej 'c' */<br />
    Function diff1 = new Function(&quot;diff1&quot;, &quot;z(n) - z(n-1)&quot;, &quot;n&quot;);       /* Definicja funkcji o parametrze n opartej również na argumencie rekurencyjnym */<br />
    diff1.addArguments(z);                                              /* Wskazanie funkcji oczekiwanego argumentu 'z' */<br />
    System.out.println(diff1.calculate(10));                            /* Obliczenie wartości funkcji + wyświetlenie wyniku */<br />
  }<br />
}</p>
<p>

Rezultat

</p>
<p>0.17863353779409574</p>
<p>

 

Pozdrowienia,

Mariusz Gromada

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa

mXparser - parser matematyczny

Serdecznie zapraszam do zapoznania się z wysoce elastycznym interpreterem wyrażeń matematycznych. Oprogramowanie jest mojego autorstwa, powstało w 2010 roku i wtedy zostało opublikowane w serwisie SourceForge.net. Z racji, że teraz posiadam stronę o odpowiedniej tematyce, zdecydowałem się przygotować dedykowany opis, który znajdziecie pod tym linkiem. Dostępne są również tutorial oraz specyfikacja API.

Pozdrowienia,

Mariusz Gromada

Pobierz mXparser – parser matematyczny

Download mXparser

Download mXparser

Poza Liczbami: Inne Twórcze Przestrzenie

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury

Matematyka i muzyka są ściśle powiązane przez rytm, harmonię i struktury, które wykorzystują matematyczne wzory i proporcje do tworzenia estetycznych i emocjonalnych doznań. Z nieśmiałą ekscytacją przedstawiam moją pierwszą poważniejszą kompozycję, w której starałem się uchwycić te połączenia.

I Am Here – RELEARN – Mariusz Gromada (2024)
I Am Here – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)
Deep Under – RELEARN – Mariusz Gromada (2024)

Scalar – zaawansowana aplikacja mobilna z silnikiem matematycznym mojego autorstwa