Cudnovate zgode Fibonaccijevog broja

[Bubba]

Pozdrav svima,

Jucer sam, za relaksaciju i za dusu, operativno slozio jednu od masina iz siga, Quadru 650, da budem precizniji. Nevezano uz temu, ali ne bi covjek vjerovao kako je ta Motorolica unutra zivahna i bez problema vrti apsolutno sav office posao (M$ Office paket, Explorer i slicno).

No, back to the track, gore je trenutno u eksperimentalnoznanstvenofantasticne svrhe OpenBSD 4.2. Zanimljivo je bilo gledati kako sshd kreira DSA kljuc 7:15 min, RSA 3:45 min a RSA1 5:25 min. I dok sam obnevideo od cekanja nakon peripetija s particioniranjem i boot loaderima, pade mi napamet, shale radi, okinem neku obicnu rekurziju za Fibonaccijeve brojeve pa da vidim koliko ce mu trebati da izracuna.

vi, i ->

#include stdio.h
#include stdlib

unsigned int fib(int n)
{
if (n <= 2) return 1;
else return fib(n-1) + fib(n-2);
}

int main (int argc, char * argv[])
{
unsigned int n = strtol(argv[1], NULL, 0), rezultat;
if (argv[1] == NULL)
{
printf ("Unesite n za dobivanje n-tog Fibonaccijevog broja: ");
scanf ("%u", &n);
}
printf ("\nn-ti Fibonaccijev broj je: %u.\n", fib(n));
return 0;
}

Puno racuna, primitivno, eksponencijalna slozenost, baratanje cistim integerima. Motorola number cruncher ocito nije, jer:

$ time ./fib.out 40

n-ti Fibonaccijev broj je: 102334155.
2m47.88s real 2m47.64s user 0m0.15s system

No dobro. To sad ne bi bilo nista strasno, da ja ne pokrenuh i na "Svoj komp", pa u Windblowsima kaze:

C:\>ptime fib.exe 40

ptime 1.0 for Win32, Freeware - http://www.pc-tools.net/
Copyright(C) 2002, Jem Berkes

=== fib.exe 40 ===

n-ti Fibonaccijev broj je: 102334155.

Execution time: 2.040 s

Ajdobro. Nije ko da nisam zadovoljan, obzirom je to izveo 100njak puta brze. No stvar je zasmrdjela kada sam to pokrenuo na Netserveru E60:

korea:/home/bubba# time ./fib.out 40

n-ti Fibonaccijev broj je: 102334155.

real 0m6.122s
user 0m6.120s
sys 0m0.000s

Hmmm. Rezultat ispada previse linearan, ruku na srce, s obzirom da ovaj C2D ima ~3 puta vecu frekvenciju, i 3x brze racuna. Progutam ja to jos nekako, no Athlon XP 1900+ istu stvar izracuna za

C:\>ptime fib.exe 40

ptime 1.0 for Win32, Freeware - http://www.pc-tools.net/
Copyright(C) 2002, Jem Berkes

=== fib.exe 40 ===

n-ti Fibonaccijev broj je: 102334155.

Execution time: 1.786 s

docim je Athlon XP 1700+ zericu sporiji

C:\>ptime fib.exe 40

ptime 1.0 for Win32, Freeware - http://www.pc-tools.net/
Copyright(C) 2002, Jem Berkes

=== fib.exe 40 ===

n-ti Fibonaccijev broj je: 102334155.

Execution time: 1.982 s

Sva mjerenja ponovljena su nekoliko desetaka puta radi standardnih devijacija i nikakva znacajna odstupanja ne postoje. Pokusavsi ga dotjerati do vrha unsignea, probao sam izracunati 47. broj, nadajuci se da bi mozda duzina racunanja mogla anularati i eventualno prevagnuti rezultat u Pentačevu korist, ali avaj:

C2D vs. AXP -> 60.351 vs 50.642

Kompajlirao sam samo na ovom Intelu i to s mingw32 3.4.5. Moze li netko isprobati s kakvim nabudzenim Phenomom ili brend nju kloukanim Penrynom? Ima li itko ideju/objasnjenje?

Eh, da dometnem, nikakvi power saving tu tu ru tu modovi i cuda nisu ukljuceni. Frekvencija je 1.86GHz, vise puta provjerena.

[Elven]

hehe da... vidis to sa Athlonom i njegovim superiornim racunanjem sam ja otkrio sasvim slucajno... dok sam imao Athlon XP 1500+, a frend si je nabavio novi P4 3.0 i isao se kurcit. Kako smo obojica tada studirali matematiku isao se bahatit i rec mi da izracunam neku bolesnu potenciju broja 2 na svom kompu... uglavnom njegov komp je izracunao za cca 25sekundi (ako se dobro sjecam brojki, nhf ako fulam koju sekundu), a moj za cca 18... da ne kazem da je moj radio na 1.333, a njegov na 3.0...

Ali me cudi da i Core2Duo radi te matematicke racunice tako sporo...

[rendula]

heh, sad znam kako oprati nekoga tko mi se pocne kurciti sa super pi rezultatom.

[Bubba]

Autor Elven

Ali me cudi da i Core2Duo radi te matematicke racunice tako sporo...

