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

Odpowiedz Nowy wątek
2016-03-25 12:08

Rejestracja: 3 lata temu

Ostatnio: 5 godzin temu

Lokalizacja: Warszawa

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

Pozostało 580 znaków

2016-03-25 14:21

Rejestracja: 14 lat temu

Ostatnio: 4 godziny temu

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

"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2016-03-25 16:12

Rejestracja: 3 lata temu

Ostatnio: 5 godzin temu

Lokalizacja: Warszawa

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

edytowany 1x, ostatnio: LowSkiller, 2016-03-25 16:21

Pozostało 580 znaków

2016-03-25 16:22

Rejestracja: 14 lat temu

Ostatnio: 4 godziny temu

1

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


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 1x, ostatnio: Wibowit, 2016-03-26 00:30

Pozostało 580 znaków

Odpowiedz

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