Fibonaci


#1

U zadatku Fibonacijev podniz u Uvodu u algoritme sam primetio da su mi svi test primeri OK samo tri zadnja TLE, kada sam ubacio https://pastebin.com/rdzEBDCi kod izbacio mi je TLE, prakticno je nemoguce napraviti program koji zadovoljava ovaj uslov ako samo za input prekoraci TLE, probao sam i sa scanf isto izbacuje TLE.
Mislim da trazeno vreme nije u redu.


#2

Koliko ja znam, new se izbegava jer je veoma sporo, da nije zbog toga TLE?


#3

TLE ce dobiti i bez dinamicke alokacije, problem je u pretvaranju tipova.

for(unsigned short i = 0; i < n; ++i)

n je unsigned int, i je unsigned short. U svakom ciklusu se tip od i pretvara u unsigned int, sto izaziva TLE.
Ako eksplicitno castujes, dobije se isto.
Ovako ce valjati. Unsigned short je svejedno premali da bi cuvao 10.000.000:

for(unsigned int i = 0; i < n; ++i)

edit:

Vreme se trosi samo kada pretvaras iz manjeg tipa u veci (npr. iz short u int).
To je zato sto short cuva 2 bajta a int 4, pa onda ovi novi bitovi moraju prvo da se popune.
Kada pretvars iz veceg u manji, npr. iz int u short, onda se veci bitovi prosto ne gledaju.
Ako ubacis:

for(unsigned short i = 0; i < (unsigned short)n; ++i)

neces dobiti TLE, mada zadatak nece proci za 100% test primera.


#4

Hvala puno izbavivalo mi je TLE za tri zadnja primera i nisam znao sta ne valja 10 kodova sam pisao ispravljao sam na drugim mestima short u int ali ovde sam zaboravio… sad je sve OK.


#5

Problem jeste u tome što je i tipa unsigned short, ali TLE se ovde ne javlja zbog konverzije tipova (koja, čak i u slučajevima kada menja vrednost broja, obično “košta” samo jednu procesorsku instrukciju i neće drastično usporiti program).

U većini slučajeva, unsigned short je tip koji sadrži neoznačene brojeve dužine dva bajta (“u većini” jer standard ne garantuje tačnu širinu tipa, ali svi popularni kompajleri se ponašaju isto). Samim tim, u promenljivu tipa unsigned short možemo upisati broj u intervalu [0, 2^{16} - 1], tj. najviše 65535. Ako je rezultat izračunavanja izraza veći od ove granice, dolazi do “overflow-a” i dobijamo rezultat kao da su brojevi poređani u krug – rezultat 65535 + 1 će biti 0.

Zbog toga, ako je n veće od 65535, petlja

for(unsigned int i = 0; i < n; ++i)

je beskonačna. Brojač i će uzimati vrednosti od 0 do 65535, pa onda opet od 0 do 65535, i tako dalje… U svakom trenutku će važiti $$, tako da se petlja neće prekinuti.

Svakako, rešenje ovde jeste da se tip i promeni u int (ili unsigned int) da ne bi došlo do overflow-a.


#6

Da, to ima vise smisla.
Nisam znao da integer overflow spada u undefined behaviour, bio sam ubedjen da program u tom slucaju izbacuje error. Hvala na ispravci!

Ipak stojim iza toga da konverziji tipova nije mesto u samoj petlji, pogotovo ako se petlje granaju i pogotovo ako je u pitanju pretvaranje izmedju celobrojnog tipa i decimalnog - jer ono “kosta” mnogo vise (naravno u zavisnosti od procesora) od jedne instrukcije.


#7

Integer overflow jeste nedefinisano ponašanje, ali samo za označene tipove (za unsigned tipove ovo “kružno” ponašanje je definisano standardom). Za označene brojeve je ponašanje obično isto, ali kompajleru je dozvoljeno da uradi bilo šta i moderni kompajleri ovo koriste za optimizacije – ponekad se i na takmičenju nekome ovo desi pa izgubi poene.

Slažem se da retko ima potrebe za konverzijom u takmičarskim programima (obično je na raspolaganju dovoljno memorije da nema potrebe za kraćim tipovima), ali ne zbog efikasnosti, već samo da se ne bi dešavale slučajne greške. Čak i konverzija int u double je samo jedna instrukcija na modernim procesorima (i kompajleri ovo stvarno koriste), tako da ovo nema potrebe izbegavati zbog efikasnosti, ali opet nema ni potrebe da kod bez potrebe komplikujemo.