FR_08_13 - Matematostenes i funkcje trygonometryczne

Jest kilka zadań, które nie akceptują -0 i niestety, ale to na implementującym, a nie na autorze ciąży odpowiedzialność, żeby o tym pamiętać. W razie problemów zawsze należy sprawdzić forum.

Jeżeli ktoś w danej chwili walczy o AC (a nie o czas 0.00 albo najmniejszą liczbę zgłoszeń do uzyskania AC) to w przypadku czegokolwiek zmiennoprzecinkowego wysyłamy kolejne zgłoszenia. Pierwsze to pierwszy epsilon i nieobsłużone -0.0, drugie to pierwszy epsilon ale obsłużone -0.0, trzecie to kolejny epsilon i nieobsłużone -0.0, …

a przynajmniej ja nigdy nie przejechałem się na tej taktyce, choć wymaga ona cierpliwości.

Jeżeli ktoś ma tzw klapki na oczach i jest zapatrzony tylko w AC i pierwszą stronę rankingu na SPOJ’u [np ja] to tak taka taktyka jest godna polecenia.

BTW
Ale przecież tu nie tylko o to chodzi. Istnieje życie poza Spojem [Fraktalem, CodeChef… itd] i już chociażby na PA [Potyczki Algorytmiczne, Olimpiady Inforematryczne itd] na takiej taktyce przejedziesz się na 100% [może nawet 111% ]

A więc jak …?
Np
Generujesz własny/e testy i testujesz.
Analizujesz działanie swojego kodu.
Sprawdzasz poprawność jego działania
…
A jeżeli już raz zdarzyła Ci się taka wpadka, taki problem, to powinieneś już wiedzieć [do końca świata i jeden-dwa dni dłużej] jak z nim postępować w przyszłości, a nie znowu wysyłać zgłoszenia metodą prób i błędów, aż się uda a potem promować taką metodę na forum.

Achtung! Spam!

Gdzieś kiedyś i dawno temu zarazem znalazłem pracę naukową4 w stylu “double i float - czy powinno się o tym uczyć w szkole i wymagać tego na konkursach”. Autor podał przykład: rzekomo kultowy (nie wiem, nie jestem po profilu informatycznym) dowód “potęgi” programowania rozwalającego wszystko co żmudne na lekcjach matematyki. Dowód polegający na rozwiązaniu równania kwadratowego. Jak wiadomo pierwiastki (równania, ale też kultowej w ogólniakach delty) mogą być “dzikie” i uwzględnienie ułamków jest jak najbardziej logiczne. Od takie równanie (x-sqrt(2))(x+sqrt(17))=0 po sprowadzeniu do postaci ax^2 + bx + c = 0 wymaga double/float już przy wczytywaniu współczynników liczbowych.

Autor pokazał, że używanie double jest szkodliwe dla uczniów. (Na marginesie: na double wyłożył się m. in. Mirosław Zelent, więcej info tu: JSUMDUZE - Dodawanie. Zwracam uwagę, że choć jeden zainteresowany jego kursami przyjął, że jak unsigned long long int to za mało, wystarczy użyć long double i będzie wszystko liczyć ok). Podał w tym celu kilka przykładów, z których najlepiej pamiętam równanie kwadratowe z takimi współczynnikami, że błąd względny obliczeń rozwiązań tego równania wynosił… sporo a także pętlę while(x > 0.0), gdzie x było typu double i było dekrementowane o 0.1 w pętli. Autor pokazał, że w zależności od kompilatora i kilku innych czynników taka pętla daje różne wyniki. W każdym przypadku wyjaśnił dlaczego tak jest i jeżeli było to możliwe podał prawidłowy sposób rozwiązania zadania.

Aby dalej nie spamować: autor jest zdania, że floaty i double powinny być w szkole ciekawostką, a na konkursach informatycznych najlepiej, aby (prawie) w ogóle ich nie było. Uważa tak, gdyż:

