Archiv für die Kategorie ‘Math’

Rekursiv vs. Iterativ

Sonntag, 29. Januar 2012

In der dotnetpro 8/2011 hat Ralp Westphal im Artikel “Aus Baum mach Fluss” zum Einstieg die Fakultätsberechnung in der rekursiven und in der iterativen Variante gezeigt. Seiner Meinung nach ist die iterative Variante einfacher zu verstehen, besonders für nicht-Mathematiker.
Ich fragte mich dann, welche Variante ist für den Computer einfacher zu verstehen, d.h. welche Variante ist performanter? Oder ist es egal, optimiert der Compiler schon so weit, dass beide Varianten in etwa gleich schnell sind?

Ich habe ein kleines Programm geschrieben, dass die Fakultät für verschiedene Werte mehrmals berechnet, um messbare Werte zu erhalten.
Hier die Resultate:

Factorial recursive and iterative
---------------------------------

10!
Recursive: 00:00:00.0390023
Iterative: 00:00:00.0220012

100!
Recursive: 00:00:00.2940168
Iterative: 00:00:00.1720099

1000!
Recursive: 00:00:02.5131437
Iterative: 00:00:01.0270588

10000!
Recursive: 00:00:25.0624335
Iterative: 00:00:09.4535407

Die rekursive Variante braucht also etwa 2.5 mal so lang wie die iterative. Und bei grossen Fakultäten kommt noch ein weiteres Problem hinzu: Es wird eine StackOverflowException geworfen, da jeder Rekursionsschritt einen Funktionsaufruf zur Folge hat, der einen Teil des Stacks beansprucht.

Fazit:
Der iterative Ansatz ist (mindestens in diesem Fall) auch für den Computer “einfacher zu verstehen”. Neben der besseren Performance ist aber auch die gebannte Gefahr des Stack Overflows ein wichtiger Grund, die iterative Varinate vorzuziehen.

Factorial Source Code

Fläche zu Umfang Teil 2: der Kreis

Donnerstag, 15. November 2007

Nach dem Blogeintrag Fläche zu Umfang oder warum die Biene Waben baut stellt sich die Frage, welche Form das beste Fläche-zu-Umfang-Verhältnis hat.
Wenn man vom Dreieck über das Viereck, das Fünfeck, das Sechseck usw. das Verhältnis ausrechnet, sieht man, dass das Verhältnis immer besser wird, je mehr Ecken das n-Eck hat. Deshalb hat das beste Verhältnis das n-Eck mit n gegen unendlich, sprich der Kreis.

AQuadrat = s2UQuadrat = 4s

AKreis = r2 πUKreis = 2 r π

Bei gleichem Umfang von Quadrat und Kreis ergibt sich:

UQuadrat = UKreis = 4s = 2 r πr = 2s / π

AKreis = r2 π = (2s / π)2 π = 

      = 4s2 π

Wenn wir nun die beiden Flächen vergleichen ergibt sich:

AKreis / AQuadrat = 4s2 π / ( s2) =

                = 4 / π = ~1.27

Fläche zu Umfang oder warum die Biene Waben baut

Montag, 12. November 2007

Beim Morgenessen stellte sich die Frage, warum die Bienenwaben sechseckig sind. Auf meine Antwort, dass das Sechseck die Form mit dem besten Fläche-zu-Umfang-Verhältnis ist, die ohne Zwischenräume aneinander gereiht werden kann, wurde mit Skepsis reagiert.

Also musste dies mathematisch bewiesen werden:

AQuadrat = s2

UQuadrat = 4s
ASechseck = 3a2 sqrt(3) / 2

USechseck = 6a

Bei gleichem Umfang von Quadrat und Sechseck ergibt sich:

UQuadrat = USechseck = 4s = 6a

a = 4s / 6

a = 2s / 3

ASechseck = 3 (2s / 3)2 sqrt(3) / 2 =
         = 3 * 4 s2 sqrt(3) / (9 * 2) = 2 s2 sqrt(3) / 3

Wenn wir nun die beiden Flächen vergleichen ergibt sich:

ASechseck / AQuadrat = 2 s2 sqrt(3) / (3 * s2) =
                   = 2 sqrt(3) / 3 = ~1.15

Das heisst, bei gleichem Umfang hat das Sechseck etwa 15% mehr Fläche.