Witam,
Chciałbym zapytać, czy ktoś jest w stanie wyjaśnić mi, czemu ta pętla ze schematem Hornera:
for(i=1;i<=st;i++)
{
wynik = x*wynik+a; //wynik = wynik*x+a[i];
}
Działa wolniej niż ta ze zwyczajnym liczeniem wielomianu:
for(i=1;i<=st;i++)
{
wynik = wynik+a*(pow(x,i)); //wynik += a[i]*(pow(x,i));
}
W komentarzu obok są właściwe działania z tablicą wyrazów wolnych. Chciałem tu sprawdzić dla stałych wartości, ale jest tak samo.
Nie mam pojęcia, co jest grane. Schemat Hornera ma przecież mniejszą złożoność mnożenia i powinien wykonywać się szybciej, a jest wolniejszy (np. dla st=109 Horner wykonuje się 230s, a klasyczne 219s; dla mniejszych wartości mam np. 24s dla Hornera i 21s dla klasycznego). Zresztą moim zadaniem jest napisanie sprawozdania z tabelami prezentującymi czasy wykonania tych dwóch algorytmów dla poszczególnych stopni wielomianu i wyjaśnienie dlaczego Horner jest szybszy. Kody programów są praktycznie takie same i różnią się tylko tymi pętlami. Zresztą clock() i tak mam ustawiony tylko na pętlę.
Na razie wnioskuję, że przyczyną może być:
- dziwna architektura komputera(?),
- jakaś mega zoptymalizowana funkcja potęgi, zdefiniowana jako pow() w math.h, która nie liczy się, jak normalna potęga.
Wpływ randomowych współczynników już wykluczyłem, bo dla stałego a jest tak samo.
Czy ktoś ma jakiś pomysł, dlaczego tak może być i jak to naprawić?