Codex @codex  0

An absolute spreadsheet reference, such as $F$1, fixes both coordinates when its spreadsheet formula is copied. In the spreadsheet tabular model, every copied total reads the same tax rate. Absolute addressing retains the spreadsheet cell reference, not the value: changing the input in F1 changes the computed totals even though the references remain $F$1.

A numerical value retained for reuse by memoization. It is usable only while the spreadsheet formula and all its relevant inputs remain valid. After changing A1 from 3 to 5, following outgoing directed edges finds exactly B1,B2,C1,D1. Invalidate their cached cell values before evaluating another requested result; install the new input value for A1. The cached cell values of A2 and E1 remain valid because neither has a directed path from A1.

One recomputation in the restricted topological order B1,B2,C1,D1 gives $9,10,19,19/2$. Four spreadsheet formulas are recomputed, while E1 stays at 16. Removing invalid values from the cache prevents a subtle error: a finished marker from the previous evaluation does not prove that the old value is correct after an edit. The affected set is conservative; a changed prerequisite might leave a consumer's value numerically equal, but this simple scheme still invalidates it. For a formula edit, update the incoming directed edges and corresponding outgoing consumer lists as well as invalidating the edited spreadsheet cell and its downstream consumers. Microsoft's documentation explicitly describes both direct and indirect dependents being marked for recalculation.^[ref]

For demand-driven evaluation, memoization combines with depth-first search. Each spreadsheet cell has one of three states: UNSEEN means no valid cached cell value; ACTIVE means its evaluation is on the current call stack; FINISHED means a valid value is available. Initialize valid input spreadsheet cells as FINISHED. Start with all spreadsheet formulas UNSEEN, or retain only valid FINISHED entries after invalidation. The following original algorithm uses an ordered references list and an apply_formula operation for each spreadsheet formula:

def value(cell):
    if state[cell] == FINISHED:
        return cache[cell]
    if state[cell] == ACTIVE:
        i = stack.index(cell)
        raise CircularReference(stack[i:] + [cell])
    state[cell] = ACTIVE
    stack.append(cell)
    try:
        args = [value(p) for p in references[cell]]
        cache[cell] = apply_formula(cell, args)
        state[cell] = FINISHED
        return cache[cell]
    except Exception:
        state[cell] = UNSEEN
        raise
    finally:
        stack.pop()

Requesting D1 first makes D1,C1,B1 active, then reads the finished inputs A1,A2. B1 finishes at 7. Evaluating B2 reuses the finished value of A1 and finishes at 6; C1 finishes at 13 and D1 at $13/2$. A later request for D1 immediately returns its cached cell value. The shared prerequisite A1 is not a directed cycle: it was finished before the second request. The crucial distinction is between a previously visited vertex and a still-active vertex. The exceptional path restores unfinished states while unwinding the call stack, so failed evaluations are not cached as successful results. MIT's depth-first search notes use stack-duration marks to distinguish an edge to an active ancestor and to detect a directed cycle.^[ref]

With adjacency lists and constant-time state/cache access, the structural work of a successful demand-driven evaluation is $O(|V_R|+|E_R|)$ in big O notation, where $V_R$ and $E_R$ are the requested spreadsheet cells and their recursively reached prerequisites and references. Each reached spreadsheet formula is computed once; each reference is inspected once. This time complexity counts dependency bookkeeping separately from the cost of the arithmetic operations. Detecting a spreadsheet circular reference can additionally scan the current call stack once to report its witness.

A different interpretation can treat cyclic spreadsheet formulas as simultaneous equations and seek a fixed point by repeated numerical updates. This requires an explicit update rule, initial values and stopping condition. It is not automatically the meaning of a spreadsheet formula. In particular, a directed cycle alone tells us neither whether a fixed point exists nor whether a chosen update rule approaches it.

Two original toy examples make the distinction exact. The cyclic pair X1=Y1+1, Y1=X1+1 has no solution over the real numbers: substitution gives $X1=X1+2$. For X1=Y1, Y1=X1, every equal pair is a fixed point, so there is no unique answer. Simultaneously updating both spreadsheet cells from the previous pair gives $(x_{n+1},y_{n+1})=(y_n,x_n)$. Starting at $(0,1)$ produces the periodic sequence $(0,1),(1,0),(0,1),\dots$, which does not approach a fixed point. Updating X1 first and immediately using its new value for Y1 instead gives $(1,1)$ in one sweep. That difference follows from the specified rules, not from a claim about any current spreadsheet product. Numerical iteration can be useful for a deliberately chosen model with a justification such as the contraction mapping theorem; ordinary acyclic spreadsheet dependency evaluation already has its answer from prerequisite order.

A mixed spreadsheet reference fixes exactly one coordinate. $A2 fixes column A and lets the row follow the copy; B$1 fixes row 1 and lets the column follow the copy. Put $2,3,4$ in A2:A4 and $5,6,7$ in B1:D1. Store =$A2*B$1 in B2, then fill the rectangle B2:D4. The colon denotes the inclusive rectangular range between the named corner spreadsheet cells. Each spreadsheet formula reads its row's factor from column A and its column's factor from row 1, producing a multiplication table.

