Friday, June 10, 2016

całkowanie numeryczne

W ramach zaliczenia pewnego przedmiotu trzeba było sobie wybrać zadanie i wykonać projekt. Wybrałem całkowanie numeryczne, bo uznałem to za ciekawy temat. Napisałem względnie prosty skrypt wyznaczający przybliżoną wartość całki oznaczonej funkcji jednej zmiennej czterema metodami. Projekt miał za zadanie wypisać obliczenia, błąd bezwzględny oraz czas wykonywania każdej z metod i wyniki miały zostać przedyskutowane. Do jednej metody (Romberga) wykorzystałem zewnętrzną bibliotekę oraz przyjąłem wartości zwracane przez tę funkcję biblioteczną za wzorcowe, ponieważ, według moich obserwacji, zdaje się ona podawać wynik najbliższy analitycznemu (kiedy to tylko możliwe).

Skrypt wykorzystuje 4 metody:
  • prostokątów
  • trapezów
  • Simpsona (parabol)
  • Romberga

Pomijając metodę Romberga, w przypadku 3 pozostałych metod przedział, w którym całka ma być wyznaczona, jest dzielony na N podprzedziałów. Skrypt zakłada przy tym, że funkcja, którą mu podamy istnieje i że jest ciągła w każdym punkcie przedziału < a ; b >, gdzie a oznacza dolną granicę całkowania a b - górną.

Metoda prostokątów i coraz dokładniejsze dopasowanie wraz ze wzrostem podziałów:


