Obfuscated C: De Fibonacci-reeks

[rollebol]

Wie zet dit om naar code die werkt op Intel-processoren?

Aangezien Gijs en ik net een practicum moesten maken met uitsluitend leestekens in C, zijn we er maar even voor gaan zitten. We mochten ook geen spaties of andere whitespace gebruiken, jullie dus ook niet. Dit is wat wij hebben gemaakt, het laat de eerste paar Fibonacci-getallen zien, met een recursieve aanroep van de functie 'return (i-1)+(i-2)'.

Is een PC nu little endian of big endian? Anyway, dit programma werkt op Mac, SPARCs enzovoort. Oh, het werkt misschien ook wel op de Palm.

Als uitdaging voor jullie: Maak het geschikt voor Intel-architecturen. Je moet ergens bij de << iets veranderen.

code:

__(____(________)){____(______);______^=______;______++;_______(________?(________==______?________:__(________-______)+__(________-______-______)):________);}_(){____(_____),______,_________,__________,___________,____________,_____________,______________,_______________;_____^=_____;______=++_____;_____<<=(______<<______<<______)+______;_____+=______<<______<<______<<______<<______;_________=(__(______^______)+_____);__________=(__(______)+_____);___________=(__(______<<______)+_____);____________=(__((______<<______)+______)+_____);_____________=(__(______<<______<<______)+_____);______________=(__((______<<______<<______)+______)+_____);_______________=(__((______<<______<<______)+(______<<______))+_____);_________<<=______<<______<<______<<______;__________<<=______<<______<<______<<______;___________<<=______<<______<<______<<______;____________<<=______<<______<<______<<______;_____________<<=______<<______<<______<<______;______________<<=______<<______<<______<<______;_______________<<=______<<______<<______<<______;___(&_________);___(&__________);___(&___________);___(&____________);___(&_____________);___(&______________);___(&_______________);}

Je moet de Makefile er ook bij hebben, want zo briljant zijn we ook weer niet.

code:

_: _.c
      gcc -o _ _.c -D_=main -D___=printf -D____=short -D_______=return

Veel succes, ik ben benieuwd naar jullie resultaten.

[ACM]

Een pc is net andersom als een sparc, dus als de sparc big endian is (dacht het wel?) is de intel little endian.

* ACM vindt de code er wel leuk uitzien.
Maar wat is het nut van zo'n opdracht

[rollebol]

Je kan hem ook even downloaden op http://gene.wins.uva.nl/~gwkunze/

[Gerco]

Ja, ziet er leuk uit, maar ik zie het nut niet. Kan iemand hier een lichtje op laten schijnen misschien?

[rollebol]

Een pc is net andersom als een sparc, dus als de sparc big endian is (dacht het wel?) is de intel little endian.

Ik geloof je op je woord, ik haal het altijd door elkaar. Wij moesten in ieder geval gedoe uithalen om een integer om te zetten naar een string, en dat hoeft op een PC niet, dus komt de minst significante toestand op een PC eerst.

* ACM vindt de code er wel leuk uitzien.
Maar wat is het nut van zo'n opdracht

Het was niet zo'n nuttige opdracht, het was de eerste vraag die als inleiding was bedoeld, maar wij hebben ons er uitstekend de hele ochtend mee vermaakt.

Nou ja, hele ochtend, een uurtje misschien.

[rollebol]

Even voor de goede orde: Het is inderdaad totaal nutteloos.

[Soultaker]

Als het geldige ANSI-C is werkt het vast ook wel op Intel processoren (of elke andere machinearchitectuur).

[Verwijderd]

wtf is dit dan weer

[Gerco]

Op donderdag 18 april 2002 12:25 schreef Soultaker het volgende:
Als het geldige ANSI-C is werkt het vast ook wel op Intel processoren (of elke andere machinearchitectuur).

Als je gaat bitshiften is het wel degelijk belangrijk in welke volgorde de bytes staan.:+

[rollebol]

Als het geldige ANSI-C is werkt het vast ook wel op Intel processoren (of elke andere machinearchitectuur).

Nee hoor, dit is prima ANSI-C code. Nou ja, goeddeels. Het probleem met het verschil tussen Intel en de rest van de wereld heeft niets met ANSI-C specifiek te maken, maar met het feit dat een integer in het geheugen als meerdere bytes wordt gezien, een array van bytes, zeg maar. En een string is ook een array van bytes. Op Intel ziet een integer in het geheugen er anders uit dan op Macintoshes, Suns, nou, eigenlijk anders dan bij alle andere architecturen.

Printf wil als eerste parameter een pointer naar een character array (een string zegmaar) en wij geven hem een pointer naar een integer. Hij ziet het verschil niet, hij denkt 'pointer is pointer'.

[FlowDesign]

Ik heb hier niet echt verstand van ofzo,
ben nog voor aan het leren namelijk.

Maar ik leer nu op de Universiteit in Tilburg Java programmeren, en daar hebben we wel een keer die Fibonacci-reeks in Java geprogrammeerd. (Althans, de docent deed het ff voor om proberen uit te leggen waarom recursie sneller werkt dan iteratie, maar dit terzijde )

