Tabellenkalkulation - Software selbst programmieren, Berechnungsalgorithmus

Wie funktioniert eine Tabellenkalkulation?
Wie werden Spalten und Zeilen gehandhabt?
Welcher Berechnungsalgorithmus wird verwendet?

Falls jemand sich seine eigene Tabellenkalkulation programmieren will steht er vor obigen Fragen. Dazu einige Überlegungen:

Die einzelnen Zellen einer Tabellenkalkulation werden nicht nach Zeilen- und Spalten angesprochen, sondern nach Zellen-Nummern. Man kann sich vorstellen, dass die Zellen zeilenweise durchnummeriert sind. Die Zelle A1 hat die Nummer 1, B1 die Nummer 2 und so weiter. Hat also ein Tabellenkalkulationsblatt 4 Spalten, so beginnt A2 mit der Zellennummer 5.

Die Umrechnung von Zellennummer und Zeile bzw. Spalte (wobei S die Anzahl der Spalten pro Zeile ist) funktioniert dann so:

 

• Zellennummeri = (Zeilennummeri -1) * S + Spaltennummeri
• Zeilennummeri = integer [ ( Zellennummeri -1) / S + 1 ]
• Spaltennummeri = Zellennummeri modulo S

In einer Tabelle (indiziertes Feld) sind die Zellen der Reihe nach mit ihrer Zellennummer und der mathematischen Funktion (formelle Abhängigkeit von anderen Zellennummern) aufgelistet:

1. Zellennummer1 Funktion1
2. Zellennummer2 Funktion2
3. Zellennummer3 Funktion3
4. usw.

Durch Anlyse aller Funktionen kann eine Tabelle von gerichteten Graphen konstruiert werden (Beispiel):

   Graph vonZellennummer nachZellennummer:
   1 2
   2 3
   2 4
   3 4

Man sieht an dem Beispiel, dass Zelle (Knoten) 1 einen numerischen Wert enthält, da sie nur in der Spalte vonZellennummer einmal vorkommt und nicht in der nachZellennummer (kein Input aus bzw. Abhängigkeit von einer anderen Zelle).
Zelle 2 ist wiederum nur von Zelle 1 abhängig und Zelle 3 nur von Zelle 2.
Am Ende des Graphen ist die Zelle 4 die mit der höchsten Abhängigkeit von anderen Zellen (hängt von den Werten der Zelle 2 und 3 ab).

Erstellt man daraus eine Häufigkeitstabelle, indem man die Anfänge und Enden der jeweiligen Zellen zählt, erhält man:

   Häufigkeit - Zellennummer Anfänge Enden:
   1 1 0
   2 2 1
   3 1 1
   4 0 2

Zelle 1 hat einen Anfang und kein Ende, Zelle 2 hat zwei Anfänge und ein Ende, Zelle 3 hat einen Anfang und ein Ende und Zelle 4 hat keinen Anfang und zwei Enden.

Will man nun diesen "topologischen Baum" berechnen, so scheint eine Berechnungsreihenfolge der Zellwerte nach folgenden Kriterien optimal:

1. Zellen ohne Ende (Zelle 1) brauchen nicht berechnet werden (enthalten ohnehin nur numerische Werte).
2. Zellen mit vielen Anfängen müssen zuerst berechnet werden (Zelle 2).
3. Bei Zellen mit gleich vielen Anfängen müssen diejenigen Zellen zuerst berechnet werden, die weniger Enden aufweisen.

Zuletzt muss noch gewährleistet werden, wie oft diese Berechnungsreihenfolge abgearbeitet werden soll. Hier bietet sich das Prinzip der "minimalen Fehlerquadrate" an:

Dazu wird vor der Berechnung jeder Zelle der alte Zellwert gespeichert, von dem dann nach der Berechnung der Zelle der neue Zellwert abgezogen wird. Diese Differenz (Fehler) wird quadriert (Fehlerquadrat) und einer Gesamtfehlersumme hinzuaddiert. Die letztendlich resultierende Gesamtfehlersumme wird dann mit einer vorgegebenen Genauigkeit verglichen. Ist sie größer, muss noch ein Berechnungsdurchlauf gestartet werden.