[Ratkaistu] c++ja fibonaccin aikavaativuus

[teele]

Kokeilin c++ :n chrono-kirjastoa ja huomasin, että Fibonaccin lukujen laskeminen kestää yllättävän kauan.

Esimerkissä noin 0,6 sekuntia, mutta omalla koneellani jopa yli 2 sekuntia. Ohjelmaa on helppo kokeilla. Lähdekoodi on tässä

Koodia: [Valitse]

#include <iostream>
#include <chrono>
#include <ctime>
 
long fibonacci(unsigned n)
{
    if (n < 2) return n;
    return fibonacci(n-1) + fibonacci(n-2);
}
 
int main()
{
    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();
    std::cout << "f(42) = " << fibonacci(42) << '\n';
    end = std::chrono::system_clock::now();
 
    std::chrono::duration<double> elapsed_seconds = end-start;
    std::time_t end_time = std::chrono::system_clock::to_time_t(end);
 
    std::cout << "finished computation at " << std::ctime(&end_time)
              << "elapsed time: " << elapsed_seconds.count() << "s\n";
}

Käänsin sen komennolla

Koodia: [Valitse]

g++ koe03.cpp -o koe03 -std=c++0x -Wall -pedantic

Olisi mielenkiintoista tietää, kauanko ohjelman suoritus toisilla koneilla kestää ja olsiko jollain käännöskomennon parametreilla vaikutusta asiaan (mitä en kyllä uskoisi).

Oma koneeni on vanha i5 -laite.

[kamara]

Itselläni kesti seuraavasti. (Vanha I7-kone):

Koodia: [Valitse]

$ time ./fibonacci
f(42) = 267914296
finished computation at Sun Feb 21 13:41:37 2016
elapsed time: 3.07565s

real 0m3.078s
user 0m3.076s
sys 0m0.000s


[Lepotila zZ]

Koodia: [Valitse]

System:~/Documents/c$ ./koe03
f(42) = 267914296
finished computation at Sun Feb 21 13:54:22 2016
elapsed time: 1.33544s

Pentium G3258 (@4.5GHz).

[Tomin]

Fibonacciahan ei kannata laskea rekursiolla vaan silmukalla:

Koodia: [Valitse]