1. double nie dają dokładnych wyników, co zresztą już napisałem. W związku z tym sprawdzarka musi uwzględnić pewną niedokładność obliczeń (jaką? dlaczego taką a nie inną? jak dokładności wpływają na złożoności obliczeniowe? co jak w danym języku obliczenia zmiennoprzecinkowe są zrobione tak a w innym siak co powoduje różnicę w czasie działania funkcji typu sin()?)
2. przy bardziej złożonych obliczeniach na double autorzy zadań nie będą w stanie wykazać poprawności swoich algorytmów ze względu na różne złośliwości liczb zmiennoprzecinkowych, albo zajmie im to mnóstwo czasu i omówienie jednego zadania na 100 stron nie będzie miało żadnego sensu. Jednocześnie samo użycie takich liczb de facto utrudni wyłącznie implementację, a tok rozumowania prowadzący do optymalnego algorytmu będzie taki sam. Utrudnienie implementacji może sprowadzić wiedzę potrzebną do rozwiązania zadania do poziomu akademickiego wzwyż (wszak minimalizowanie błędu obliczeń na podstawie matematyki a nie zgadywania epsilonów to nie jest elementarna matematyka ani informatyka), co zresztą autor pokazał już na przykładzie rozwiązania równania kwadratowego
3. jeżeli autorzy dołożą wszelkich starań i stworzą dobre zadanie (co zajmie im ileś razy więcej czasu, gdy np. metrykę Manhattan zastąpimy metryką euklidesową) odporne na problemy liczb zmiennoprzecinkowych, z łaskawymi dokładnościami rozwiązań itd. to ostatecznie zadanie będzie promowało uczestników, którzy nie posiadają wiedzy potrzebnej do jego prawidłowego rozwiązania. Uczestnicy tworzący epsilony i szukający stabilnych numerycznie algorytmów będą tracili cenny czas a osoby kodujące “na pałę” rozwiążą zadanie szybciej nawet nie wiedząc, ile roboty odwalili za nich autorzy

Ostatecznie autor pochwalił zadania Międzynarodowej Olimpiady Informatycznej. Podał kilka przykładów, gdzie decyzja o ograniczeniu się do liczb całkowitych doprowadziła do powstania zadań ciekawych i trudnych algorytmicznie, a nie numerycznie, a gdyby przejść na liczby typu double to ich rozwiązanie byłoby niemożliwe w czasie trwania konkursu. Polskiego podwórka niestety nie kojarzę Z cytatów: OI 151: “W obliczeniach komputerowych (…) staramy się jednak unikać stosowania liczb zmiennoprzecinkowych (…). W obliczeniach na zmiennoprzecinkowych wartościach (…) szczególnie z wykorzystaniem tak złożonych funkcji, jak odwrotne funkcje trygonometryczne, trudno bowiem uniknąć błędów zaokrągleń. Ich konsekwencją mogłaby być na przykład niewłaściwa kolejność w posortowanym ciągu punktów (…) [BTW sam się na tym wyrżnąłem i zadanie http://pl.spoj.com/problems/FR_09_15/5 mogłem mieć zaliczone od razu na FRAKTALu, ale na siłę dopasowywałem EPS, który wystarczyło… usunąć. Albo odpowiednio mocniej niż sądziłem pomniejszyć, być może zrobić to bez liczb zmiennoprzecinkowych (robiłem to jako któreś tam zadanie pod presją czasu i nie myślałem nad tym głębiej) - dop. red.]. (…) Wobec wcześniejszych uwag na temat arytmetyki zmiennoprzecinkowej, nie powinno nikogo dziwić, że rozwiązanie oparte o metodę I [obliczenia zmiennoprzecinkowe - dop. red.] nie zostało w ogóle zaimplementowane. W metodzie tej bowiem wielokrotnie zachodzi potrzeba operowania na liczbach rzeczywistych (pojawiają się w nim ułamki - na przykład przy wyznaczaniu parametrów prostej (…) czy pierwiastki kwadratowe), co może powodować problemy z dokładnością.”. Ba! Syllabus IOI z 2009 roku jasno wyklucza z zakresu zainteresowań olimpijskich: “Excluded: Real and complex numbers, general conics (parabolas,
hyperbolas, ellipses), trigonometric functions”, powołując się na wspomnianą pracę badawczą.

