Mamy wielomian $W(x)$ w postaci:

$W(x)=a_0+a_1x+a_2x^2+\ldots+a_{n-1}x^{n-1}+a_nx^n$

Możemy go zapisać w postaci:

$W(x)=a_0+x(a_1+x(a_2+\ldots +x(a_{n-1}+xa_n)\ldots))$

Aby wyliczyć wartość wielomianu korzystając z pierwszego wzoru musimy wykonać $n$ dodawań i $\dfrac{n(n+1)}{2}$ mnożeń. Użycie drugiego wzoru pozwala zmniejszyć liczbą mnożeń do $n$; liczba dodawań pozostaje bez zmian.

Zadanie

Należe napisać trzy funkcje wyliczające wartość wielomianu:

1. Metodą bezpośrednią (pętli, korzystamy z funkcji pow()).
2. Metodą bezpośrednią, wyliczając potęgi $x$ metodą kolejnych mnożeń¹.
3. Metodą Hornera².

Metoda Hornera może być zrealizowana w sposób rekurencyjny.

Zadania (funkcje) powinny być dodawane w podanej wyżej kolejności: bezpośrednio z pow(), bezpośrednio z mnożeniem, metodą Hornera, metodą Hornera rekurencyjną. Na koniec można dodać czas obliczeń dla każdego wariantu.

Porównanie czasu obliczeń każdego wariantu

Podstawy opisujące zasady wyliczania czasu obliczeń podane są w Bryku w Dodatku E.

Wykorzystać trzeba funkcję gettimeofday()

Funkcja korzysta ze zdefiniowanej w pliku nagłówkowym sys/time.h struktury struct timeval. Każda zmienna tego typu ma dwie składowe: pierwsza (tv_sec) zawiera liczbę sekund, która upłynęła od początku Epoki, a druga (tv_usec) liczbę mikrosekund od ostatniej pełnej sekundy.

Najprostsze użycie tej funkcji jest takie

Zmienna (struktura) start zawiera aktualny czas jako liczbę sekund (od początku Epoki) i liczbę mikrosekund od ostatniej pełnej sekundy. Możemy to zamienić na mikrosekundy (sekundy mnożymy przez 1000000, czyli milion):

Podobnie trzeba odczytać czas po zakończeniu obliczeń.

Żeby dostać wiarogodne wyniki należy obliczenia powtórzyć kilka razy. Same wywołanie funkcji również powinno być wykonane kilka-kilkanaście tysięcy razy.

Wersja PDF dokumentu…

…jest również dostępna.