long fibonacci(unsigned n)
{
    long a = 0, b = 1, c;
    if (n < 2) return n;
    for (unsigned i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}
Tällöin aikavaativuudesta tulee lineaarinen muuttujan n suhteen ja tilavaativuudesta vakio.

Ylläoleva kirjoitettu omasta päästä, jos siinä on virhe, niin korjatkaa. Ainakin tuo n=42 oli sama kuin aiemmin.

Koodia: [Valitse]

:!./a.out
f(42) = 267914296
finished computation at Sun Feb 21 14:21:48 2016
elapsed time: 4.4443e-05s     

[hillo]

Koodia: [Valitse]

f(42) = 267914296
finished computation at Sun Feb 21 14:19:24 2016
elapsed time: 5.44003s
AMD Athlon(tm) 64 X2 Dual Core Processor 4000+

[kamara]

Fibonacciahan ei kannata laskea rekursiolla vaan silmukalla:

Ellei sitten halua testata muistin/keskusyksikön nopeutta.

[Tomin]

Fibonacciahan ei kannata laskea rekursiolla vaan silmukalla:

Ellei sitten halua testata muistin/keskusyksikön nopeutta.

Totta. Tosin aihe on "fibonaccin aikavaativuus", joten arvelin tätä haettaneen.

[kamara]

Poistin ajanoton C:stä ja ajoin sitten Raspberry Pi:llä, ja se ajoi kyseisen ohjelman käskyllä: (Versio B 512Mt:lla)

Koodia: [Valitse]

$ time fib
Real  0m38.364s
user 0m38.100s
sys 0m0.000s


[nm]

Kyllähän optimoinnilla on vaikutusta (Core 2 Q9550 2,83GHz):

Ilman optimointia (= -O0)

Koodia: [Valitse]

$ g++ fib.cc -o fib -std=c++0x -Wall -pedantic
$ ./fib
f(42) = 267914296
finished computation at Sun Feb 21 13:43:29 2016
elapsed time: 6.27204s
-Os (optimointi binäärin koon pienentämiseksi):

Koodia: [Valitse]

$ g++ fib.cc -o fibOs -std=c++0x -Wall -pedantic -Os
$ ./fibOs
f(42) = 267914296
finished computation at Sun Feb 21 13:43:54 2016
elapsed time: 4.13447s
-O1:

Koodia: [Valitse]

$ g++ fib.cc -o fibO1 -std=c++0x -Wall -pedantic -O1
./fibO1
f(42) = 267914296
finished computation at Sun Feb 21 13:43:37 2016
elapsed time: 3.97295s
-O2 (yleisimmin käytetty optimointitaso):

Koodia: [Valitse]

$ g++ fib.cc -o fibO2 -std=c++0x -Wall -pedantic -O2
$ ./fibO2
f(42) = 267914296
finished computation at Sun Feb 21 13:43:45 2016
elapsed time: 4.6483s
-O3:

Koodia: [Valitse]

$ g++ fib.cc -o fibO3 -std=c++0x -Wall -pedantic -O3
$ ./fibO3
f(42) = 267914296
finished computation at Sun Feb 21 13:43:48 2016
elapsed time: 1.5272s

Yksinkertaisen rekursiivisen toteutuksen aikavaativuus on eksponentiaalinen O(2^n), joten suoritusaika kasvaa hyvin nopeasti mahdottomaksi. Iteratiivinen ratkaisu toimii huomattavasti nopeammin, kuten Tomin näytti, mutta silläkään ei käytännössä päästä lineaariseen aikaan suurilla n:n arvoilla, koska 64-bittisten kokonaislukujen tarkkuus loppuu kesken. GMP:n rajoittamattoman tarkkuuden kokonaisluvuilla voi kokeilla todellista suorituskykyä. Esimerkiksi F(1000000):n laskeminen iteratiivisesti kestää 19 sekuntia omalla koneellani. Tuloksessa on 208988 numeroa. Kasvava lukujen koko johtaa neliölliseen hidastumiseen, joten kovin paljon kauemmas ei päästä järkevässä ajassa, vaan on parempi etsiä apuja fiksummista algoritmeista:
http://www.opimedia.be/DS/onlinedocumentations/severalgos/Fibonacci_cpp/html/index.html
https://www.nayuki.io/page/fast-fibonacci-algorithms

[Lepotila zZ]

Tuo -O3 tiputti koneellani ajankäytön teelen mainitseman esimerkin lukemiin:

Koodia: [Valitse]

$ ./koe03
f(42) = 267914296
finished computation at Sun Feb 21 15:06:04 2016
elapsed time: 0.583469s


[Tomin]

Yksinkertaisen rekursiivisen toteutuksen aikavaativuus on eksponentiaalinen O(2^n), joten suoritusaika kasvaa hyvin nopeasti mahdottomaksi. Iteratiivinen ratkaisu toimii huomattavasti nopeammin, kuten Tomin näytti, mutta silläkään ei käytännössä päästä lineaariseen aikaan suurilla n:n arvoilla, koska 64-bittisten kokonaislukujen tarkkuus loppuu kesken.

Näinhän se on. Tuo toteutus (ei siis algoritmi) käyttää kuitenkin vain long-tyyppiä, joka on kai yleensä 32-bittiä ja ei siis mikään ongelma nykyisille suorittimille. En tosin tiedä mikä on suurin n, jonka tuo suostuisi laskemaan.Se voinee olla yllättävänkin pieni.

https://www.nayuki.io/page/fast-fibonacci-algorithms

En tiennytkään että Fibonaccin voi laskea myös noin, mielenkiintoista.

Tuo -O3 tiputti koneellani ajankäytön teelen mainitseman esimerkin lukemiin:

Koodia: [Valitse]

$ ./koe03
f(42) = 267914296
finished computation at Sun Feb 21 15:06:04 2016
elapsed time: 0.583469s


Tämä taitaa olla se tulos, jota teele haki.

Muokkaus: Mielenkiintoista, omalla koneellani O2 ja O3 eivät juuri eroa toisistaan (1,9 s ja 1,7 s). (O1 oli 2,9 s ja ilman mitään 3,9 s) Prosessorina Intel Haswell U-sarjaa (Core i5-4200U).

[nm]

Näinhän se on. Tuo toteutus (ei siis algoritmi) käyttää kuitenkin vain long-tyyppiä, joka on kai yleensä 32-bittiä ja ei siis mikään ongelma nykyisille suorittimille.

long int on 64-bittinen 64-bittisessä Linuxissa. 32-bittisessä Linuxissa, Windowsissa ja monissa muissa järjestelmissä se on vain 32-bittinen, joten 64-bittisiä lukuja varten on parempi käyttää long long -tyyppiä tai int64_t:tä, joka on tuettu C99:ssä ja C++11:ssä.

En tosin tiedä mikä on suurin n, jonka tuo suostuisi laskemaan.Se voinee olla yllättävänkin pieni.

Suurin 64-bittiseen etumerkilliseen kokonaislukukuun mahtuva Fibonaccin luku on
F(92) = 7540113804746346429

Sitten loppuu tila ja F(93) saa arvon -6246583658587674878

[teele]

Optimointeja en olekaan aikaisemmin kokeillut.

Valinta -O3 pudotti ajan alle puoleen eli 0,96 sekuntiin. O2 kesti 1.16 sekuntia ja O1 1.58 sekuntia. Alkuperaäinen optimoimaton aika oli 2,16 sekuntia.