Marcus Zinn wrote:
> Hallo !> Für ein Projekt habe ich diese for-Schleife entdeckt!> Was macht diese ?
Nichts.
> for(;;)>> Ist das eine Schleife die nie endet ?
Ja. Man nennt so etwas (O Wunder!) Endlosschleife. Geht auch z.B. mit
1
while(1);
wobei an Stelle der "1" auch alles stehen kann, was nicht Null ist.
ist unvollständig.
Erst durch ein angehängtes Semikolon wird 'ne Endlosschleife draus.
Sonst wird der auf das for-Statement folgende Block ewig wiederholt:
1
for(;;)
2
machwas();
oder
1
for(;;)
2
{
3
machwas();
4
}
Und dann lässt sich die vermeintlich endlose Schleife auch verlassen:
Peter S. wrote:
> for(;;) finde ich hässlich!
Hat sich aber eingebürgert, dem Vernehmen nach, weil lint es nicht
anmosert sondern als Ausdruck des Programmierers nimmt, wirklich eine
Endlosschleife haben zu wollen.
> for(;;) finde ich hässlich!
Ich nicht.
> while(1) ist hingegen logisch und völlig selbsterklärend!
Das sagt etwa aus: "Tue das Folgende, solange 1 nicht 0 ist). Die erste
Variante sagt: "Tue das Folgende in einer Schleife, und zwar ohne
Abbruchbedingung".
> Tue das Folgende, solange 1 nicht 0 ist)
Und wehe, ein Mathematiker beweist eines Tages, dass 1 gleich 0 ist.
Meine Programme mit for(;;) werden auch dann noch endlos weiterlaufen
:-)
Ich finde for(;;) sehr schön. Das sieht nämlich irgendwie nach
Däumchendrehen aus.
while(true) wäre für mich auch noch akzeptabel, aber bei while(1)
frage ich mich immer, warum nicht while(2) oder while(-1) oder
while(0.0745)?
I remember being impressed with Ada because you could write an
infinite loop without a faked up condition. The idea being that in
Ada the typical infinite loop would normally be terminated by
detonation. -- Larry Wall
Wer also richtige Endlosschleifen programmieren will, sollte
auf die Programmiersprache Ada umsteigen:
> ...rage ich mich immer, warum nicht while(2) oder while(-1) oder> while(0.0745)?...>>> Geht auch...
Eben. Weil mir die Entscheidung für eine bestimmte Zahl so schwer
fällt, finde ich es nicht besonders logisch, überhaupt eine Zahl als
Abbruchbedingung hinzuschreiben. Was zeichnet denn die 1 vor anderen
Zahlen aus? Dass sie das neutrale Element der Multiplikation ist? Aber
das hat doch mit Abbruchbedingungen nichts zu tun.
Anderer Vorschlag:
1
#define loop for(;;)
2
3
loop{
4
// Code
5
}
Dann sieht's fast aus wie in Ada. Oder
1
#define loop for(;;) {
2
#define end_loop }
3
4
loop
5
// Code
6
end_loop
Jetzt sieht's noch mehr nach Ada aus, dafür aber leider nicht mehr
nach C.
Ich bevorzuge while(), weil es über viele Programmiersprachen hinweg
betrachtet üblicher ist als eine Zählschleife die mit for ebenfalls in
fast allen Sprachen vorkommt aber nur im C Standard zählen kann was
nicht vorhanden ist und somit unendlich lange irgendwas zählt was nicht
zählbar ist. Das ist unlogisch.
Gruß Hagen
> Wer also richtige Endlosschleifen programmieren will, sollte> auf die Programmiersprache Ada umsteigen:> loop> Do_Something;> end loop;
Und in C geht's auch ganz klassisch, wie es schon auf dem Homecomputer
in BASIC gemacht wurde:
1
loop:
2
do_something();
3
gotoloop;
@Hagen:
Du siehst die for-Schleife nur als einfache Zählschleife, aber sie ist
in C eben flexibler. Und for(;;) ist ein Konstrukt, der extra für
Endlosschleifen vorgesehen ist. Bei while(1) mißbraucht man die
Schleife, indem man für die Ausführung eine Bedingung einbaut, die immer
wahr ist.
Wie yalu schon schrieb, stellt sich auch die Frage, was die 1 so
besonders macht, daß man gerade die verwendet.
ist in C im Prinzip nichts anderes als eine Kurzschreibweise für
1
a;
2
while(b)
3
{
4
//...
5
c;
6
}
for hat in C nicht direkt etwas mit "zählen" zu tun. Ich gebe Dir
allerdings recht, wenn Du den Vergleich mit anderen Sprachen ziehst, in
denen tatsächlich "for"-Konstrukte hauptsächlich für Aufgaben mit einer
definierten Zykluszahl verwendet werden.
Rolf Magnus wrote:
> Wie yalu schon schrieb, stellt sich auch die Frage, was die 1 so> besonders macht, daß man gerade die verwendet.
Das Define "TRUE" was man in gängigen C-Standardheadern findet, als auch
"true" als boolescher Wert entsprechen (in der Regel) einer 1
> Das Define "TRUE" was man in gängigen C-Standardheadern findet,
... das da aber gar nicht stehen dürfte ...
> als auch "true" als boolescher Wert entsprechen (in der Regel) einer 1
Wenn man den boolschen Wert in einen Integer konvertiert, kommt 1 raus.
In der while-Schleife benutzt man aber die umgekehrte Konvertierung, bei
der außer 0 alle Werte dasselbe Ergebnis liefern.
Rolf Magnus wrote:
> Nein.
Gut, dann nicht. For-Schleifen benutze ich eh selten. Nur wenn eine
feste Anzahl Zyklen durchlaufen werden soll. Ansonsten benutze ich immer
while(xyz--){} oder sowas. Von daher wusste ich das nicht genau.
Naja, jetzt weiß ich es ja ;)
@Simon: Nein.
Eine for-Schleife wird bei nichtzutreffen der Schleifenbedingung nie
durchlaufen, entspricht also einer "pre-check-loop" while (cond) {} und
nicht einer "post-check-loop" do {} while (cond);
Michael Wilhelm wrote:
> Früher hat soetwas noch kopf- bzw. fußgesteuerte Schleife geheißen.
Je nachdem, ob du drüber nachgedacht hast oder einfach nur drauf
trittst. :-)
@Rolf, ua.
ich weis das es so in C ist, keine Frage. Die Entscheidung ob nun eine
leere for() oder while(1) logischer oder unlogischer ist, mache ich
dingfest auf Grund einer anderen Sichtweise. Wer tagtäglich mit mehr als
2-3 Programmiersprachen arbeitet sollte sich meiner Meinung nach daran
gewöhnen einen angepassten Programmierstil zu benutzen der für alle
Sprachen einigermaßen gültig ist. Im Grunde passiert das ja sowieso
automatisch.
Und es ist eben nur in C so das man for() so benutzen kann. Ich benutze
dementsprechend for() wirklich nur als echte Zählschleife, und das
while(1) Konstrukt für Endlosschleifen. Das ist Sprachübergreifender.
Auch in anderen Sprachen baut man Endlossschleifen zb. über while True
do; oder repeat until False; usw. (nur mal in die PASCAL Fraktion
geschaut).
Da ist es mir dann Brust, ja ich gebe sogar zu das ich mir nie die Frage
gestellt habe warum while (1) oder ähnliches unlogisch wäre, es ist
einfach so das while (immer Wahr) benötigt wird damit sie endloss lange
läuft, was daran ist unlogisch ? Anders ausgedrückt, jede Sprache hat
ihre "Ungereimtheiten", C ist da wohl die negative Ausnahme im Vergleich
zu anderen Sprachen, das ist normal. Für mich ist die Programmiersprache
nur ein Mittel zum Zweck, also ärgere ich mich nicht darüber das es
Ungereimtheiten gibt, denke darüber nicht weiter nach, sondern löse mein
Softwareproblem.
Gruß Hagen
> Und es ist eben nur in C so das man for() so benutzen kann. Ich benutze> dementsprechend for() wirklich nur als echte Zählschleife,
In python gibt es gar keine Zählschleifen, und trotzdem gibt's da for.
Aber es ist dort dazu da, um eine Aktion für jedes Element in einem
Container zu machen (in manchen Sprachen als for_each o.ä. bekannt).
> ja ich gebe sogar zu das ich mir nie die Frage gestellt habe warum> while (1) oder ähnliches unlogisch wäre,
Ich behaupte nicht, es sei unlogisch. Ich behaupte nur, daß es mit
for(;;) einen Konstrukt gibt, der besser paßt.
> Anders ausgedrückt, jede Sprache hat ihre "Ungereimtheiten",
Endlosschleifen sind in C allerdings keine davon, denn gerade für die
wurde extra die Möglichkeit eingebaut, bei for() die Bedingung ganz
wegzulassen. Wenn du stattdessen while(1) schreibst und dann als
"Ungereimtheit" ansieht, daß du da gezwungen bist, eine immer wahre
Bedingung anzugeben, ist das nicht die Schuld der Sprache.
Daß wir uns nicht falsch verstehen: Ich bekomme jetzt nicht gleich einen
Anfall, wenn ich ein while(1) irgendwo sehe. Nur wenn jemand es als
"logischer" oder "eleganter" als ein for(;;) ansieht, bin ich eben
anderer Meinung.
> Für mich ist die Programmiersprache nur ein Mittel zum Zweck, also> ärgere ich mich nicht darüber das es Ungereimtheiten gibt, denke> darüber nicht weiter nach, sondern löse mein Softwareproblem.
Wenn das bei mir nicht der Fall wäre, würde ich bestimmt kein C
programmieren. ;-)
> Und wehe, ein Mathematiker beweist eines Tages, dass 1 gleich 0 ist.
Meine Programme mit for(;;) werden auch dann noch endlos weiterlaufen
:-)
Dann mache eben
1
while(!0)
2
{
3
}
Bleibt dann auch gültig, und die Frage warum 1 und nicht 2 erübrigt sich
;-)
Richtig schön ist das bei jener Sorte interpretierter Sprachen, in denen
jedes Objekt technisch gesehene eine Variable ist, auch wenn es optisch
wie eine lexikale Konstante aussieht. Da ist es grundsätzlich möglich,
der Konstanten "0" den Wert "1" zuzuweisen.
Wenn sie schon eine extra Konstruktion für Endlosschleifen einbauen,
wäre meiner Meinung nach sowas wie
1
do{/*...*/}
passen. Da gibt's dann weder ein immer wahrer Vergleich, noch keine
Bedingung, wo eigentlich eine hingehörte. Ausser man will das fehlende
"while(cond);" auch als fehlende Bedingung bezeichnen.
Da lob' ich mir doch (Visual) Basic, da gibt's sowas:
Do
'...
Loop
Ist aber wohl schlussendlich eh alles eine "Glaubensfrage".
#define long for // wer braucht schohn den Datentyp?
3
#define the (
4
#defie world ;
5
#define is ;
6
#define still ;
7
#define spinning )
8
9
aslongastheworldisstillspinning
10
{
11
...
12
}
Ich wollte gerade auf diese innovative Schreibweise umsteigen. Allein
die Aussicht, sich nie mehr zwischen int und long entscheiden zu
müssen, rechtfertigt den Umstieg. C-Programme sehen nun fast wie Cobol
aus, das ist so einfach, dass sogar 70-Jährige (oder vielleicht nur
diese?) darin programmieren können.
Dann musste ich aber entsetzt feststellen, dass da noch zwei Bugs drin
sind. Also aus der Traum, aber vielleicht funktioniert's im nächsten
Release :-)
... aber warum diskutieren wir überhaupt darüber, ob nun for(;;) oder
while(1) die logischere Endlosschleife ist?
Viel logischer ist es doch, Schleifen ganz wegzulassen. Denn:
1. Schleifen sind schlechter Programmierstil. Das lernt jeder
Lisp-Anfänger.
2. Die visuelle Analyse von Programmschleifen am Bildschirm
schädigt die Augenmuskulatur und verschleißt Mausräder.
3. Schleifen (vor allem, wenn mehrere Schleifentypen angeboten werden)
führen zu ressourcenfressenden Diskussionen wie dieser.
4. Schleifenkonstrukte werden mittelfristig sowieso aus den
Programmiersprachen verschwinden, ähnlich dem Goto. Einige neuere
Programmiersprachen wie z. B. Haskell haben schon den Anfang
gemacht:
http://www.haskell.org/~pairwise/intro/section4.html#part1
Also,versucht mal, die Schleifen dort zu lassen, wo sie hingehören,
nämlich an Weihnachtsgeschenken und Brautjungfern. Der Verzicht fällt
am Anfang schwer, aber manche haben sich sogar schon das Rauchen
abgewöhnt.
> 4. Schleifenkonstrukte werden mittelfristig sowieso aus den> Programmiersprachen verschwinden, ähnlich dem Goto. Einige neuere> Programmiersprachen wie z. B. Haskell haben schon den Anfang> gemacht:
Ohja, Rekursion rockt. Nieder mit iterativen Lösungen!
>> zwei?>> Innerhalb des for() dürfen nur zwei Semikolons sein, nicht drei.
Das war der, den ich gleich beim Abschicken gesehen habe. ;-)
Das #defie hatte ich übersehen. Fazit: Mit copy/paste wäre das nicht
passiert.
yalu wrote:
> Viel logischer ist es doch, Schleifen ganz wegzulassen. Denn:
Na super.
Schleifen gehören zum Programmieren, wie Luft zum Atmen !
Ich habe kein einziges Programm ohne Schleifen.
Wie würde man z.B. dieses praktische Beispiel ohne Schleife machen ?
> Schleifen gehören zum Programmieren, wie Luft zum Atmen !
Das Atmen wird völlig überbewertet. Luft ist nur eine Droge, deren
Entzugserscheindungen sehr schnell einsetzen.
> Ich habe kein einziges Programm ohne Schleifen.
Ironiedetektor kaputt?
> Wie würde man z.B. dieses praktische Beispiel ohne Schleife machen ?
@Rolf,
Du schreibst also ne Schleife in ne schlecht lesbare Rekursion um.
Und was macht der AVR-GCC daraus ?
Er formt es wieder in ne Schleife um !
Weg mit all den überflüssigen PUSH, POP, CALL und RET.
Wow, hätte ich dem GCC nicht zugetraut.
Nur das Inlinen von spi_out2 in spi_out packt er nicht,
selbst nicht mit "inline static void spi_out2".
Peter
Peter Dannegger wrote:
> Nur das Inlinen von spi_out2 in spi_out packt er nicht,> selbst nicht mit "inline static void spi_out2".
Wahrscheinlich deshalb:
1
% avr-gcc -Os -mmcu=atmega1281 -S loop.c
2
loop.c: In function 'spi_out':
3
loop.c:8: sorry, unimplemented: inlining failed in call to 'spi_out2': recursive inlining
4
loop.c:19: sorry, unimplemented: called from here
Das bekommt man, wenn man __attribute__((always_inline)) dafür
benutzen möchte.
> Rekursionen sind Teufelszeug, braucht man wie das Ozon zum Atmen.
Wie yalu festgestellt hat, gibt es Programmiersprachen, die für
Rekursion gut geeignet sind, und Programmiersprachen, die dafür weniger
geeignet sind. C und C++ fallen definitiv in die zweite Kategorie,
Sprachen wie Haskell und Lisp dagegen in die erste.
Wie man an deiner Aussage sieht, ist es schwierig Rekursion mit C++ zu
verteidigen.
> C und C++ fallen definitiv in die zweite Kategorie, Sprachen wie> Haskell und Lisp dagegen in die erste.
C++ würde ich nur teilweise dazuzählen. Mit Template Metaprogramming
kann man in C++ ganze Algorithmen schreiben, die komplett zur
Compilezeit ausgeführt werden. Da gibt's aber keine Schleifen.
>Die intensive Verbreitung von Haskell und Lisp auf allen>Microcontrollersystemen spricht ja auch irgendwie für sich ...
;) Killerargument, besonders da das Denken der Menschen auch rekursiv
und nicht iterativ geprägt ist. Also ich kenne nur Programmierer und
Mathematiker die überhaupt wissen was ein Rekursiver Algorithmus ist,
alle anderen sind es gewohnt sequentiell iterativ zu denken.
Gruß Hagen
@Peter Dannegger:
> Rekursionen sind Teufelszeug, braucht man wie das Ozon zum Atmen.
Eins vorweg, damit nicht der Eindruck entsteht, ich sei so ein
abgespaceter Programmierhippie: Ich programmiere, wie die meisten
anderen auch, das hauptsächlich in C/C++, und setze Rekursionen
ziemlich selten ein.
Trotzdem würde ich die Rekursion nicht verteufeln. Es ist eines von
vielen Programmierkonzepten, das - mit Verstand eingesetzt - das Leben
durchaus leichter machen kann.
> Sie verschlechtern die Lesbarkeit ...
Nicht generell. Schau dir z. B. mal zwei Quicksortroutinen in C an,
einmal mit Rekursion und einmal ohne Rekursion programmiert. Das
rekursive Programm ist etwa halb so lang und man erkennt auf den
ersten Blick das Funktionsprinzip, wohingegen die nichtrekursive
Version praktisch nur mit zusätzlicher Dokumentation zu verstehen ist.
Und diese hat mit ziemlicher Sicherheit ihrerseits einen rekursiven
Aufbau ;-)
Dasselbe gilt natürlich auch für alle anderen Algorithmen, die nach
dem Divide-and-Conquer-Prinzip arbeiten. Dieses Prinzip ist von Natur
aus rekursiv und wird auch im Kopf der meisten Leute rekursiv
dargestellt.
In einer Funktionalsprache wie Haskell sind solche Algorithmen noch
ein Stück kürzer und selbsterkärender.
> und machen dem Compiler das Leben schwer.
So soll es ja auch sein. Der Compiler für eine Programmiersprache ist
der Vermittler zwischen den unterschiedlichen Denk- und Arbeitsweisen
von Programmierer und dem Prozessor. Will man sich als Mensch nicht an
den Prozessor anpassen (d. h. anfangen, in Opcodes und Sprungadressen
zu denken), muss eben der Compiler die Umsetzungsarbeit übernehmen,
was unter Umständen in Schwerstarbeit ausartet. Das ist mir aber recht
so, wenn ich dadurch selber Arbeit sparen kann :-)
yalu wrote:
> Trotzdem würde ich die Rekursion nicht verteufeln. Es ist eines von> vielen Programmierkonzepten, das - mit Verstand eingesetzt - das Leben> durchaus leichter machen kann.
Dann sollte man sie auch als Werkzeug betrachten, d.h. nur an den
Stellen einsetzen, wo es sinn macht, eben immer das passende Werkzeug
nehmen.
Aber auf keinen Fall mit Gewalt jede Schleife in ne Rekursion
ummanschen, damit sich dann der Compiler an die Stirn tippt und es
wieder in ne Schleife umformt.
Alle Wiederholungen, wo die Anzahl der Durchläufe schon beim Eintritt
feststeht sind nunmal besser als Schleife implementierbar.
Beliebtes Beispiel für Rekursionen ist ja ne Suche in wurzelartigen
Dateisystemen. Aber Vorsicht, so ein Dateisystem kann ja auch flach sein
und nur vorgaukeln, daß es wurzelartig ist.
Generell abzuraten ist von Rekursionen, die sich mehrfach aufrufen, da
dann der Rechenzeitbedarf exponentiell ansteigt (z.B. Fibonacci).
http://zach.in.tu-clausthal.de/teaching/info1_0506/folien/07_rekursion_6up_2.pdf>> und machen dem Compiler das Leben schwer.>> So soll es ja auch sein. Der Compiler für eine Programmiersprache ist> der Vermittler zwischen den unterschiedlichen Denk- und Arbeitsweisen> von Programmierer und dem Prozessor.
Nein so sollte es nicht sein.
Es nützt die schönste Porgrammiersprache nichts, wenn sie nicht
implementierbar ist.
Der Compiler muß immer ein Kompromiß zwischen beiden Seiten
(Programmierer, CPU) sein, wenn das Ergebnis optimal sein soll.
Peter
> Generell abzuraten ist von Rekursionen, die sich mehrfach aufrufen, da> dann der Rechenzeitbedarf exponentiell ansteigt (z.B. Fibonacci).
Du rätst also von Quicksort ab, weil es exponentiellen Rechenzeitbedarf
hat?
Chris wrote:
> Du rätst also von Quicksort ab, weil es exponentiellen Rechenzeitbedarf> hat?
Habe ich nirgends behauptet.
Es ruft sich zwar selber mehrfach auf, aber mit unterschiedlichen
Parametern.
Daher ist eine Eleminierung unnötiger Aufrufe schwer möglich.
Präzise hätte ich also sagen müssen:
"Generell abzuraten ist von Rekursionen, die sich mehrfach mit den
selben Parametern aufrufen, z.B. Fibonacci."
Peter
>"Generell abzuraten ist von Rekursionen, die sich mehrfach mit den>selben Parametern aufrufen, z.B. Fibonacci."
Hm, das verstehe ich nicht.
Wenn eine rekursive Funktion mit den gleichen Parametern aufgerufen wird
dann ruft sich sich wiederum rekursiv mit den gleichen Parametern auf,
und das muß eine Endlos-Rekursion sein.
Damit kommt man also bei der Fibonacci Funktion niemals zum Ende, und
das stimmt meiner Meinung nach nicht. Fibonacci ruft sich rekursiv mit
immer kleiner werdenden Parametern auf bis die Abbruchbedingung erreicht
ist.
Eine rekursive Funktion mit den gleichen Parametern sich selbst rekursiv
aufruft wird immer zu einer Endlosrekusion führen, da die
Abbruchbedingung nie erreicht werden kann.
Ich betrachte eine globale Variable die zb. durch die Rekursion
dekrementiert wird, auch als ein Parameter der Funktion. Also auch wenn
diese Variable nicht als Funktions-Parameter übergeben wird so ist es
denoch ein Parameter der das Verhalten der Rekursion beeinflusst. Ich
erwähne das nur um zu vermeiden das wieder Kümmel gespalten wird.
Gruß Hagen
Bei Fibonacci oder auch Fakultät ruft sich eine Funktion nicht mit den
selben Parametern wieder auf. Vielmehr benötigen verschiedene Pfade die
selben Ergebnisse, so dass es vorkommt, dass die selben Parameter
übergeben werden. Allerdings nicht direkt in Folge.
> Bei Fibonacci oder auch Fakultät ruft sich eine Funktion nicht mit den> selben Parametern wieder auf. Vielmehr benötigen verschiedene Pfade die> selben Ergebnisse, so dass es vorkommt, dass die selben Parameter> übergeben werden.
Dieses Laufzeitproblem kann sich mit Memoizing beheben lassen. Oder mit
geschickterer Wahl des Rückgabewerts. In Haskell könnte man die
Rekursion etwa so implementieren, um lineare Laufzeit und konstanten
Speicherbedarf zu erhalten:
1
fib n = fst (fib' n)
2
where fib' 0 = (0, 1)
3
fib' n = let (a, b) = fib' (n - 1) in (b, a + b)
In C++ könnte man dieselbe Idee so umsetzen:
1
intfib(intn){
2
returnfib_helper(n).first;
3
}
4
pair<int,int>fib_helper(intn){
5
if(n==0)
6
returnmake_pair(0,1);
7
pair<int,int>x=fib_helper(n-1);
8
returnmake_pair(x.second,x.first+x.second);
9
}
Diese Rekursion wird ein guter Compiler mittels tail call optimization
komplett wegoptimieren. Ein Teil der Unübersichtlichkeit des Codes kommt
natürlich daher, dass C++ keine built-in Tuples kennt wie andere
Sprachen.
Interessanterweise hat eine naive iterative Lösung in C++ genausoviele
Zeilen wie die obige rekursive Variante:
1
intfib(intn){
2
intlast=0,current=1;
3
for(inti=0;i<n;++i){
4
inttemp=last+current;
5
last=current;
6
current=temp;
7
}
8
returnlast;
9
}
Ich würde aber zustimmen, dass in C++ die iterative Variante trotz
identischer Code-Länge einfacher zu verstehen ist als die rekursive. In
rein funktionalen Sprachen wie Haskell dagegen kann man eine iterative
Version wie in C++ gar nicht hinschreiben aufgrund des Fehlens von
veränderbaren Variablen. Dennoch ist es in Haskell möglich eine sehr
kompakte Variante des rekursiven fib-Algorithmus zu schreiben, der in
linearer Zeit läuft:
1
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fibs ist dann die (unendliche) Liste der Fibonacci-Zahlen. Die Funktion
fib ist also nur noch ein Elementzugriff dieser Liste:
Wir haben also gelernt:
- Schleifen sind, egal wie man sie schreibt, unlogisch.
- Rekursion ist Teufelszeug.
Also bleibt für die Fibonacci-Berechnung nur noch folgendes übrig:
Chris schrieb:
> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Das ist genau das, was ich an Funktionalsprachen so cool finde *. Man
kann mal eben in einer Zeile eine unendliche Liste mit nichttrivialem
Inhalt hinschreiben. Und die Ausführungszeit dafür ist trotzdem
endlich, sie dürfte sogar verschwindend gering sein.
Und der Code ist absolut selbsterklärend, selbst für einen Nicht-
Haskellianer wie mich. Ich glaube, ich muss mir demnächst doch mal ein
Haskell-Tutorial reinziehen.
*) ... und weswegen ich Peters Argument falsch finde, ein Compiler
dürfte kein schweres Leben haben ;-)
@Hagen Re:
Deinen Fibonacci-Algorithmus finde ich ebenfalls cool. Er ist zwar
nicht ganz selbsterklärend ;-), scheint aber in logarithmischer Zeit
zu laufen (unter der Annahme, dass die Einzeloperationen in konstanter
Zeit laufen) und benötigt im Gegensatz zu obiger Lösung nur
Integer-Operationen.
yalu wrote:
>> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)> Und der Code ist absolut selbsterklärend, selbst für einen Nicht-> Haskellianer wie mich.
Das ist schön für Dich.
Aber für mich wäre er in Chinesich geschrieben genau gleich gut zu
verstehen (also wie das Uhrwerk fürn Schwein).
+ in Klammern finde ich schonmal lustig, muß also was völlig anderes
sein als + ohne Klammern, aber was ?
"zipWith" und "tail" sind das reservierte Wörter in Haskell oder
Biblitoheken oder eigene Funktionen, was machen die ?
Was machen die : ?
Wie würde denn mein SPI-Beispiel in Haskell aussehen ?
Ich komme leider aus der Hardwareentwicklung, d.h. ich denke in
Abläufen, also was passiert wann.
Timingdiagramme liebe ich, da versteht man sofort, was wie passiert.
Für mich ist nicht wichtig, was passiert, sondern wann es passiert.
Da sieht man immer wieder schöne Ablauffehler, wenn man sich Quelltexte
von reinen Softwareentwicklern ansieht.
In der Hardware ist nicht das Ergebnis allein wichtig, sondern stimmt
auch der Weg bis dahin.
Z.B. muß ich einen Kondensator über einen Widerstand laden, dann braucht
das eine bestimmte Zeit und eine bestimmte Spannung.
Der Softwerker würde einfach die Zeit verkürzen und die Spannung erhöhen
(z.B 10000V).
Das Ergebnis wäre theoretisch das gleiche, aber praktisch ist die
Schaltung schon längst durchgebrannt.
Schleifen sind das direkte Äquivalent zur Rückkopplung, praktisch keine
Schaltung funktioniert ohne Rückkopplung.
Daher sind Schleifen für Hardwerker super einfach zu verstehen.
Peter
@Peter Dannegger:
> yalu wrote:>>>> fibs = 0 : 1 : zipWith (+) fibs (tail fibs)>>> Und der Code ist absolut selbsterklärend, selbst für einen Nicht->> Haskellianer wie mich.>> Das ist schön für Dich.>> Aber für mich wäre er in Chinesich geschrieben genau gleich gut zu> verstehen (also wie das Uhrwerk fürn Schwein).
Naja, ich geb zu, die Syntax ist schon etwas kryptisch, aber wer C
kann, sollte durch kryptische Syntaxen nicht mehr abgeschreckt werden
können :-)
> + in Klammern finde ich schonmal lustig, muß also was völlig anderes> sein als + ohne Klammern, aber was ?
Chris mag mich korrigieren, wenn ich jetzt Krampf erzähle. Wie schon
geschrieben, kann ich kein Haskell.
Aber ich schätze mal, ein + in Klammern notiert die Additionsfunktion
als solche, die als Argument (ähnlich einem Funktionspointer in C) an
die Funktion zipWith übergeben wird. Ohne die Klammern würde
wahrscheinlich versucht, zipWith mit fibs zu addieren, was wenig Sinn
ergibt.
> "zipWith" und "tail" sind das reservierte Wörter in Haskell oder> Biblitoheken oder eigene Funktionen, was machen die ?>> Was machen die : ?
Es sind Funktionen. Ob die bereits in der Sprache definiert sind und
damit Schlüsselwortcharakter haben, oder ob es Bibliotheksfunktionen
sind, weiß ich nicht, ist zum Verständnis aber unerheblich.
tail <liste>
liefert als Ergebnis alle Elemente der Liste außer dem ersten (Vom
Namen her könnte es auch sein, dass sie nur das letzte Element
liefert, aber wie soll das bei einer unendlich langen Liste gehen?).
zipWith <funktion> <liste1> <liste2>
bildet aus den Elementen der beiden Listen Paare (zip ==
Reißverschluss *) und lässt auf jedes dieser Paare die Funktion los.
Die Doppelpunkte sind wohl die Trennzeichen der Elemente einer Liste.
In dem Beispiel wird also rekursiv eine Liste fibs gebildet, deren
erste Elemente 0 und 1 sind, und deren restliche Elemente sich aus der
paarweisen Addition der Ergebnisliste fibs mit der Ergebnisliste ohne
das erste Element (tail fibs) ergeben:
fibs = 0 1 1 2 3 5 ... (Ergebnis vorweg genommen)
tail fibs = 1 1 2 3 5 ... (Ergebnis ohne die 0)
------------------------------------------------------
Summe = 1 2 3 5 8
Diese Summenliste wird an die beiden Anfangselemente 0 und 1
angehängt:
fibs = 0 1 1 2 3 5 8 ...
fertig.
> Wie würde denn mein SPI-Beispiel in Haskell aussehen ?
Weiß ich nicht. Zum Schreiben von Programmen braucht's etwas mehr
Kenntnisse als zum Lesen. Vielleicht hat Chris einen Vorschlag.
Und wenn ich irgendwann ein Haskell-Tutorial durchgelesen habe, werde
ich die Lösung hier posten (falls man in Haskell wirklich alles machen
kann und das Tutorial von guter Qualität ist ;-)).
> Ich komme leider aus der Hardwareentwicklung, d.h. ich denke in> Abläufen, also was passiert wann.
Leider? Ich mache auch etwas Hardwareentwicklung, habe es aber bisher
nicht bereut. Oft denke ich bei der Hardwareentwicklung auch in
Abläufen. Aber bei einem gegengekoppelten Verstärker (wo du weiter
unten das Thema Rückkopplung ansprichst) denke ich eher in Richtung
Fixpunktbestimmung einer Funktion.
> Timingdiagramme liebe ich, da versteht man sofort, was wie passiert.> Für mich ist nicht wichtig, was passiert, sondern wann es passiert.
Dass dir völlig egal ist, was in deiner Schaltung passiert, kann ich
eigentlich nicht ganz glauben.
> Da sieht man immer wieder schöne Ablauffehler, wenn man sich> Quelltexte von reinen Softwareentwicklern ansieht.>> In der Hardware ist nicht das Ergebnis allein wichtig, sondern> stimmt auch der Weg bis dahin.
Klar. Aber es muss halt beides stimmen: Der korrekte zeitliche Ablauf,
aber auch die Rechenergebnisse, die irgendwelche Algorithmen
ausspucken. Falsche Ergebnisse zum richtigen Zeitpunkt sind mindestens
genauso schlecht wie richtige Ergebnisse zum falschen Zeitpunkt.
> Z.B. muß ich einen Kondensator über einen Widerstand laden, dann> braucht das eine bestimmte Zeit und eine bestimmte Spannung. Der> Softwerker würde einfach die Zeit verkürzen und die Spannung erhöhen> (z.B 10000V).
Wenn's der Kondensator und die Platine mitmachen, warum nicht? Zeit
ist Geld :-) und warten tut keiner gerne.
> Schleifen sind das direkte Äquivalent zur Rückkopplung, praktisch> keine Schaltung funktioniert ohne Rückkopplung. Daher sind Schleifen> für Hardwerker super einfach zu verstehen.
Hmm, wenn ich mir die Übertragungsfunktion, z. B.
y = f(x1, x2, x3, 0)
einer offenen (also nicht rückgekoppelten) Schaltung anschaue und
schließe nun den Rückkopplungspfad
y = f(x1, x2, x3, y)
dann sieht das für eher nach einer Rekursion als nach einer Schleife
aus.
In der Schaltung ist die Rückkopplung natürlich als Draht- oder
Leiterbahnschleife realisiert, aber diese Sorte Schleife hat ja nun
wirklich nicht viel mit einer Softwareschleife zu tun.
*) Beim Erraten der Funktion von zipWith hatte ich zugegebenermaßen
den Vorteil, dass ich hin und wieder etwas in Python mache. Dort gibt
es eine Funktion zip, die die Elemente von n Listen zu n-Tupeln
zusammenfasst. Die dem zipWith entsprechende Funktion heißt in Python
allerdings map.
Wem das nicht kryptisch genug war, der kann sich mal die diversen
Varianten von Fibonacci in APL auf der Zunge zergehen lassen:
http://www.dyalog.dk/dfnsdws/n_fibonacci.htm (Font beachten, IE7 geht,
Opera nicht).
>Deinen Fibonacci-Algorithmus finde ich ebenfalls cool. Er ist zwar>nicht ganz selbsterklärend ;-), scheint aber in logarithmischer Zeit>zu laufen (unter der Annahme, dass die Einzeloperationen in konstanter>Zeit laufen) und benötigt im Gegensatz zu obiger Lösung nur>Integer-Operationen.
Das ist der Sinn ;) Der Algo. ist von der Komplexität her der schnellste
um Fibonacci zu berechnen. Und ich meine damit nicht Zahlen nur im
Double Bereich, sondern mit Millionen von Stellen.
Gruß Hagen
@Hagen Re:
Funktioniert hat der Algorithmus bei mir aber trotzdem nicht. F ist am
Anfang 1, wird etliche Male quadriert und am Schluss als Ergebnis
zurückgegeben. Kann es sein dass da beim Kopieren irgendwo eine Zeile
verloren gegangen ist?
Ich habe mal versucht, etwas nach dem gleichen Prinzip in C aufzubauen:
Das ist das Original ;)
1.) du hast zweimal b quadriert, das kannst du in eine Variable rechnen
und sparrst eine Quadrierung
2.) 2ab kann man per Quadrierung mit anschleißender Subtraktion
berechnen.
Man hat also 3 Quadrierungen wenn man's bischen umschreibt. Das Original
ist für eine reine Integer Version mit sehr kleinen Zahlen brauchbar.
Aber bei richtig großen Zahlen ist es so das eine Quadrierung 1.5 ma
schneller geht als eine Multiplikation mit gleichgroßen Zahlen.
Der Trick ist also 2ab + b² = (a + b)² - b²
Hier mal mein Source der mit meiner Large Integer Bibliothek arbeitet.
der letzte Teil ist der den ich oben als Pseudocode gepostet habe. Der
Code besteht aus 3 Teilen, einmal Fib() mod M, also Fibonacci modular
reduziert, einmal modular zu 2^x und einmal zu einem normalen Modulus.
Der letzte Teil ist ohne modulare Reduktion.
Gruß Hagen
PS: falls du weitergehendes Interesse hast schick mir ne PN, ich will
ungern diesen Thread kapern
PPS: im Bereich N < 2^32 ist sowieso eine Lookup Tabelle die schnellste
Variante.
> Man hat also 3 Quadrierungen wenn man's bischen umschreibt.
Klar kann man das Ganze noch optimieren, wobei das für normale
32-Bit-Integers der Compiler schon tut. Der Unterschied zwischen der
Multiplikation verschiedener Zahlen und der Quadrierung kommt hier
auch nicht zum Tragen und die Multiplikation mit zwei geht sowieso
fix.
Aber du hast schon recht, wenn man das Ganze mit großen Zahlen
rechnet, muss man etwas umdenken.
> PS: falls du weitergehendes Interesse hast schick mir ne PN, ich> will ungern diesen Thread kapern
Vielen Dank für das Angebot. Aber im für's Erste ist mein Durst nach
Fibonacci-Zahlen gelöscht. Ich beschäftige mich normalerweise mit
anderen Dingen, trotzdem war es eine sehr interessante Diskussion.
Was mich höchstens noch interessieren würde: Wozu brauchst du diese
Monster-Fibonacci-Zahlen? Hat das etwas mit Kryptographie zu tun?
>Was mich höchstens noch interessieren würde: Wozu brauchst du diese>Monster-Fibonacci-Zahlen? Hat das etwas mit Kryptographie zu tun?
Jain ;) Ich benutze Fibonacci/Fakultät/Berchnung von Konstanten wie Pi
oder e mit Millionen Stellen, als Testsuite. Zu diesen Zahlen findet man
Vergleichssoftware bzw. Testdaten im Netz. Damit teste ich ob meine
Langzahl Bibliothek korrekt läuft und ob die Performance sehr gut ist im
Vergleich zu anderen. Zb. meine Pi Berechnung, ohne großartige
Optimierung, ist auf Rangliste 4 aller PC Softwares die Pi berechnen.
Die Bibliothek ansich ist für kryptograhische Funktionen geeignet und
für andere Mathematische Berechnungen, also relativ universell und in
weiten Zahlenbereichen sehr performant.
Und warum mache ich das ? Einfach aus Interesse, ich finde es spannend
ausgehend von einer komplexen mathematischen Formel, also sehr sehr
abstrakt, eine reale Implementierung in Software zu bauen. Mann arbeitet
auf sehr hohem Level kann aber bis runter auf Assemblerebene
implementieren. Das macht Spaß, und man ist nicht abhängig von
irgendwelchen Mist von Micrososft oder muß bunte GUIs programmieren,
also quasi als Entspannungsaufgabe fürs Hobby ;)
Gruß Hagen
Hagen Re wrote:
> Zb. meine Pi Berechnung, ohne großartige> Optimierung, ist auf Rangliste 4 aller PC Softwares die Pi berechnen.
Ui, hast du mal nen Link oder sowas?
Nöö hab ich nicht mehr, kannst aber ne komplierte EXE haben und selber
vergleichen. Suche mal nach FastPI, SuperPI da gibts ne WEB Seite wo
alle PC Programme aufgelistet und verglichen werden. Das letzte mal bei
dem ich daran gearbeitet habe ist auch schon wieder 5 Jahre her.
Wie gesagt, schick mir ne PN und ich kann dir mein Pi/Faktorial Program
mailen.
Gruß Hagen