Archiv der Kategorie: Math

Rekursiv vs. Iterativ revisited

1 Antwort

Im KaffeeKlatsch vom November 2012 habe ich einen interessanten Artikel über die Fakultätsberechnung gelesen.

Dies hat mich dazu bewogen, meine eigene Untersuchung nochmals hervorzuholen und zu überprüfen.

Ich habe dabei, wie im KaffeeKlatsch-Artikel, den Datentyp BigInteger (Namespace System.Numerics, Assembly System.Numerics.dll) eingesetzt. Ich habe auch noch die Schlaufe verkürzt, damit ich nicht so lange auf das Resultat warten muss. Weitere Optimierungen habe ich nicht vorgenommen.

Hier das Ergebnis:

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

10!
Recursive: 00:00:00.1390079
Iterative: 00:00:00.1190069

100!
Recursive: 00:00:01.9631122
Iterative: 00:00:01.7991029

1000!
Recursive: 00:00:51.7689611
Iterative: 00:00:43.3274782

10000!
Process is terminated due to StackOverflowException.

Es sind zwei Dinge ersichtlich:

  1. Die iterative Implementierung ist immer noch schneller als die rekursive, aber der Unterschied ist nicht mehr so gross. Dies dürfte darauf zurückzuführen sein, dass die eigentliche Berechnung (das Multiplizieren) mit dem BigInteger mehr Aufwand verursacht und der Overhead des rekursiven Aufrufs nicht mehr so ins Gewicht fällt. Dafür spricht auch, dass ich die Wiederholungszahl verkleinern musste.
  2. Es wird schon früher eine StackOverflowException geworfen. Dies dürfte auch daran liegen, dass mit dem BigInteger noch weitere Funktionsaufrufe einhergehen, die auf dem Stack gespeichert werden.

Fazit:
Meine erste Untersuchung wurde (ansatzweise) bestätigt, die Vereinfachung mit dem akzeptieren eines falschen Resultates mit dem int hat aber das Ergebnis stärker beeinflusst, als ich das vermutet hatte.

Factorial2 Source Code

Zwei Ansätze zur Preisgestaltung

1 Antwort

Heute habe ich zwei Artikel gelesen, die sich beide mit der Preisgestaltung befassen.

Während Ralf Westphal vorschlägt, sich mittels Experimenten an den optimalen Preis heranzutasten rät Joel Spolsky von Preisexperimenten ab, wenn man nicht sicherstellen kann, dass sich die Kunden nicht über die Preise unterhalten. In seinem Artikel „Camels and Rubber Duckies“ erläutert er dafür die Theorie zur Preisgestaltung, um sie dann aber wieder in den Müll zu werfen. Der Artikel enthält viel Interessantes, auch wenn er einem mit dem folgenden Schlusssatz entlässt:

(..) and I apologize for leaving you even less able to price software than you were when you started reading this.

Wieviel sind 72 Brontobytes?

Schreibe eine Antwort

In einer Pressemeldung in der iX zum Dateisystem GlusterFS bin ich über die maximalen Grösse von 72 Brontobytes gestolpert. Bronto(-bytes) hatte ich bis anhin noch nie gehört. Als offizieller SI-Einheitenpräfix existiert dieser Begriff (noch) nicht, weitere Recherchen ergaben aber, dass es sich um das Präfix für 1027 (oder auch hier) handelt.
Solche unvorstellbar grossen Zahlen schreien nach einem Vergleich, um sie fassbarer zu machen.

Die zur Zeit grössten erhältlichen Festplatten fassen 4 Terabyte. Somit müssten wir 18 * 1015 Festplatten einsetzen um das Dateisystem an das Limit zu bringen:

(72 * 1027) / (4 * 1012) = 18 * 1015

Wenn wir nun Server einsetzen, in denen wir auf einer Bauhöhe von 2 Units 12 Festplatten benutzen können und ein herkömmliches Rack mit 42 Units einsetzen können wir in einem Rack 21 Server einsetzen. Das Rack benötigt eine Standfläche von 0,6 m2. Dann benötigen wir für alle Racks (Seite an Seite und Tür an Tür) 42 * 106 km2 Standfläche:

(18 * 1015) / (12 * 21) * 0.6 m2 = 42 * 1012 m2 = 42 * 106 km2

Die Schweiz hat eine Fläche von ca. 42’000 km2. Daraus folgt, dass wir 1000 mal die Fläche der Schweiz benötigen würden, um alle Server aufzustellen.

Europa hat eine Fläche von 10,18 * 106 km2. Demzufolge wäre mehr als 4 mal die Fläche von Europa nötig für alle Server.

Zur Zeit wäre das Ausreizen des Dateisystems also noch ein Platzproblem, auch bei einem durchgängig vierstöckigen Rechenzentrum würde ganz Europa durch das Rechenzenter bedeckt.

Rekursiv vs. Iterativ

2 Antworten

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

Schreibe eine Antwort

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

2 Antworten

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.