Przepraszam, jeżeli zostałem tak zrozumiany. Jak najbardziej nie polecam metody pałowania zadań (chyba, że jako ciekawy eksperyment np. w celu sprawdzenia, czy autor dobrze dobrał testy albo sprawdzenia jakiegoś rozwiązania randomizowanego). Popieram tylko i wyłącznie używanie metod znajdujących się w zasięgu swoich możliwości a nie porywanie się z motyką na Słońce. Trudno sprawdzać poprawność działania kodu przy problemach typu dodatnie i ujemne zera (na start), na które uwagę zwróciła @yula, a dalej - dokładność, np. czym różni się liczba naturalna od nieskończoności. Ambitniejszym i niedowiarkom na różnicę między liczbą naturalną a nieskończonością polecam obliczenie:

#include <iostream>
#include <cmath>

using namespace std;

int main() {
	double x = 100000000.0;
	
	cout << 1.0 / (sqrt(x * x + 1.0) - x) << endl;
	return 0;
}

Jeżeli ktoś ogarnia tematykę obliczeń numerycznych to myślę, że nawet testować większości zadań z double na SPOJu nie ma po co - wszak to trywialne i od razu widać jak to zakodować

Tyle jeśli chodzi o moje zdanie na temat wartości testowania algorytmów, w których występuje double. Jeżeli ktoś wygeneruje 100 testów i przeliczy je ręcznie w sposób bezbłędny (na kartce ciężko o błędy precyzji) to ok. Czas skomentować:

Nie, nie przejadę, bo zadań z +/- zero albo long double tam po prostu nie będzie Wspomniane przeze mnie zadanie z 15 OI zawiera informację, że: “Okazuje się, że pole trójkąta lub trapezu o wierzchołkach w punktach o całkowitoliczbowych współrzędnych musi być całkowitą wielokrotnością 1/2. Dzięki temu, wszystkie obliczenia (…) mogą być wykonywane na liczbach całkowitych, a dopiero na samym końcu trzeba wynik podzielić przez 2. To spostrzeżenie wyjaśnia także, dlaczego w zadaniu wystarczy wypisać wynik z dokładnością do zaledwie jednej cyfry po przecinku.” i na tym kończy się temat double itp. na wspomnianych konkursach

A ponieważ moje pisanie (być może słusznie) zostało uznane za:

więc to wszystko co mam do powiedzenia i nie odpisuję już na komentarze dotyczące mojego postu Krytyka mile widziana, każdy potem przeczyta moje i innych wypociny a następnie zrobi co uzna za stosowne ponosząc tego konsekwencje

Brawo ja, wpadłem na rozwiązanie sprytne kiedy juz dostałem AC.
Chociaz raczej wypadałoby nazwać to oszustwem, a nie sprytnym rozwiązaniem…

Dodam tylko że liczenie Taylorem przechodzi przy minimum 8 wyrazach każdego szeregu.

Masz na myśli wzór Eulera? Nie wydaje mi się by to było oszustwo. Nie omija to ograniczeń narzuconych przez autora. Co do rozwijania w szereg Taylora to ja rozbiłem dwa rozwinięcia - jedno siedem wyrazów a drugie sześć wyrazów.

Nie chodzi o wzór Istnieje pewien trywialny sposób.

No, to ja go nie wymyśliłem. Wczoraj (chociaż to chyba było już dzisiaj ) zrobiłem to zadanie wykorzystując wzór Eulera. O dziwo czas wykonania był dłuższy niż wcześniej przy rozwijaniu w szereg Taylora.