Wat ik dus eigenlijk wil zeggen is, als je het in Java programmeerd dan werkt het toch op ieder platform?
Maar dit was natuurlijk niet jullie opdracht. (te simpel zeker?)

[Verwijderd]

Heej Frank, volgens mij heb ik 'm goed zo

code:

__(____(________)){____(______);______^=______;______++;_______(________?(________==______?________:__(________-______)+__(________-______-______)):________);}_(){____(_____),______,_________,__________,___________,____________,_____________,______________,_______________;_____^=_____;______=++_____;_____<<=(______<<______<<______)+______;_____+=______<<______<<______<<______<<______;_________=(__(______^______)+_____);__________=(__(______)+_____);___________=(__(______<<______)+_____);____________=(__((______<<______)+______)+_____);_____________=(__(______<<______<<______)+_____);______________=(__((______<<______<<______)+______)+_____);_______________=(__((______<<______<<______)+(______<<______))+_____);___(&_________);___(&__________);___(&___________);___(&____________);___(&_____________);___(&______________);___(&_______________);}

Deze doet het prima op Intel(TM) Architecturen
Wel erg leuk verzonnen trouwens!

[RickN]

Op donderdag 18 april 2002 12:37 schreef FlowDesign het volgende:
Althans, de docent deed het ff voor om proberen uit te leggen waarom recursie sneller werkt dan iteratie, maar dit terzijde

offtopic:
Docent moet zelf maar eens terug naar school denk ik

[Gerco]

Op donderdag 18 april 2002 14:25 schreef RickN het volgende:
Docent moet zelf maar eens terug naar school denk ik

Misschien bedoelde 'ie wel dat het sneller programmeert. Het verschil in runtime is meestal niet erg groot, maar het lijkt me erg sterk dat optimale recursie sneller is als optimale iteratie

[D2k]

Op donderdag 18 april 2002 12:13 schreef ACM het volgende:
Een pc is net andersom als een sparc, dus als de sparc big endian is (dacht het wel?) is de intel little endian.

* ACM vindt de code er wel leuk uitzien.
Maar wat is het nut van zo'n opdracht

&ltot maar leuk om te weten ;)>
SPARC en IBM mainframes Big Endian, INTEL little endian

</ot maar leuk om te weten ;)>

[ACM]

Op donderdag 18 april 2002 15:03 schreef Gerco het volgende:
Misschien bedoelde 'ie wel dat het sneller programmeert. Het verschil in runtime is meestal niet erg groot, maar het lijkt me erg sterk dat optimale recursie sneller is als optimale iteratie

Mja, over het algemeen wordt recursie geoptimaliseerd naar iteratie, dacht ik
(ALS het geoptimaliseerd wordt, that is)

[RickN]

Op donderdag 18 april 2002 15:03 schreef Gerco het volgende:

[..]

Misschien bedoelde 'ie wel dat het sneller programmeert.

Dat zal et zijn ja. Als het probleem er zich voor leent ben ik op zich ook wel een groot voorstander van recursie...

[Soultaker]

Misschien bedoelde 'ie wel dat het sneller programmeert.

Ach, een docent die z'n studenten stimuleert snel te programmeren doet ook iets fout. Je kan studenten beter leren goed te programmeren; met een beetje mazzel doen ze dat dan ook nog, terwijl ze zo snel mogelijk programmeren vanzelf wel doen.

