Schemat Hornera WOLNIEJSZY niż zwykłe liczenie wielomianów?!

0

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ć?

1

U mnie Horner działa dużo szybciej.

Taki kod:

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <unistd.h>

using namespace std;

#define PROBLEM_SIZE 1234567890

double plain(double const x, double const * const a, int64_t const n) {
    double result = 0.0;
    clock_t start = clock();
    for (int64_t i = 0; i < n; i++) {
        result += a[n - i - 1] * pow(x, i);
    }
    clock_t end = clock();
    printf("process time spent: %lf s\n", (end - start) * 1.0 / CLOCKS_PER_SEC);
    return result;
}

double horner(double const x, double const * const a, int64_t const n) {
    double result = 0.0;
    clock_t start = clock();
    for (int64_t i = 0; i < n; i++) {
        result = x * result + a[i];
    }
    clock_t end = clock();
    printf("process time spent: %lf s\n", (end - start) * 1.0 / CLOCKS_PER_SEC);
    return result;
}

int main(int argc, char** argv) {
    double * a = new double[PROBLEM_SIZE];
    
    for (int64_t i = 0; i < PROBLEM_SIZE; i++) {
        a[i] = (i + sqrt(i)) * sqrt(i);
    }
    
    double resultPlain = plain(0.33, a, PROBLEM_SIZE);
    double resultHorner = horner(0.33, a, PROBLEM_SIZE);
    
    printf("%lf\n%lf\n", resultPlain, resultHorner);
    
    delete [] a;
    return EXIT_SUCCESS;
}

Daje taki wynik:

process time spent: 78.392118 s
process time spent: 2.639456 s
64745564589967.500000
64745564589967.515625

RUN FINISHED; exit value 0; real time: 1m 30s; user: 490ms; system: 1m 30s
0

Dzięki! Już mi działa. :)

Wynik obliczen:
W(6) = -1

Czas obliczen dla schematu Hornera:
0.465000 sekund(y)
Czas obliczen dla zwyklego liczenia wielomianu:
8.865000 sekund(y)

Zmieniłem po prostu typy zmiennych z float i int na double. Nie mam pojęcia, co to dało, ale muszę o tym poczytać.

1

Z floatami mam identyczną prędkość (co z double'ami).

1 użytkowników online, w tym zalogowanych: 0, gości: 1