mikrocontroller.net

Forum: Compiler & IDEs for(; ;) - Schleife


Autor: Marcus Zinn (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo !
Für ein Projekt habe ich diese for-Schleife entdeckt!
Was macht diese ?

for(;;)

Ist das eine Schleife die nie endet ?

Mfg Marcus Zinn

Autor: Johannes M. (johnny-m)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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
while(1);
wobei an Stelle der "1" auch alles stehen kann, was nicht Null ist.

Autor: Marcus Zinn (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok...danke..!

Autor: Rufus Τ. Firefly (rufus) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Naja,
for(;;)

ist unvollständig.

Erst durch ein angehängtes Semikolon wird 'ne Endlosschleife draus. 
Sonst wird der auf das for-Statement folgende Block ewig wiederholt:
for(;;)
  machwas();

oder
for(;;)
{
  machwas();
}

Und dann lässt sich die vermeintlich endlose Schleife auch verlassen:
for(;;)
{
  if (machwas())
    break;
}

Autor: Peter S. (psavr)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
for(;;) finde ich hässlich!

while(1) ist hingegen logisch und völlig selbsterklärend!

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Und weil ältere Compiler mit wenig Sinn für Optimierung einzig daraus 
wirklich eine Schleife ohne sinnlosen Test gemacht haben.

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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".

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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)?

Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
...rage ich mich immer, warum nicht while(2) oder while(-1) oder
while(0.0745)?...


Geht auch...

Autor: PS (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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:
loop
   Do_Something;
end loop;

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> ...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:
#define loop for(;;)

loop {
  // Code
}

Dann sieht's fast aus wie in Ada. Oder
#define loop for(;;) {
#define end_loop }

loop
  // Code
end_loop

Jetzt sieht's noch mehr nach Ada aus, dafür aber leider nicht mehr
nach C.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Anderer Vorschlag
#define loop while(1)

loop {
  // Code
}

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

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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:
loop:
   do_something();
goto loop;

@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.

Autor: Johannes M. (johnny-m)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@Hagen Re:
for(a; b; c)
{
    //...
}
ist in C im Prinzip nichts anderes als eine Kurzschreibweise für
a;
while(b)
{
    //...
    c;
}
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.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Johannes M. wrote:
> @Hagen Re:
>
> for(a; b; c)
> {
>     //...
> }
> 
> ist in C im Prinzip nichts anderes als eine Kurzschreibweise für
> [...}

Nicht eher
a;
do
{
   //...
c;
} while(b);

?

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nein.

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;)

Autor: Rufus Τ. Firefly (rufus) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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);

Autor: Michael Wilhelm (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>"pre-check-loop"
>"post-check-loop"

Früher hat soetwas noch kopf- bzw. fußgesteuerte Schleife geheißen.

MW

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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. :-)

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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).

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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. ;-)

Autor: Werner B. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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
while(!0)
{
}

Bleibt dann auch gültig, und die Frage warum 1 und nicht 2 erübrigt sich 
;-)

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: jemand (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
while(!0)
{
}
>>Bleibt dann auch gültig

Nein. Weil 0 gleich 1 ist, also steht da praktisch while(!1), also wird 
auch dieses nicht funktionieren xD

Autor: Philipp Burch (philipp_burch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wenn sie schon eine extra Konstruktion für Endlosschleifen einbauen, 
wäre meiner Meinung nach sowas wie
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".

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Zur Not halt einfach:
#include <stdio.h>

#define forever for(;;)

int main()
{
    forever
    {
        puts("Hello, World");
    }
    return 0;
}

Wobei man da auch wieder darüber streiten könnte, ob im #define ein 
for(;;) oder ein while(1) steht ;-)

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So sieht's doch auch schick aus, nicht?
#define ever ;;

...

   for (ever) {
      ...
   }

;-)

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich biete noch an:
#define all ;
#define eternity ;

for (all eternity)
{
    ...
}
#define as
#define long for // wer braucht schohn den Datentyp?
#define the (
#defie world ;
#define is ;
#define still ;
#define spinning )

as long as the world is still spinning
{
    ...
}

