Getallen van Fibonacci berekenen.

[Rogier]

Merk op dat die

Code: Selecteer alles

while (p<=n) p+=p;

de hoogste bit van n bepaalt, waardoor de recursie overbodig wordt, en dat geeft een stuk minder overhead.

Beide while loopjes zijn uiteraard

\({\cal O}(\log(n))\)

.

[Vladimir Lenin]

Die percentjes zijn volgens mij gewoon achtergrondsbewerkingen die bijvoorbeeld een besturingssysteem uitvoeren, waardoor het programma een beetje afgeremd wordt, en zijn inderdaad verwaarloosbaar, volgens mij zijn compilers wel meestal slim genoeg om recursie om te zetten naar while-lussen. Volgens mij zou de eerste while lus nog een optimalisatie kunnen krijgen met een logaritme, al hangt dat ook weer af van de CPU instructie-set volgens mij (hardware werkt altijd sneller dan software (als het natuurlijk om hetzelfde algoritme gaat)). dus:

\(p:=\lceil \log_2(n)\rceil\)

EDIT: @Rogier: klopt die code van die while wel, volgens mij gaat p net één bit hoger dan n. p verdubbelt immer iedere keer (wat je zeer mooi uitwerkt, geen vermenigvuldiging, spaart de processor). Maar je geraakt pas uit de while wanneer p > n, dus de eerste 1 bit van p, is de laatste bit van de rij 0-en van n.

[Rogier]

Zie de n-- aan het begin. En zie resultaat als je de code zelf probeert

[Vladimir Lenin]

srry, had ik moeten zien, al moet ik zeggen dat de beschrijving van je vorig bericht die niet helemaal compleet was. Maar dat is geen excuus. Ik ben zo te zien weer nog altijd niet goed wakker. Ik ga eens wat koffie drinken.

[Cycloon]

volgens mij zijn compilers wel meestal slim genoeg om recursie om te zetten naar while-lussen.

Waarom zou een compiler dat willen doen? Sowieso moet hij dan meestal de hele zaak omzetten naar een stack systeem, terwijl functieaanroepen sowieso al neer komen op het opvullen van het stackmechanisme in je computer. Of hier echt snelheidswinst valt door te boeken betwijfel ik sterk.

[Rogier]

Waarom zou een compiler dat willen doen? Sowieso moet hij dan meestal de hele zaak omzetten naar een stack systeem, terwijl functieaanroepen sowieso al neer komen op het opvullen van het stackmechanisme in je computer. Of hier echt snelheidswinst valt door te boeken betwijfel ik sterk.

Dat ligt maar net aan de recursierelatie, ik heb best vaak gezien dat een recursieve oplossing in eerste instantie veel makkelijker lijkt, maar later blijft dat het net zo goed in een loopje kan, zonder alles bij iedere iteratie een keer op de stack te zetten.

Zie bijvoorbeeld ook de laatste twee versies van die matrix methode die ik gepost heb: van dit (recursief) naar dit (niet recursief). Niks stack (in de tweede variant zijn die a,b,c,enz variabelen toevallig lokaal, maar die mogen ook globaal en/of static zijn).

[Vladimir Lenin]

Je kan volgens mij iedere recursie als while schrijven. Daar je bij recursie altijd een voorwaarde krijgt, krijg je dus iets als volgt:

Code: Selecteer alles

public Type Methode (ParameterType1 t1, ParameterType2 t2,...) {

   ...

   if(voorwaarde) {

	  Methode(f(t1),f(t2),...);

   }

}

kan je makkelijk schrijven als

Code: Selecteer alles

public Type Methode (ParameterType1 t1, ParameterType2 t2,...) {

   boolean bool = true;

   while(bool) {

	  ...



	  t1 = f(t1);

	  t2 = f(t2);

	  t3 = ...



	  bool = voorwaarde;

   }

}

[Cycloon]

Dat ligt maar net aan de recursierelatie, ik heb best vaak gezien dat een recursieve oplossing in eerste instantie veel makkelijker lijkt, maar later blijft dat het net zo goed in een loopje kan, zonder alles bij iedere iteratie een keer op de stack te zetten.

Ja ok, in sommige simpele gevallen waar de programmeur niet voor de beste code gaat kan het mss wel iets uitmaken. Maar zouden compilers er ook toe in staat zijn om iets complexere recursieproblemen op te lossen met while lussen? Ik vrees er voor. Mijn kennis over compilers is nog vrij beperkt, dus mss kan ik toch nog verbaasd worden door compilertechnieken

Je kan volgens mij iedere recursie als while schrijven.

Natuurlijk kan je dat altijd, maar in bepaalde situaties moet je gewoon het stackmechanisme van je processor nabootsen, en of je dat sneller in software kan dan in hardware (welja hardware...) betwijfel ik.

[Vladimir Lenin]

een compiler kan vanalles zolang er geen algebra bij komt kijken, dus als je inderdaad in je code wat zou gaan goochelen met variabelen kan ik me inbeelden dat dat arme programma de kluts kwijtraakt ( ) en daarom zijn compilers eigenlijk ook niet veel verandert. In sommige gevallen kunnen ze optimaliseren, maar meestal wordt met optimaliseren bedoelt dat ze de code zelf niet meer in ere moeten laten. Dat heeft tot gevolg dat ze beter pipelining technieken criëren, en bijvoorbeeld veel gevraagde berekeningen naar buiten brengen: voorbeeld:

Code: Selecteer alles

for(int i = 0; i < 20; i++) {

   j += m*n;

}

wordt door een compiler meestal vervangen door:

Code: Selecteer alles

int k = m*n;

for(int i = 0; i < 20; i++) {

   j += k;

}

al vraag ik me af of we nu niet een beetje off-topic gaan.

In een boek "Write Great Code: Part I understanding the machine" wat ik nu aan het lezen ben, staat er dat een compiler van vandaag nauwelijks betere code oplevert dan een compiler van pakweg 10 jaar geleden.

Het enige wat misschien verandert is, is dat er nu ook in enkele compilers een lijst met belangrijke algoritmen en hun optimalisatie zit, als bijvoorbeeld de compiler ziet dat je selectionSort gebruikt kan het zijn dat hij dat inwendig omzet naar QuickSort

EDIT: Nee, nee, hardware levert normaal altijd beter (sneller) resultaat. Omdat software vereist dat er verschillende stappen bij komen kijken in de processor, vraagt dit dus nog een organisatie in de processor, terwijl wanneer er een module is die dat doet, deze maar een tick in beslag neemt.

[Rogier]

voorbeeld:

Code: Selecteer alles

for(int i = 0; i < 20; i++) {

   j += m*n;

}

wordt door een compiler meestal vervangen door:

Code: Selecteer alles

int k = m*n;

for(int i = 0; i < 20; i++) {

   j += k;

}

VS haalt heel die for loop weg en maakt er meteen j += 20*m*n van

(en die factor 20 zelfs nog met wat lea instructies i.p.v. een normale imul)