Credit: Khurram Wadee (https://en.wikipedia.org/wiki/File:Rectangle_rule.gif)

Metoda trapezów:



Skrypt przyjmuje 4 parametry: dolną (a) oraz górną (b) granicę całkowania, ilość podprzedziałów (N) oraz wzór funkcji jednej zmiennej.
Napisany w Perlu. Nie wrzucam tu wszystkich wzorów - jeżeli interesuje Cię ten temat, z łatwością odszukasz je w Internecie. Chciałbym bardziej skupić się na przykładowym rezultacie działania.


(Przypominam, że przyjmuję w swoich rozważaniach wartość metody Romberga jako wzorzec. Mowa o całkowaniu numerycznym, więc operujemy na przybliżeniach.)

Nasunęło mi się kilka wniosków w związku z powyższymi danymi:
  • pomijając metodę biblioteczną Romberga, metoda Simpsona daje najbardziej dokładny wynik
  • czas liczenia (za wyłączeniem metody Romberga) jest mniej więcej liniowy
  • z każdym 10-krotnym zwiększeniem ilości podprzedziałów wyniki stają się o 2 rzędy wielkości dokładniejsze
  • przy znacznie zwiększonej liczbie podziałów metoda prostokątów jest nieznacznie szybsza od pozostałych

To tylko mały "skrawek" zagadnienia. Funkcja, którą wykorzystałem jako przykład jest względnie gładka (zob. wykres). Problemem byłoby policzenie całki oznaczonej "stromej" funkcji, która "bardzo skacze" i do czego wymagana byłaby duża ilość podziałów, co wiązałoby się z wydłużeniem czasu trwania obliczeń. Wykorzystywane podejścia dzielą przedział na równe podprzedziały, bez badania przebiegu zmienności funkcji i "inteligentnego" ich ustalania lub dobierania metody w zależności od tego, jaki funkcja "ma mniej więcej kształt".

Do kodu nie roszczę sobie żadnych praw, możesz z niego korzystać w dowolny sposób, przy czym nie ponoszę odpowiedzialności za to, co nim zrobisz. Na pewno może być napisany lepiej, ale pierwotne założenie (przeważnie prostoty) spełnia.
#!/usr/bin/perl
use Math::Integral::Romberg qw(integral);
use POSIX;
use Time::HiRes qw(time);
use Scalar::Util qw(looks_like_number);

use constant PI => 4 * atan2(1,1);
use constant e => 2.71828182845904523536;

sub wrapper {
 my ($x) = @_;
 eval $funkcja;
}

sub rectangles {
 $lower = $_[0];
 $upper = $_[1];
 $intervals = $_[2];
 $step = ( $upper - $lower ) / $intervals;

 for($x = $lower; $x < $upper; $x += $step){
  $a = $step;
  $b = eval $funkcja;
  $sum += $a*$b;
 }
 return $sum;
}

sub trapezoids {
 $lower = $_[0];
 $upper = $_[1];
 $intervals = $_[2];
 $step = ( $upper - $lower ) / $intervals;

 $temp_sum = 0;
 $overall_sum = 0;
 $iterator = 0; #zliczanie "przebytych" podzialow; ich dlugosc nie musi (i najczesciej nie bedzie) liczba calkowita
 for($x = $lower; $x < $upper; $x += $step, $iterator++){
  $temp_sum = eval $funkcja;
  $overall_sum += ( $iterator==0 ? ($temp_sum/2) : ( $iterator==($intervals-1) ? ($temp_sum/2) : ($temp_sum) ) );
 }
 $overall_sum *= $step;
 return $overall_sum;
}

sub simpsons {
 $lower = $_[0];
 $upper = $_[1];
 $intervals = $_[2];
 $step = ( $upper - $lower ) / $intervals;

 $iterator = 0;
 $k = 0;
 $overall_sum = 0;
 for($x = $lower; $x <= $upper; $x += $step, $iterator++){
  $temp_sum = eval $funkcja;
  if($iterator==0 || $iterator==$intervals){
   $overall_sum += $temp_sum;
  } else {
   $k ^= 1;
   $overall_sum += ($k+1) * 2 * $temp_sum;
  }
 }
 $overall_sum *= $step/3;
 return $overall_sum;
}

sub parse_constants {
 $tempstr = $_[0];
 $tempstr =~ s/pi/PI/g;
 $tempstr =~ s/Pi/PI/g;
 $tempstr =~ s/pI/PI/g;
 #$tempstr =~ s/e/e/g;
 #print "\n $tempstr \n";
 $tempstr = eval $tempstr;
 return $tempstr;
}

sub call_redirector {
 $start = time;
 $sum = $_[0]($_[2], $_[3], $_[4]);
 $end = time;
 ${$_[1]} = ( $end - $start ) * 1000;
 return $sum;
}

sub wypisz_wynik_metody {
 print " metoda ", ($_[0]), "\t: ", (${$_[1]});
 if ($cmpval != 0) {
  $bl_bezwzgl = abs( ${$_[1]} - $cmpval );  
  print "\tblad bezwzgledny: $bl_bezwzgl";
  if ($bl_bezwzgl == 0) { print "\t\t"; }
 }
 print "\t\tczas: ", (${$_[2]}), " ms\n\n ";
 return;
}

$n_args = @ARGV;
if ($n_args < 4) { die "Za malo parametrow.\n"; }

$lower = parse_constants(shift); #$ARGV[0]
$upper = parse_constants(shift); #$ARGV[1]
$intervals = shift; #$ARGV[2]

$not_numeric1 = "Podana wartosc ";
$not_numeric2 = " zdaje sie nie byc wartoscia liczbowa.\n";

if(!looks_like_number($lower)) { die "$not_numeric1" . "dolnej granicy" . "$not_numeric2"; }
if(!looks_like_number($upper)) { die "$not_numeric1" . "gornej granicy" . "$not_numeric2"; }
if(!looks_like_number($intervals)) { die "$not_numeric1" . "ilosci interwalow" . "$not_numeric2"; }

unless ($intervals > 0) { die "Ilosc interwalow musi byc dodatnia.\n"; }

for($i = 0; $i < $n_args - 3; $i++ ) { #n_args minus 3, bo 3 parametry zostały już zdjęte z ARGV
 if ($i==0) {
  $funkcja = shift;
 } else {
  $funkcja = $funkcja . ' ' . shift;
 }
}
$_funkcja = $funkcja;
our $funkcja =~ s/x/\$x/g;

print "\n dolna granica calkowania: $lower\n";
print " gorna granica calkowania: $upper\n";
print " ilosc interwalow : $intervals\n";
print " funkcja: $_funkcja\n";

#tak sie sklada, ze wszystkie wlasciwe funkcje liczace przyjmuja po 3 parametry
$czas_prostokaty = 0;
$suma_prostokaty = call_redirector(\&rectangles, \$czas_prostokaty, $lower, $upper, $intervals);

$czas_trapezy = 0;
$suma_trapezy = call_redirector(\&trapezoids, \$czas_trapezy, $lower, $upper, $intervals);

$czas_simpson = 0;
$suma_simpson = call_redirector(\&simpsons, \$czas_simpson, $lower, $upper, $intervals);

$czas_romberg = 0;
$suma_romberg = call_redirector(\&integral, \$czas_romberg, \&wrapper, $lower, $upper);

our $cmpval = $suma_romberg; #funkcja biblioteczna zwraca bardzo dokladne wartosci; jej wyjscie posluzy jako wartosc wzorcowa

print "\n przyblizona wartosc calki oznaczonej:\n\n ";
wypisz_wynik_metody("Romberga", \$suma_romberg, \$czas_romberg);
wypisz_wynik_metody("prostokatow", \$suma_prostokaty, \$czas_prostokaty);
wypisz_wynik_metody("trapezow", \$suma_trapezy, \$czas_trapezy);
wypisz_wynik_metody("Simpsona", \$suma_simpson, \$czas_simpson);

Tuesday, January 13, 2015

Udało mi się

Jakiś czas temu pisałem o problemie, okoliczności odtworzenia którego nie były trywialne. Chodzi mi o okna/notyfikacje, które poruszają tematykę rzekomo niskiej wydajności komputera, a których nachalność stanowi udrękę. Najpierw zrobiłem patcha (łatkę) do systemu, a potem odkryłem, że w systemie istnieje funkcja pozwalająca na wyłączenie schematu kolorów. Nie przyszło mi do głowy, że Microsoft pozwoliłby ot tak zmienić kompozycję jednym wywołaniem: ma to skutek globalny, przy uruchamianiu "zasobożernych" aplikacji powoduje często zawieszenie się systemu a w niektórych przypadkach uniemożliwia niektórym programom funkcjonowanie (np. Fraps, z tego co mi wiadomo, nie jest w stanie nagrywać bez kompozycji z przeźroczystoscią okien). Ale. Najpierw odkryłem ("złamałem") to okno.



Analizowałem kod w debugerze i ustaliłem, jak trzeba ten proces (dwm.exe) "szturchnąć", żeby to okno się pojawiło. Wystarczy oknu Menedżera okien pulpitu wysłać odpowiednią wiadomość. Pokażę teraz, jak każdy z Was może sprawić, żeby to okno się pojawiło (Windows 7), wysyłając procesowi 3 liczby :). Będzie to też pewnego rodzaju dowód, że z czterech liter sobie tego nie wyjąłem.