Autor: Matthias (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die spinnen, die Programmierer!

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
#define as
#define long for // wer braucht schohn den Datentyp?
#define the (
#defie world ;
#define is ;
#define still ;
#define spinning )

as long as the world is still spinning
{
    ...
}

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 :-)

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
zwei? ich habe im Moment des Auf-Absenden-Drückens einen gesehen. Oder 
meinst du meinen Tippfehler im Kommentar?

Autor: Marco S (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
#defie
for(;;;)

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Rolf Magnus wrote:

> zwei?

Innerhalb des for() dürfen nur zwei Semikolons sein, nicht drei.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
... 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.

Autor: Thomas B. (yahp) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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!

Autor: Peter S. (psavr)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
}
goto top_of_this_topic;    // Enlosschlaufe damit diese sinnlose
                           // Diskussion nie abbricht...

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>> 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.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ?
#include <io.h>

#define SPI_PORT        PORTB
#define SPI_SCK         PB0
#define SPI_DOUT        PB1


void spi_out( unsigned char dat )
{
  unsigned char i;

  for( i = 8; i; i-- ){
    SPI_PORT &= ~(1<<SPI_DOUT);
    if( dat & 1 )
      SPI_PORT |= 1<<SPI_DOUT;
    dat >>= 1;
    SPI_PORT |= 1<<SPI_SCK;
    SPI_PORT &= ~(1<<SPI_SCK);
  }
}


Peter

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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 ?
void spi_out2(unsigned char dat, unsigned char i)
{
    if (!i)
        return;

    SPI_PORT &= ~(1<<SPI_DOUT);
    if( dat & 1 )
      SPI_PORT |= 1<<SPI_DOUT;
    dat >>= 1;
    SPI_PORT |= 1<<SPI_SCK;
    SPI_PORT &= ~(1<<SPI_SCK);

    spi_out2(dat, --i);
}

void spi_out( unsigned char dat )
{
    spi_out2(dat, 8);
}

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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

Autor: Jörg Wunsch (dl8dtl) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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:
% avr-gcc -Os -mmcu=atmega1281 -S loop.c
loop.c: In function 'spi_out':
loop.c:8: sorry, unimplemented: inlining failed in call to 'spi_out2': recursive inlining
loop.c:19: sorry, unimplemented: called from here

Das bekommt man, wenn man __attribute__((always_inline)) dafür
benutzen möchte.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Rekursionen sind Teufelszeug, braucht man wie das Ozon zum Atmen.

Sie verschlechtern die Lesbarkeit und machen dem Compiler das Leben 
schwer.


Peter

Autor: Chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Rufus Τ. Firefly (rufus) (Moderator) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Die intensive Verbreitung von Haskell und Lisp auf allen 
Microcontrollersystemen spricht ja auch irgendwie für sich ...

Autor: Rolf Magnus (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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 :-)

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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...


>> 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

Autor: Chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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?

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>"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