Ik kan me trouwens ook geen geval voorstellen waarin recursie efficienter is dan iteratie, al is een directe transformatie naar een iteratief algoritme niet in alle gevallen mogelijk (en in zo'n geval is het recursieve algoritme dus eigenlijk 'sneller').

[ACM]

Op donderdag 18 april 2002 15:22 schreef Soultaker het volgende:
Ach, een docent die z'n studenten stimuleert snel te programmeren doet ook iets fout. Je kan studenten beter leren goed te programmeren; met een beetje mazzel doen ze dat dan ook nog, terwijl ze zo snel mogelijk programmeren vanzelf wel doen.

Mja, in dit geval geldt dat niet zo
fibonacci is gewoon veel makkelijker in een recursieve methode te maken

Ik kan me trouwens ook geen geval voorstellen waarin recursie efficienter is dan iteratie, al is een directe transformatie naar een iteratief algoritme niet in alle gevallen mogelijk (en in zo'n geval is het recursieve algoritme dus eigenlijk 'sneller').

Recursie schijnt _altijd_ naar iteratie om te zetten te zijn. Bewijs heb ik niet, maar dat is de boodschap die ik opving uit een paar college's alhier (college: Parallelle Computing & Parallelle Algoritmes)

[RickN]

Op donderdag 18 april 2002 15:27 schreef ACM het volgende:

[..]
Recursie schijnt _altijd_ naar iteratie om te zetten te zijn.

Ben ik het mee eens. Ten eerste is dit wat ik ook altijd heb opgevangen. Ten tweede heb ik het er net toevallig met een collega over gehad en we hebben een voor onszelf vrij overtuigend bewijs gegeven, waarin we in een aantal transformaties een generieke recursieve oplossing omschrijven tot een iteratieve.

[Gerco]

Op donderdag 18 april 2002 15:27 schreef ACM het volgende:
Recursie schijnt _altijd_ naar iteratie om te zetten te zijn. Bewijs heb ik niet, maar dat is de boodschap die ik opving uit een paar college's alhier

Misschien is het mijn gebrekkige opleiding, maar voor zover ik weet heeft een x86 CPU geen native ondersteuning voor recursie en wordt ALLES op een iteratieve manier uitgevoerd.

Dus alle recursieve algoritmes die op een x86 kunnen draaien, kunnen omgezet worden naar een iteratief algoritme (al is dat misschien niet altijd even efficient)

Is natuurlijk geen bewijs, maar komt voor praktische doeleinden dicht genoeg in de buurt.

[RickN]

Op donderdag 18 april 2002 15:57 schreef Gerco het volgende:

[..]

Misschien is het mijn gebrekkige opleiding, maar voor zover ik weet heeft een x86 CPU geen native ondersteuning voor recursie en wordt ALLES op een iteratieve manier uitgevoerd.

Dus alle recursieve algoritmes die op een x86 kunnen draaien, kunnen omgezet worden naar een iteratief algoritme (al is dat misschien niet altijd even efficient)

Is natuurlijk geen bewijs, maar komt voor praktische doeleinden dicht genoeg in de buurt.

Nou, x86 heeft een hardware stack en je mag gerust een CALL X in X zelf zetten. Lijkt me toch echt native ondersteuning voor recursie....

[Nielsz]

Op donderdag 18 april 2002 15:27 schreef ACM het volgende:
[..]
Recursie schijnt _altijd_ naar iteratie om te zetten te zijn.

Je bedoelt irritatie

[Gerco]

Op donderdag 18 april 2002 16:03 schreef RickN het volgende:
Nou, x86 heeft een hardware stack en je mag gerust een CALL X in X zelf zetten. Lijkt me toch echt native ondersteuning voor recursie....

If CALL een hardware instructie? Zo ja, wat is er anders aan dan JMP X oid?

En heeft de CPU enig idee van procedures, functies, methods, hoe je ze ook wilt noemen. Volgens mij weet de CPU alleen dat 'ie een instructie op locatie X aan het uitvoeren is en boeit het hem helemaal niet of die instructie deel is van een (recursieve) functie.

Vandaar mijn statement over geen hardware ondersteuning van recursie omdat er in de CPU niet zoiets BESTAAT als recursie, het ding weet niet eens wat het is. Het kan instructies uitvoeren en naar andere instructies springen. PUNT.

[RickN]

Een CALL zet de huidige waarde van de programcounter op de stack. Vervolgens kun uit een CALL naar de locatie van de aanroep terug keren met behulp van de RET instructie. M.a.w. Het CALL-RET mechanisme is de hardware implementatie van functieaanroepen.

[Gerco]

Ah, iets handiger dan JMP dus, maar dat zegt nog steeds niet dat de CPU enige notie heeft van recursie. Hij gooit bijvoorbeeld nog steeds niet je lokale variabelen op de stack (om maar eens wat te noemen), omdat er in ASM niet zoiets bestaat als een lokale variabele.

Misschien hebben we allebei een wat ander idee van hardware ondersteuning van recursie. Ik bedoel dus dat de CPU weet dat hij iets recursiefs aan het doen is en dat er dus zoiets bestaat als een "recursieve functie" op hardware niveau.

[Creepy]

Bron: http://www.google.nl/search?q=cache:XkSyM3X3F-QC:ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/stacks.html+variables+stack+recursive&hl=nl (google cache ja..kon de echte site niet bereiken)
3.3.1 Stack Frames
Almost invariably, programs compiled from modern high level languages (even C!) make use of a stack frame for the working memory of each procedure or function invocation. When any procedure or function is called, a number of words - the stack frame - is pushed onto a program stack. When the procedure or function returns, this frame of data is popped off the stack.
As a function calls another function, first its arguments, then the return address and finally space for local variables is pushed onto the stack. Since each function runs in its own "environment" or context, it becomes possible for a function to call itself - a technique known as recursion. This capability is extremely useful and extensively used - because many problems are elegantly specified or solved in a recursive way.

[edit]
Ow.. en deze is ook wel grappig: theorie van omzetten van recursieve naar een niet recursieve functie
http://www.cmpe.boun.edu.tr/~akin/cmpe160/recursion.html

[RickN]

Op donderdag 18 april 2002 16:37 schreef Gerco het volgende:
Ah, iets handiger dan JMP dus, maar dat zegt nog steeds niet dat de CPU enige notie heeft van recursie. Hij gooit bijvoorbeeld nog steeds niet je lokale variabelen op de stack (om maar eens wat te noemen), omdat er in ASM niet zoiets bestaat als een lokale variabele.

Misschien hebben we allebei een wat ander idee van hardware ondersteuning van recursie. Ik bedoel dus dat de CPU weet dat hij iets recursiefs aan het doen is en dat er dus zoiets bestaat als een "recursieve functie" op hardware niveau.

De CALL instructie is er voor functie aanroepen. Een recursieve functie is een functie die zichzelf aanroept, dus een CALL X in X is met die definitie van recursie recursief. Overigens zou je het CALL-RET mechanisme uitstekend kunnen implementeren met alleen JMP's als je toegang zou hebben tot de programcounter. Kijk, ASM kent geen instructie die in één keer een complete C for-statement implementeert, betekent dat dat de CPU geen hardware ondersteuning heeft voor iteratie? Lijkt me niet.

Een CPU heeft geen "recursieve functie aanroep"-instructie, die zul je zelf moeten samenstellen uit een aantal kleinere instructies en ook zul je registers die na terugkeer uit je recursieve aanroep bewaard moeten zijn zelf op de stack moeten zetten ja, maar als je dat allemaal doet, heb je lijkt me toch echt recursie geïmplementeerd. Het lijkt me iig niet dat je kunt zeggen dat je hiermee iteratie hebt geïmplementeerd, toch?

edit:

Oh, en zelfs met jouw definitie ( ) van hardware ondersteuning is er hardware ondersteuning voor locale variablen in procedures. De ENTER en LEAVE instructies maken en verwijderen ruimte op de stack voor de locale variablen van een procedure.

[Bergen]

Check ook eens iets als dit: Dit is dus gewoon compileerbaar en het doet waarschijnlijk ook nog iets. De makefile enzo staan er wel bij op de pagina waar ik em vandaan heb (zie url onderaan).

code:

#include <stdio.h>

char
*T="IeJKLMaYQCE]jbZRskc[SldU^V\\X\\|/_<[<:90!\"$434-./2>]s",
K[3][1000],*F,x,A,*M[2],*J,r[4],*g,N,Y,*Q,W,*k,q,D;X(){r  [r
[r[3]=M[1-(x&1)][*r=W,1],2]=*Q+2,1]=x+1+Y,*g++=((((x&     7)
-1)>>1)-1)?*r:r[x>>3],(++x<*r)&&X();}E(){A||X(x=0,g  =J
),x=7&(*T>>A*3),J[(x[F]-W-x)^A*7]=Q[x&3]^A*(*M)[2      +(
x&1)],g=J+((x[k]-W)^A*7)-A,g[1]=(*M)[*g=M[T+=A      ,1
][x&1],x&1],(A^=1)&&(E(),J+=W);}l(){E(--q&&l          ()
);}B(){*J&&B((D=*J,Q[2]<D&&D<k[1]&&(*g++=1          ),
!(D-W&&D-9&&D-10&&D-13)&&(!*r&&(*g++=0)          ,*
r=1)||64<D&&D<91&&(*r=0,*g++=D-63)||D              >=
97&&D<123&&(*r=0,*g++=D-95)||!(D-k[              3]
)&&(*r=0,*g++=12)||D>k[3]&&D<=k[                  1]
-1&&(*r=0,*g++=D-47),J++));}j(                  ){
putchar(A);}b(){(j(A=(*K)[D*                    W+
r[2]*Y+x]),++x<Y)&&b();}t                      ()
{(j((b(D=q[g],x=0),A=W)                      ),
++q<(*(r+1)<Y?*(r+1):                        Y)
)&&t();}R(){(A=(t(                          q=
0),'\n'),j(),++r                            [2
]<N)&&R();}O()                            {(
j((r[2]=0,R(                                ))
),r[1]-=q)                              &&
O(g-=-q)                                  ;}
C(){(                                    J=
gets                                    (K
[1]))&&C((B(g=K[2]),*r=!(!*r&&(*g++=0)),(*r)[r]=g-K[2],g=K[2
],r[
1]&&
O())
);;}
main
(){C
((l(
(J=(
A=0)
[K],
A[M]
=(F=
(k=(
M[!A
]=(Q
=T+(
q=(Y
=(W=
32)-
(N=4
))))
+N)+
2)+7
)+7)
),Y=
N<<(
*r=!
-A))
);;}

Komt van de International Obfuscated C Code Contest -> http://www.ioccc.org
Bovenstaande is the winner van dit jaar.

[FlowDesign]

Kijk, zulke posts leer ik ook nog iets van. Thanks
Maar het is idd zo dat iedere recursieve mothode ook als een iteratieve methode geschreven kan worden.

En voor de Fibonacci-reeks geldt:

Ik zat er naast! Was denk ik een beetje aan het slapen tijdens dat college hèhè.
Het voorbeeld was juist dat het wel eens zo kan zijn dat recursie juist veel langzamer is dan iteratie, maar omdat je bij recursie naar een base-case toewerkt (een case waarvoor maar 1 oplossing bestaat), is het moeilijk te zien dat recursie sosm juist inefficient is.
Wat wel zo is, is dat recursie bij bijvoorbeeld het sorteren van een lijst veel efficienter is (quick sort).

[tomato]

FlowDesign:maar omdat je bij recursie naar een base-case toewerkt (een case waarvoor maar 1 oplossing bestaat)

Da's niet helemaal fijn uitgedrukt, een base-case hoeft niet 1 oplossing te hebben, maar moet gewoon geen recursieve functiecall kunnen maken

Wat wel zo is, is dat recursie bij bijvoorbeeld het sorteren van een lijst veel efficienter is (quick sort).

Nee, het is 10 keer makkelijker te programmeren.

[.oisyn]

Op donderdag 18 april 2002 12:27 schreef Gerco het volgende:

[..]

Als je gaat bitshiften is het wel degelijk belangrijk in welke volgorde de bytes staan.:+

das niet correct, bitshiften gaat altijd goed. Het enige verschil tussen little en big-endian is de byte order in het geheugen. Voor de rest zijn alle berekeningen hetzelfde (shift left is dus *2, shift right is /2)

dat is ook logisch, want je shift de waarde van een register, en hoe de representatie daarvan in het geheugen ook is, de waarde blijft hetzelfde

[FlowDesign]

Op donderdag 18 april 2002 22:51 schreef tomato het volgende:

Nee, het is 10 keer makkelijker te programmeren.

Selection Sort: bij een list met lengte n duurt het n^2 stappen om te sorteren.
n = 1.000.000 -> n^2 = 1.000.000.000.000

Quick Sort: bij een list met lengte n duurt het n*log2n stappen om te sorteren.
n = 1.000.000 -> n*log2n = 19.931.569

Dus het lijkt mij wel ff een stuk efficienter

[.oisyn]

Op donderdag 18 april 2002 17:08 schreef RickN het volgende:

[..]

Kijk, ASM kent geen instructie die in één keer een complete C for-statement implementeert, betekent dat dat de CPU geen hardware ondersteuning heeft voor iteratie? Lijkt me niet.

in principe kun je van de LOOP en REP instructies hardware for-lusjes maken

[.oisyn]

Op donderdag 18 april 2002 23:18 schreef FlowDesign het volgende:

[..]

Selection Sort: bij een list met lengte n duurt het n^2 stappen om te sorteren.
n = 1.000.000 -> n^2 = 1.000.000.000.000

Quick Sort: bij een list met lengte n duurt het n*log2n stappen om te sorteren.
n = 1.000.000 -> n*log2n = 19.931.569

Dus het lijkt mij wel ff een stuk efficienter

dit heeft met het algoritme zelf te maken, verder niet of het recursief of iteratief geimplementeerd is. Een quicksort kun je namelijk ook best iteratief implementeren (net als dat je een iteratief iets ook recursief kunt implementeren)

[rollebol]

Wel jammer dat een grappig bedoeld verhaaltje moet uitmonden in gezeur over assembler.

Wat mij betreft kan iedere recursieve functie ook als iteratieve functie worden geschreven. Turing-machines kennen ook geen recursiviteit en kunnen alles wat hedendaagse computers kunnen, maar ik loop het risico nu van alles verkeerd te gaan zeggen, dus houd ik verder maar mijn mond.

[Gerco]

Op donderdag 18 april 2002 23:15 schreef .oisyn het volgende:
das niet correct, bitshiften gaat altijd goed. Het enige verschil tussen little en big-endian is de byte order in het geheugen. Voor de rest zijn alle berekeningen hetzelfde (shift left is dus *2, shift right is /2)

Dat weet ik ook wel, voor de shift maakt het natuurlijk geen ruk uit, maar als je 01 A0 in het geheugen hebt staan en je shift 8 bits naar links (zonder wrap) krijg je A0 00, en als de bytes als A0 01 gestaan hadden kreeg je 01 00.

Voor het resultaat van de shift maakt het dus wel degelijk uit of je little- of big-endian gebruikt.

[Gerco]

Op donderdag 18 april 2002 17:08 schreef RickN het volgende:
Kijk, ASM kent geen instructie die in één keer een complete C for-statement implementeert, betekent dat dat de CPU geen hardware ondersteuning heeft voor iteratie? Lijkt me niet.

Mij wel. In mijn definitie van hardware ondersteuning heeft een x86 dus beperkte hardware ondersteuning van iteratie (met een REP heb je een soort for lus, maar wat beperkt). Als er een soort hardware FOR zou bestaan, dan had de CPU hardware ondersteuning voor iteratie.

Dat het mogelijk is om er iets iteratiefs, recursiefs of wat dan ook op te doen betekent voor mij niet dat het ding er hardware ondersteuning voor heeft. Je kan toch ook niet zeggen dat een CPU hardware ondersteuning voor Java heeft als je er een java programma op kan draaien (via wat software lagen)?

[RickN]

Op vrijdag 19 april 2002 10:26 schreef Gerco het volgende:

[..]

Dat het mogelijk is om er iets iteratiefs, recursiefs of wat dan ook op te doen betekent voor mij niet dat het ding er hardware ondersteuning voor heeft. Je kan toch ook niet zeggen dat een CPU hardware ondersteuning voor Java heeft als je er een java programma op kan draaien (via wat software lagen)?

Hier heb je in principe wel gelijk in.
Maar goed, waar het op neer komt is dat jij dacht elke recursieve expressie naar iets iteratief vertaald kan worden omdat in assembler alles iteratief is. Dat laatste is dus niet waar. Daarnaast is een recursieve functie aanroep een bijzonder geval van een functie aanroep. x86 heeft echt hardware ondersteuning voor functie aanroep en dus ook voor recursieve functie aanroep.

Je kunt wel heel puristisch zeggen dat een processor alleen hardware ondersteuning heeft voor die zaken waar één specifieke instructie voor is en dan zou ik je niet absoluut ongelijk kunnen geven. Zelf denk ik dat je hardware ondersteuning en de instructie set moet zien zoals ie door de ontwerpers bedoeld is. Concreet wil dat zeggen dat er in die visie dan ondersteuning is voor iteratie m.b.v REP-LOOP (tnx .oisyn) functie aanroep m.b.v. CALL-ENTER-LEAVE-RET en dan dus ook recursieve functie aanroep. De instructies in deze constructie zijn pas nuttig als je ze in bepaalde combinaties met andere instructies gebruikt; een RET statement in z'n eentje doet niks nuttigs. Nu kun je zeggen dat de cpu hardware ondersteuning heeft voor RET en nog wat onzinnige dingen, maar zo is het natuurlijk niet bedoeld.
Nogmaals, je hoeft het hier niet mee eens te zijn, dit is geen geschreven wet ofzo, maar ik weet wel dat hardware ontwerpers het met me eens zullen zijn.

[Gerco]

Op vrijdag 19 april 2002 11:11 schreef RickN het volgende:
Daarnaast is een recursieve functie aanroep een bijzonder geval van een functie aanroep. x86 heeft echt hardware ondersteuning voor functie aanroep en dus ook voor recursieve functie aanroep.

Dat klopt, ik wilde ook niet zeggen dat de CPU er alleen ondersteuning voor heeft als er 1 specifieke intructie voor is, maar meer dat de CPU moet "weten" wat 'ie aan het doen is voor je het hardware ondersteuning kan noemen.

Als de CPU een Java programma draait heeft 'ie daar geen "weet" van, dus heeft 'ie er geen hardware ondersteuning voor. Als je een CALL uitvoert, "weet" 'ie dat je een functie aanroept en "verwacht" 'ie dat je die met een RET gaat afsluiten. Dus de CPU heeft WEL hardware ondersteuning voor functie aanroepen (procedures eigenlijk, volgens mij bestaat er niet zoiets als een return value, maar dat kan ik natuurlijk mishebben).

[RickN]

Joh hé, dan zijn we het gewoon met elkaar eens!

[Gerco]

Op vrijdag 19 april 2002 11:46 schreef RickN het volgende:
Joh hé, dan zijn we het gewoon met elkaar eens!

Goh, wie had dat nog kunnen bedenken!

[Varienaja]

Op vrijdag 19 april 2002 00:58 schreef rollebol het volgende:
Wat mij betreft kan iedere recursieve functie ook als iteratieve functie worden geschreven. Turing-machines kennen ook geen recursiviteit en kunnen alles wat hedendaagse computers kunnen, maar ik loop het risico nu van alles verkeerd te gaan zeggen, dus houd ik verder maar mijn mond.

Hehehe.. zal ik ff nog verder offtopic gaan.

Ik heb voor een opdracht op school een Turingmachine geprogrammeerd. Ik weet al niet eens meer hoe het werkte, maar het wast zoiets van:
Er staat iets op de band in de vorm van iii.
Je programma moet dit omzetten naar
iiiKiiiiiiiii (3x de lengte van de input dus).

M'n algoritme was van complexiteit O(n^3), die van een klasgenoot O(n^4)

[ThE_ED]

Op vrijdag 19 april 2002 11:53 schreef Gerco het volgende:

[..]

Goh, wie had dat nog kunnen bedenken!

Je bent voorspelbaar Gerco.. ik wist dat je in dit topic zou posten

[Gerco]

Op vrijdag 19 april 2002 12:03 schreef ThE_ED het volgende:
Je bent voorspelbaar Gerco.. ik wist dat je in dit topic zou posten

Jij ook, ik wist dat je die opmerking zou maken als je zag dat ik hier gepost had

Maar als je de replies zou lezen, zou je weten dat het helemaal niet om die Fibonacci-reeks ging

[.oisyn]

Op vrijdag 19 april 2002 10:22 schreef Gerco het volgende:

[..]

Dat weet ik ook wel, voor de shift maakt het natuurlijk geen ruk uit, maar als je 01 A0 in het geheugen hebt staan en je shift 8 bits naar links (zonder wrap) krijg je A0 00, en als de bytes als A0 01 gestaan hadden kreeg je 01 00.

Voor het resultaat van de shift maakt het dus wel degelijk uit of je little- of big-endian gebruikt.

fout, de representatie van het getal maakt nou juist niets uit. Een shift is een bewerking op het getal zelf, en niet hoe die in het geheugen zou staan.

stel je hebt het getal 0x0123
in big-endian is dat 01 23
in little-endian is dat 23 01

ga je m nu 4 bits naar links schuiven, dan krijg je dus als resultaat 0x1230

dat is in big-endian 12 30
en in little-endian 30 12

Je schuift namelijk niet de bits in het geheugen, maar de bits in de bits van het getal zelf. Het maakt dus niets uit of je shift in big of little-endian formaat, er komt hetzelfde uit

[Soultaker]

Op donderdag 18 april 2002 23:18 schreef FlowDesign het volgende:
Selection Sort: bij een list met lengte n duurt het n^2 stappen om te sorteren.
n = 1.000.000 -> n^2 = 1.000.000.000.000

Quick Sort: bij een list met lengte n duurt het n*log2n stappen om te sorteren.
n = 1.000.000 -> n*log2n = 19.931.569

Dus het lijkt mij wel ff een stuk efficienter

Nee hoor, quick sort heeft ook O(N^2) als worst-case complexiteit. Had dan heapsort of mergesort als voorbeeld genomen. Selection sort zegt me verder niet zoveel, maar als de coplexiteit O(N^2) is, is dat waarschijnlijk niet zo erg.

[tomato]

Soultaker: Nee hoor, quick sort heeft ook O(N^2) als worst-case complexiteit. Had dan heapsort of mergesort als voorbeeld genomen. Selection sort zegt me verder niet zoveel, maar als de coplexiteit O(N^2) is, is dat waarschijnlijk niet zo erg.

Selection sort kent een complexiteit van O(n^2) (die overigens best- en worstcase is).

Quick sort en mergesort hebben allebei een average van O(n*log(n)) qua complexiteit, alleen mergesort gebruikt veel minder gegeugen. Van beiden is de worst-case complexiteit overigens nog gewoon O(n^2).

Wanneer je van te voren het aantal te sorteren eenheden weet, zijn er nog snellere algoritmen.

[RickN]

Op vrijdag 19 april 2002 18:12 schreef tomato het volgende:

[..]

Selection sort kent een complexiteit van O(n^2) (die overigens best- en worstcase is).

Quick sort en mergesort hebben allebei een average van O(n*log(n)) qua complexiteit, alleen mergesort gebruikt veel minder gegeugen. Van beiden is de worst-case complexiteit overigens nog gewoon O(n^2).

Mergesort is worstcase O(N log N). En zoveel scheelt het geheugengebruik nou ook weer niet hoor, het hangt een beetje van je implementatie af.

Wanneer je van te voren het aantal te sorteren eenheden weet, zijn er nog snellere algoritmen.

Idd, maar je kunt bewijzen dat een algoritme dat van swaps gebruikt maakt nooit sneller kan sorteren dan in O(N log N)

[Soultaker]

Mergesort is worstcase O(N log N). En zoveel scheelt het geheugengebruik nou ook weer niet hoor, het hangt een beetje van je implementatie af.

Als ik me niet vergis, heeft mergesort in principe altijd O(N) extra geheugen nodig. Dat hoeft natuurlijk niet altijd een probleem te zijn, maar een efficient algoritme als mergesort is juist praktisch als je veel gegevens moet sorteren. Dan is het natuurlijk vervelend als je geheugengebruik ook verdubbelt. Daarbij kost het alloceren en initialiseren van veel geheugen natuurlijk ook tijd.

Zelf geef ik meestal de voorkeur aan heap sort, omdat dit algoritme een worst-case complexiteit van O(N*log(N)) (zoals van mergesort) combineert met een constant geheugengebruik (zoals quicksort). De verborgen constante van het algoritme is meestal echter wel een stuk groter dan in de implementaties van beide andere algoritmes.

[RickN]

Op vrijdag 19 april 2002 21:44 schreef Soultaker het volgende:

[..]

Als ik me niet vergis, heeft mergesort in principe altijd O(N) extra geheugen nodig. [..]

Je kunt bij mergesort nog onderscheid maken tussen external mergesort en in-place mergesort. in-place mergesort gebruikt geen extern array. Omdat het afwezig zijn van zo'n array uiteraard ten koste gaat van de efficientie kun je vraagtekens zetten bij het nut van zo'n implementatie.

[Soultaker]

Op zaterdag 20 april 2002 00:49 schreef RickN het volgende:
in-place mergesort gebruikt geen extern array. Omdat het afwezig zijn van zo'n array uiteraard ten koste gaat van de efficientie kun je vraagtekens zetten bij het nut van zo'n implementatie.

Hoe werk dat dan ongeveer? Ik heb er zelf wel eens mee zitten klooien en toen kwam ik er niet echt uit om op een handige manier te mergen zonder extra array. Uiteindelijk heb ik even in man sort gekeken en kwam ik tot de (misschien niet heel goed gefundeerde) conclusie dat 't schijnbaar niet anders kon.

Wat is de complexiteit van in-place mergesort in verschillende situaties? Als het ook om O(N^2) gaat, maar met een grotere constante, kun je natuurlijk (zoals je al zei) net zo goed quicksort gebruiken...

[FlowDesign]

Zoals ik al gezegd had, ben ik nu Java aan het leren,

Maar wat is nou, denken jullie, de meest efficiënte methode om bijvoorbeeld een list van lengte 100.000 te sorteren?

[Soultaker]

Op zaterdag 20 april 2002 13:12 schreef FlowDesign het volgende:
Maar wat is nou, denken jullie, de meest efficiënte methode om bijvoorbeeld een list van lengte 100.000 te sorteren?

(Ik was hier dus een flink stuk aan het typen toen mijn X terminal er mee ophielt. Ik heb geen zin om opnieuw te beginnen dus even een korte samenvatting. Iemand anders kan desgewenst wel de achterliggende redenaties toelichten.)

Wanneer extra geheugen gebruik ter grootte van je lijst geen bezwaar is: mergesort.

Wanneer sommige individuele gevallen wel eens lang mogen duren: quicksort.

In de overige gevallen: heapsort.

Ik kies zelf vaak voor heapsort, hoewel de keuze afhangt van de omstandigheden. In het algemeen is de verborgen constante van heapsort het hoogst, daarna die van mergesort en vervolgens die van quicksort. Quicksort zal gemiddeld dus het snelste zijn (mits er willekeurige gegevens in gaan), maar in individuele gevallen kan het algoritme erg traag zijn. Heapsort en mergesort sorteren allebei in een vaste tijd (bij een zekere lengte), waarbij heapsort trager is dan mergesort, maar geen extra geheugen gebruikt.

Dit zijn natuurlij niet alle sorteeralgoritmen, maar wel de meest algemeen bekende en toepasbare. Je zult echter per situatie moeten bepalen welke het meest geschikt is.

[Janoz]

Als het een lijst is die tijdens het draaien van je programma telkens geupdate ed wordt is het handiger om hem gewoon gesorteerd in het geheugen te bewaren (in bv een binaire boom. Daarvoro zijn in java standaard classes beschikbaar). Zorg er dan wel voor dat je iig kunt garanderen dat je boom redelijk gebalanceerd blijft (bv met red/black trees)

[Soultaker]

Op zaterdag 20 april 2002 13:46 schreef Janoz het volgende:
Als het een lijst is die tijdens het draaien van je programma telkens geupdate ed wordt is het handiger om hem gewoon gesorteerd in het geheugen te bewaren (in bv een binaire boom. Daarvoro zijn in java standaard classes beschikbaar). Zorg er dan wel voor dat je iig kunt garanderen dat je boom redelijk gebalanceerd blijft (bv met red/black trees)

Een goed punt, waar ik het volgende aan wil toevoegen: kijk ook naar (wat simpelere) algoritmes als insertion sort (om elementen in een gesorteerde lijst in te voegen in O(log(N)) en heaps (wanneer je de elementen in gesorteerde volgorde nodig hebt en daarna niet meer gebruikt).

[RickN]

Op zaterdag 20 april 2002 12:45 schreef Soultaker het volgende:

[..]

Hoe werk dat dan ongeveer? Ik heb er zelf wel eens mee zitten klooien en toen kwam ik er niet echt uit om op een handige manier te mergen zonder extra array. Uiteindelijk heb ik even in man sort gekeken en kwam ik tot de (misschien niet heel goed gefundeerde) conclusie dat 't schijnbaar niet anders kon.

Ik ben geen boek Maar kijk hier maar eens, staan een hele hoop voorbeelden van sorts, waaronder in-place mergesort. Google geeft ook heel veel pagina's.

Wat is de complexiteit van in-place mergesort in verschillende situaties? Als het ook om O(N^2) gaat, maar met een grotere constante, kun je natuurlijk (zoals je al zei) net zo goed quicksort gebruiken...

Geen echt idee eigenlijk.

O, en ik heb het idee dat je een beetje negatief bent over quicksort. Je hebt wel gelijk dat quicksort in sommige gevallen heel traag is (vandaar ook O(N^2) worstcase), maar die gevallen zijn echt heel zeldzaam (B.v. een reeds gesorteerd array).

[Soultaker]

Op zaterdag 20 april 2002 15:47 schreef RickN het volgende:
Ik ben geen boek

Sorry, dat had ik zelf kunnen opzoeken natuurlijk.

Maar kijk hier maar eens, staan een hele hoop voorbeelden van sorts, waaronder in-place mergesort.

Leuk die 'puzzelstukjes'...

O, en ik heb het idee dat je een beetje negatief bent over quicksort.

Ik vind het gevoelsmatig een beetje vervelend dat je eigenlijk niet kan zeggen dat je code in elk geval efficient werkt. Ik ben me er echter van bewust dat quicksort in de meeste gevallen wel heel efficient werkt.

Zelfs situaties waarin de invoer al gesorteerd is, kunnen meestal wel efficient gesorteerd worden, als je je mediaan op een slimme manier kiest (bijvoorbeeld door de mediaan van het eerste, middelste en laatste element in je array).

Het fijne van de andere twee algoritmes die ik noemde, is dat je ZEKER weet dat een lijst in O(log(N)) gesorteerd wordt.