Pobierz program WindowHack. Służy do manipulowania oknami, bardzo przydatne narzędzie, moim zdaniem must-have dla każdej osoby zajmującej się programowaniem pod Windows.

Rozpakuj program, uruchom go. Kliknij drugi przycisk od lewej na samej górze (Show available windows).


W oknie poniżej wyszukaj "DWM Notification Window", kliknij prawym przyciskiem myszy i wybierz Get window.


Następnie, wybierz opcję jak na obrazku poniżej:


Pojawi się okno, w którym wpiszesz tylko wartości MSG, WPARAM i LPARAM (pola HWND nie ruszaj, będzie ono miało u Ciebie na pewno inną wartość).


Kliknij "Send Message" i najpewniej pojawi się omawiane na samym początku okno:


Istotnie, w polu LPARAM możesz podać wartości 201, 203, 400, 401 lub 405. Jak nie wierzysz to sprawdź :).

Wracając do meritum. Odkrywszy sposób na błyskawiczne i wygodne wywołanie tego okna, wszystko dalej potoczyło się z górki. Szybko odnalazłem miejsce w kodzie, gdzie zachodzi zmiana schematu. Zrobiłem łatkę, która zapobiega tej zmianie. Potem dowiedziałem się, że system oferuje funkcję wyłączenia tego schematu. Nic nie straciłem poza czasem. Ale dzięki temu mam 100% pewność, że uderzyłem we właściwe miejsce.

Jak wywoła się systemową funkcję zmieniającą kompozycję (lub schemat kolorów, jak kto woli), to znika przeźroczystość okien, w zasobniku systemowym pojawia się taki balon informacyjny:


...którego kliknięcie powoduje otwarcie takiego okna:


Powyższa zmiana często zachodzi, jak uruchomi się "ciężką aplikację" (grę, odtwarzanie wideo bardzo wysokiej jakości). Główną udręką jest fakt, że niektóre z tych powiadomień występują losowo, bez uzasadnienia. Okazuje się, że faktyczne zasoby komputera nie mają znaczenia. Potwierdza to opinia gościa, który twierdzi, że także otrzymuje takie komunikaty; na komputerze z dwoma dwunastordzeniowymi procesorami, 128GB RAM, dwiema kartami Nvidia 670 i dyskami SSD.[1].

Najwięcej czasu zabrało mi wywołanie tego okna i nie mam "przepisu", jak je wywołać, wysyłając procesowi wiadomość.


Tak na marginesie, z mojej analizy wynika, że to okno nie powinno się w ogóle pojawiać. Po prostu jeden z argumentów pewnej funkcji jest wpisany na stałe (ang. hard-coded) i teoretycznie nie ma możliwości, aby się ono "naturalnie" pojawiło. A najśmieszniejsze jest to, że w Internecie są zrzuty ekranu wykonane przez osoby, którym się to okno pojawiło. Magia. Co prawda zmieniłem pamięć procesu tak, żeby łatwo wywoływać sobie to okno, jest to niesamoistny sposób wywołania. Faktyczną kwestię pojawiania się tego okna dalej badam i najprawdopodobniej zabiorę się niedługo do pisania kolejnego programu "badawczego" :).

Wersja beta mojej łatki wygląda obecnie tak:


Może trochę straszyć, ale nie ma się czego bać.
Niedługo zostanie wydana.

Thursday, August 7, 2014

Obrót sprawy

W poprzednim poście pisałem o swoim programie, wyglądzie jednego z jego okien (co było nawet przedmiotem głosowania).

Ufam, że zmiany poprzestaną na tym, co widzisz poniżej:



To "najbardziej pierwszy" z układów, wymyślony jeszcze zanim zacząłem pracę nad programem. Z jakiegoś powodu go odrzuciłem - okazało się, że niesłusznie.

Sunday, August 3, 2014

Cisza

Niby nic tutaj nie dodaję, ale to nie oznacza, że nic nie knuję. :)

Pracuję nad nowym programem. Dokładnego technicznego opisu nie bedę tutaj przytaczał, bo większości z Was będzie pewnie tak samo potrzebny jak reszta badziewia, które wydaję.

System Windows oferuje ustawienia pozwalające na ukrywanie dysków (lub stacji, jak kto woli) w oknie "Mój komputer", administracyjne blokowanie dostępu do wybranych liter dysków (wiadomość w stylu "Skontaktuj się z administratorem systemu").

Oto okno, w którym macie możliwość ukrywania partycji i zabraniania do nich dostępu:


W tym oknie program obsługuje 3 ustawienia systemowe: do ukrywania partycji (Hide), administracyjnego odmawiania dostępu (Prevent access, dosł. zapobiegania dostępowi) i selektywnego wyłączenia autoodtwarzania (Disable Autorun).
Hide i Prevent access mogą Ci się przydać, gdy masz wścibską siostrę/wścibskiego brata i chcesz przed nią/nim ukryć partycję ze swoimi rzeczami albo zabronić do niej dostępu. Nie jest to nie do obejścia, ale znakomita większość użytkowników sobie z tym nie poradzi w przyzwoity sposób.

System oferuje też kilka ustawień dotyczących autoodtwarzania. Mój program obsługuje 2 z takich ustawień: jedno, wyłączające autoodtwarzanie według typów urządzeń, drugie - analogicznie do pierwszych dwóch funkcji, które opisałem - pozwalające na wyłączenie autoodtwarzania na określonych literach stacji dysków. Kto musiał robić "formata" po podpięciu zainfekowanego wirusem pen-drive'a od kolegi to wie, o co chodzi, albo będzie chciał od tego momentu się dowiedzieć.