Copying from B2 to D4 moves two columns right and two rows down. The mixed spreadsheet references become $A4 and D$1, so D4 contains =$A4*D$1 and has value $4\cdot 7=28$. For comparison, under that same displacement A2 becomes C4, $A$2 remains $A$2, $A2 becomes $A4, and A$2 becomes C$2. These four cases express the independent choice for each coordinate. Microsoft's official table demonstrates the same four possibilities for a two-row, two-column copy. ^[ref]

The filled rows have values $(10,12,14)$, $(15,18,21)$, and $(20,24,28)$. The multiplication table works because the left factor moves only vertically and the top factor moves only horizontally. Without the anchors, copying =A2*B1 from B2 to D4 would give =C4*D3, reading interior results rather than the intended boundary inputs.

// Target: computer-science.bigb

A relative spreadsheet reference, such as A2, allows both coordinates to change when its spreadsheet formula is copied. From C2, A2 means two columns left, in the same row. Copy =A2*B2 from C2 to C4: the displacement is zero columns and two rows, so it becomes =A4*B4. The row number changes to retain the same positional relationship to the spreadsheet formula.

Software consists of instructions and associated data used by a computer. A spreadsheet is software that stores spreadsheet cells and evaluates their spreadsheet formulas.

A spreadsheet is software for organizing information in a rectangular grid of spreadsheet cells and calculating with it. Rows are numbered and columns are lettered: B3 is the spreadsheet cell at column B, row 3. A spreadsheet cell can hold a label, a numerical input, or a spreadsheet formula whose value supplies an output. This brings a mathematical model close to its data: quantities, assumptions and results can be read side by side. The address convention is described in LibreOffice's official help. ^[ref]

The useful idea is to write a relationship once and reuse it across similar rows. Relative spreadsheet references follow each row's data; absolute spreadsheet references retain a shared assumption; mixed spreadsheet references let one coordinate vary while the other stays fixed. Spreadsheet dependency evaluation then computes the resulting spreadsheet formulas. A rectangular layout organizes the model for its reader, while the spreadsheet dependency graph organizes its calculation.

An addressed entry of a spreadsheet, such as A1. Here it stores either a literal numerical input or a spreadsheet formula; its current value is distinct from the stored formula. A cached cell value records a previously computed value, not an instruction to compute it again.

In a spreadsheet tabular model, D2 can store =C2*(1+$F$1) while displaying 9. The spreadsheet cell reference D2 identifies the location, the spreadsheet formula describes the calculation, and 9 is the value obtained from the present inputs. Keeping those three ideas distinct makes copying and checking a model much easier.

A spreadsheet cell reference identifies the spreadsheet cell read by a spreadsheet formula. In A1 notation, B3 combines a column letter with a row number. For copying, the column and row can each be relative or absolute, independently: a $ immediately before a coordinate fixes that coordinate during the copy. The $ is an addressing marker, not a currency symbol. ^[ref]

Number columns as $A=1$, $B=2$, and so on. If a spreadsheet formula moves by $\Delta c$ columns and $\Delta r$ rows during copying, a referenced coordinate $(c,r)$ becomeswhere each $\epsilon$ is $1$ for a relative coordinate and $0$ for an absolute coordinate. This is a translation on the unfixed coordinates. For ordinary in-sheet references whose translated addresses exist, repeated copies compose by addition of their displacements: substitute the rule twice to obtain $c^{\prime \prime }=c+{\epsilon }_c(\Delta c_1+\Delta c_2)$, and likewise for the row. Copying therefore preserves either a fixed coordinate or an offset from the formula's location.

Evaluate numeric formula dependencies using depth-first search and memoization, or a topological ordering. Marking active evaluations detects cycles; repeated numerical sweeps need not terminate or determine a unique result.

A spreadsheet dependency graph turns a page of spreadsheet formulas into a plan: compute each prerequisite before the spreadsheet cell that consumes it. This section uses a deliberately small model with explicit cell references, fixed spreadsheet formulas, and deterministic computation from numerical inputs. There are no external data changes or formulas that change their references while running. Within these assumptions, a topological order gives a reproducible answer without repeatedly sweeping the visible grid.

Take two input spreadsheet cells and five spreadsheet formulas:

Our directed edge convention is prerequisite to consumer: A1 $\to$ B1 means that B1 reads A1, not the reverse. The seven directed edges are A1 $\to$ B1, A2 $\to$ B1, A1 $\to$ B2, B1 $\to$ C1, B2 $\to$ C1, C1 $\to$ D1, and A2 $\to$ E1. This spreadsheet dependency graph is a Directed acyclic graph. One topological order is A1,A2,B1,B2,C1,D1,E1; E1 could instead be computed immediately after A2. A topological order constrains prerequisites, not the physical positions of spreadsheet cells.

In that order, the initial arithmetic operations give $B1=3+4=7$, $B2=2\cdot 3=6$, $C1=7+6=13$, $D1=13/2$, and $E1=4^2=16$. The spreadsheet formulas define one value per spreadsheet cell: an outline by induction along any topological order shows that every prerequisite already has its uniquely determined value when its consumer is computed. Different permitted orders therefore agree in this model. The useful idea is that information flows through the Directed acyclic graph even when the visible grid does not display that flow.

A concrete implementation history illustrates this separation. Microsoft's documentation distinguishes the per-worksheet calculation chains used in Excel 2002 and earlier from calculation using multiple software threads introduced in Excel 2007 for independent chain sections. This is a documented implementation example, not a definition of spreadsheet dependency evaluation.^[ref]