Relano gledajuci, na ovako primitivnom uzorku (ovdje zapravo ima uzasan broj ADDova), vjerojatno se ni ne moze vidjeti neka prevelika razlika, a K7 ima nesto kraci integer pipeline od Corea. Ipak, 200MHz vise, visestruko brza memorija, cache i ostalo bi trebalo dati, ako nista, barem *isti* rezultat...

Autor rendula

heh, sad znam kako oprati nekoga tko mi se pocne kurciti sa super pi rezultatom.

Zato sam i zamolio nekog od stimera sublatencija da izkompajlira kod i javi rezultate. Da sam pitao koju graficku uzeti ili kako naklokati moj novi Kor a mozda cak i jeli bolje Kvad ili Duo, nebih znao kud' cu sa silnim postovima...

[Dr. Faustus]

Prilikom izvršavanja ovog programa kod dvojezgrenih ili četverojezgrenih procesora koristi se samo jedna jezgra, te zato dolazi do takvih rezultata.
Napravio sam par izračuna: prilikom izračunavanja na Pentiumu D koji radi na 3GHZ vrijeme izračunavanja variralo je u intervalu [1.331 s, 1.416 s], dok je vrijeme izračunavanja na dvojezgrenom procesoru E4500 koji radi na 2.2GHz vrijeme izračunavanja je iznosilo oko 1.8 s (uz zanemariva variranja).
Zaključak je da vrijeme izračuna najvjerojatnije ovisi o trenutnoj frekvenciji jezgre procesora.

[Dr. Faustus]

Osim toga postoje i razlike u arhitekturi procesora. Kod AMD-a memorijska sabirnica je integrirana unutar procesora, dok kod Intela to nije slučaj.
U sintetičkim testovima memorijske propusnosti (npr. Everst i slični) AMD procesori imaju prednost nad Intelovim procesorima.

[Mar]

@Faustus takt nema veze ako je druga arhitektura, a K7 nisu imali integrirani mem. kontroler.

Sve mi smrdi na efikasniju arhitekturu i strukturu cjevovoda te niže latencije.

Bubba, nice find!
Sad bi trebao netko s AMD s939 i nabrijanim RAMom ovo izračunati, baš me zanima zaključak...

[Bubba]

Autor Dr. Faustus

Prilikom izvršavanja ovog programa kod dvojezgrenih ili četverojezgrenih procesora koristi se samo jedna jezgra, te zato dolazi do takvih rezultata.

Pa u tome i jest point.

Napravio sam par izračuna: prilikom izračunavanja na Pentiumu D koji radi na 3GHZ vrijeme izračunavanja variralo je u intervalu [1.331 s, 1.416 s], dok je vrijeme izračunavanja na dvojezgrenom procesoru E4500 koji radi na 2.2GHz vrijeme izračunavanja je iznosilo oko 1.8 s (uz zanemariva variranja).
Zaključak je da vrijeme izračuna najvjerojatnije ovisi o trenutnoj frekvenciji jezgre procesora.

Da, ovisi. No "problemcic" je sto bi omjer trebao biti u korist C2D, a ne AXP-a. Drzim da bi rezultati na A64 bili identicni kao i na K7. Jer nije li malo bizarno da 600MHz brzi procesor, s 8 puta vise cachea, duplo brzom sabirnicom, x puta brzom memorijom i ostalim technobabelom ima jednake performanse kao i 7 godina stari AXP (ili da budem zlocest, 10 godina stara Alpha 21264).

Opet, kazem, mozda test nije meritoran jer je prebanalan. No tim vise, covjek bi ocekivao barem jednake rezultate na istoj frekvenciji.

Autor Dr. Faustus

Osim toga postoje i razlike u arhitekturi procesora.

Ozbiljno?

Kod AMD-a memorijska sabirnica je integrirana unutar procesora,

Kod mojeg nije.

dok kod Intela to nije slučaj.

Jesi siguran?

[Dr. Faustus]

Evo rezultat za Pentium D, 3GHz za fib 47.

C:\Documents and Settings\Administrator\My Documents\ptime>ptime fib.exe 47

ptime 1.0 for Win32, Freeware - http://www.pc-tools.net/
Copyright(C) 2002, Jem Berkes

=== fib.exe 47 ===

n-ti Fibonaccijev broj je: 2971215073.

Execution time: 37.040 s

[immortal]

Konfa Moj komp:
marko@Shkatula:~/temp/true_temp$ uname -a
Linux Shkatula 2.6.22-14-generic #1 SMP Tue Feb 12 07:42:25 UTC 2008 i686 GNU/Linux
marko@Shkatula:~/temp/true_temp$ vi fibb.c
marko@Shkatula:~/temp/true_temp$ gcc -o fibb -Wall fibb.c
fibb.c: In function ‘main’:
fibb.c:12: warning: unused variable ‘rezultat’
marko@Shkatula:~/temp/true_temp$ ./fibb
Segmentation fault (core dumped)
marko@Shkatula:~/temp/true_temp$ time ./fibb 40

n-ti Fibonaccijev broj je: 102334155.

real 0m1.935s
user 0m1.876s
sys 0m0.008s
marko@Shkatula:~/temp/true_temp$