Autoodtwarzanie to dobra sprawa. Polega ono na tym, że jak podpinasz jakieś urządzenie, system automatycznie "otwiera je". W bardzo dużym skrócie, bo za tym stoi spory mechanizm w systemie i zanim uruchomi Ci się instalator gry komputerowej z płyty, system wykona mnóstwo kodu. Funkcja ta była strzałem w dziesiatkę, dopóki twórcy trojanów i innego złośliwego oprogramowania nie wpadli na pomysł, żeby wykorzystać pen-drivy do infekowania komputerów. Na takim dysku jest plik autorun.inf, który zawiera instrukcje dla Eksploratora Windows, które ten ma wykonać (o ile autoodtwarzanie dla danego typu urządzeń jest włączone). Tylko nie usuwaj teraz histerycznie każdego napotkanego autorun.inf, bo to niekoniecznie musi oznaczać infekcję. Ten plik jest często na różnorakich płytach instalacyjnych i najzwyczajniej w świecie odpala instalatora. Może to trochę przesadzone porównanie, ale noża można użyć albo do zamordowania kogoś, albo do krojenia warzyw na przykład. Tak z tym autoodtwarzaniem, jest dobre, ale jeśli znajdziesz plik autorun.inf na którymś ze swoich pendrivów, to jest on najpewniej zainfekowany. A już na pewno, jeśli ten plik jest ukryty i ma ustawione atrybuty "systemowy" i "tylko do odczytu". Dzisiejsze antywirusy, nawet "najsłabsze", wyłapują tego typu infekcje.

Co jest pierwsza rzeczą, którą robię po świeżej instalacji systemu? Wyłączenie autoodtwarzania dla wszystkich typów urządzeń z wyjątkiem CD-ROM.
Moim programem można to zrobić w 4 kliknięcia.

Okno pozwalające wyłączyć autoodtwarzanie dla poszczególnych typów urządzeń (to, o czym pisałem przy okazji pen-drive'ów):

Żeby wyłączyć autoodtwarzanie tymi 4 kliknięciami, o których wspomniałem, uruchom program (najlepiej jako Administrator). Kliknij przycisk otoczony zielonym prostokątem. Pojawi się okno jak powyżej. Klikniesz "Select recommended", zaznaczą się wszystkie ptaszki bez "CD-ROM". Następnie klikniesz "Apply (NoDriveTypeAutoRun)", pojawi się prośba o potwierdzenie operacji -> klikasz Tak. Jeśli dostaniesz okienko z wykrzyknikiem to coś poszło nie tak (brak uprawnień), w przeciwnym razie okienko informacyjne o sukcesie.

Część z Was pamięta pewnie, jak robiłem ankietę na temat tego, jak program miałby wyglądać. Teraz dochodzę do wniosku, że zmarnowałem sporo czasu właśnie na cackanie się z wyglądem okien.
(Gdyby ktoś sobie myślał, że te ściany z ptaszków robiłem ręcznie... nie, napisałem sobie do tego skrypty, które te okna za mnie wygenerowały, ja musiałem tylko zaprogramować "wzór" :))


Więcej już tego pewnie nie możesz czytać. Jeśli interesuje Cię ten program to tu jest link do wątku forum na jego temat. Program można pobrać stąd albo z tamtego forum.

To by było tyle na dziś.

Sunday, June 1, 2014

Program z Matematycznego Dnia Dziecka

W piątek odbyły się obchody Matematycznego Dnia Dziecka w ZSO, do którego uczęszczam. Nie wiedziałem, jaką konkurencję wymyślić i jakoś tak wyszło, że skończyło się na zamienianiu podanej liczby na mnożenie. Moja konkurencja nazywała się "Szalone iloczyny". Swoją drogą, nie wiedziałem, że kwestia mnożenia w liceum może przysporzyć tyle kłopotu. Tuż po obchodach czułem się trochę zmieszany, bo starałem się jak mogłem, aby być zrozumianym. Darowałbym sobie to całe biadolenie, gdyby nie fakt, że gimnazjaliści poradzili sobie z moją konkurencją lepiej. No ale kim ja jestem, żeby cokolwiek od kogokolwiek wymagać... Poza tym nie muszę wszystkiego rozumieć.
Tyle goryczy, teraz do rzeczy.
Właściwie jedyną zasadą konkurencji była zamiana liczby na mnożenie. Odpowiedzi można było udzielić na jeden z dwóch sposobów: poprzez podanie wylosowanej liczby w postaci iloczynu dwóch jakichś innych liczb albo poprzez podanie rozkładu liczby na czynniki pierwsze. Nie podam teraz punktacji bo jest ona już nieistotna. Wyjaśnię na przykładzie, bo zaraz pewnie przestaniesz czytać.
Wylosowałem liczbę 48.
W sposobie #1 mogę podać jedną z aż 4 możliwości: 2*24 3*16 4*12 6*8.
W sposobie #2 muszę podać 2*2*2*2*3, aby zdobyć punkty.
Program nie uzna odpowiedzi 1*48, bo to haratnięcie w gałę, a nie odpowiedź.
Resztę obostrzeń przybliży Ci screenshot poniżej:

Tyle.
Przykładowy screenshot programu w akcji:

Program losuje 152 liczby złożone nie większe od 200, następnie wybiera z tablicy z wylosowanymi 3 początkowe elementy.
W paczce poniżej program z konkurencji, ten sam program bez ograniczeń czasowych i kod źródłowy.
[Pobierz]

Saturday, March 22, 2014

Szczegółów kilka o stole wigilijnym...

Byłem już kilkakrotnie pytany o stół, który przed chwilą oglądałeś/aś (jeśli trafiłeś/aś tutaj z FB), więc podzielę się z Wami pewnymi ciekawostkami na jego temat i tego, jak był robiony.
Zrobiony jest z odpadów. Nogi to elementy starego stelażu na winogron, który w 2002 roku się złamał i potem do grudnia 2013 leżał w garażu. To prawdopodobnie drewno lipowe, bo bardzo lekkie i się nie kruszy, mimo trudnej przeszłości.

Konstrukcja blatu składa się z 2 ścian regału, które jakimś cudem udało mi się równo złączyć. Z czego ten regał był zrobiony, nie wiem. Wiem tylko, że z drewna iglastego, mogę po zapachu żywicy przypuszczać, że świerkowego.

Wierzchnia część blatu to stara boazeria modrzewiowa, której struktura i gładkość pozostawiały trochę do życzenia. Na zdjęciu poniżej nogi i blat bez wierzchniej części.

Robiony był ręcznie. Deski były cięte ręcznie. Jedynym zmechanizowanym narzędziem użytym do zrobienia tego stołu była ręczna PRLowska wiertarka na korbę. Wkręty były mocowane ręcznie. Powierzchnia była gładzona papierem ściernym, ręcznie. :)

Robiłem go jakieś 2 tygodnie i dało mi to trochę popalić. W końcu szkoła i tego typu sprawy, gdyby doba miała więcej niż 24h to byłoby cacy. Kilka razy zwątpiłem, jak zobaczyłem ile trzeba było się bawić z dopasowywaniem kawałków drewna. Każdy był inny, bo w końcu odpady. Jak idziesz do stolarza to wybierasz co chcesz, ja musiałem kombinować. Stolarzem nie jestem i nie zdawałem sobie nawet sprawy, ile to będzie roboty. No ale jakoś się udało, skończyłem w przeddzień Wigilii. Blat nie jest przysłowiowo równy, ale całość jest masywna i po nałożeniu obrusu detale wykończeniowe można zaniedbać.

Wymiary: 183cm dł. x 92cm szer. x 73cm wys.
Waga: nogi ok. 20kg, blat 35-40kg

Friday, March 21, 2014

Lampka do czytania...

Pewna osoba z mojego najbliższego otoczenia miała (i ma dalej) lampkę do czytania, której mankamentem był klips mocujący. Jak kapitalistycznie utemperowani inżynierowie zaprojektowali, tak ten klips po niedługim czasie się najzwyczajniej w świecie złamał. Lampki jako całości szkoda było wywalić, bo pomijając klips jest porządna. Poświęciłem więc jedną z klamr stolarskich i wykombinowałem takie coś:

Miejsce złączenia z bliska:

I lampka w docelowym miejscu użytkowania:

Zdjęcia robione suszarką, ale oddają istotę sprawy i kto ma zobaczyć to, co powinien zobaczyć, to zobaczy.
Miłego weekendu.