Autor: Frank (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Chris (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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:
fib n = fst (fib' n)
  where fib' 0 = (0, 1)
        fib' n = let (a, b) = fib' (n - 1) in (b, a + b)

In C++ könnte man dieselbe Idee so umsetzen:
int fib(int n) {
  return fib_helper(n).first;
}
pair<int, int> fib_helper(int n) {
  if(n == 0)
    return make_pair(0, 1);
  pair<int, int> x = fib_helper(n - 1);
  return make_pair(x.second, x.first + x.second);
}
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:
int fib(int n) {
  int last = 0, current = 1;
  for(int i = 0; i < n; ++i) {
    int temp = last + current;
    last     = current;
    current  = temp;
  }
  return last;
}
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:
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:
fib n = fibs !! n

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
ich würde garnicht diesen Algo. benutzen sondern den hier


fibonacci(N)
begin
  F := 1;
  E := 0;
  T := 0;
  S := 0;
  Mask := 2^Log2(N);
  while Mask <> 0 do
  begin
    T := F + E;
    E := E^2;
    T := T^2;
    F := F^2;
    T := T - E;
    E := E + F; 
    if N and Mask <> 0 then
    begin
      S := T;
      T := T + E;
      E := S;
    end;
    S := T;
    T := E;
    E := S;
    Mask := Mask / 2;
  end;
  Return(F);
end;  

der ist von der Laufzeit her um vieles schneller als der simple rekusive 
Algo. Benutzt wird das Goldene Ratio.

Gruß Hagen

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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:
long fibonacci(n) {
  return lround((pow(((1+sqrt(5))/2),n)-pow(((1-sqrt(5))/2),n))/sqrt(5));
}

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.

Autor: Peter Dannegger (peda)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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.

Autor: Andreas K. (a-k)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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).

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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:
unsigned long fib(n) {
  unsigned long a=1, b=n, m=0, tmp;

  do {            // äquivalent zu
    m = b;        //   m = (int)floor(log2(n));
    b = m & m-1;  //   b = 0;
  } while(b);     //

  while(m) {
    tmp = a*a + b*b;
    b = 2*a*b + b*b;
    a = tmp;
    if(n & m) {
      tmp = b;
      b = a+b;
      a = tmp;
    }
    m /= 2;
  }
  return b;
}
So scheint's zu gehen.

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.
procedure NFibonacci(var R: IInteger; N: Cardinal; const M: IInteger);
// R := Fib(N) mod M, if M <> nil
var
  T,E,F: IInteger;
  Mask: Cardinal;
  I: Integer;
begin
  if M <> nil then
  begin
    I := NSgn(M, True);
    if I = 0 then NRaise_DivByZero;
    if I = 1 then
    begin
      NSet(R, 0);
      Exit;
    end;
  end;
  if N = 0 then
  begin
    NSet(R, 0);
    Exit;
  end;
  NSet(F, 1);
  Mask := 1 shl (DBitHigh(N) -1);
  if Mask > 0 then
  begin
    NSet(E, 0);
    if M <> nil then
    begin
      I := NLow(M) + 1;
      if I = NSize(M) then // M = 2^i
      begin
        while Mask <> 0 do
        begin
          NAdd(T, F, E);  NCut(T, I);
          NSqr(E);        NCut(E, I);
          NSqr(T);        NCut(T, I);
          NSqr(F);        NCut(F, I);
          NSub(T, E);     NCut(T, I);
          NAdd(E, F);     NCut(E, I);
          if N and Mask <> 0 then
          begin
            NSwp(T, E);
            NAdd(T, E);   NCut(T, I);
          end;
          NSwp(T, F);
          Mask := Mask shr 1;
        end;
        NAddMod(F, M, M);  // correct sign
      end else
      begin
      // montgomery version are always slower
        while Mask <> 0 do
        begin
          NAdd(T, F, E);
          NMod(T, M);
          NSqrMod(E, M);
          NSqrMod(T, M);
          NSqrMod(F, M);
          NSubMod(T, E, M);
          NAddMod(E, F, M);
          if N and Mask <> 0 then
          begin
            NSwp(T, E);
            NAddMod(T, E, M);
          end;
          NSwp(T, F);
          Mask := Mask shr 1;
        end;
      end;
    end else
// ------------------------------------ 
     while Mask <> 0 do
      begin
          // PHI = golden ratio
          // Square (E + F*PHI)
          // (E, F) := (E² + F², 2EF + F²)
        NAdd(T, F, E);        // F + E
        NSqr(E);              // E²
        NSqr(T);              // (F + E)²
        NSqr(F);              // F²
        NSub(T, E);           // (F + E)² - E² = 2EF + F²
        // above trick exchange 2EF multiplication by faster Squaring T² + one addition -E²
        NAdd(E, F);           // E² + F²
        if N and Mask <> 0 then
        begin
          // Multiply (E + F*PHI) by PHI
          // (E, F) := (F, E + F)
          NSwp(T, E);
          NAdd(T, E);
        end;
        NSwp(T, F);
        Mask := Mask shr 1;
      end;
  // Here, E + F*PHI = PHI^N, thus (E,F) = (F[N-1],F[N])
  end;
  NSwp(F, R);
end;


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.

Autor: yalu (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> 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?

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
>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

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: Hagen Re (hagen)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.