23. Cycles and Convergence
If a cell depends on itself, that forms a cycle and the spreadsheet may not converge when evaluated.Cycles which converge can be used to implement iterative algorithms. For example, the following spreadsheet uses Newton's method to find the square root of x:
% cat sqrt.ss x = 2; a0 = b0 ? b0 : x/2; b0 = (a0+x/a0)/2; format "%20.18g";Since a0 depends on b0, and b0 depends on a0, there is a cycle.
a0 will be set to b0 if b0 is non-zero, otherwise a0 will be set to x/2 to initialize the algorithm. So a0 represents the previous value of b0, and b0 represents the next estimate of the square root. Newton's method converges quickly:
% echo "print all; eval a0:b0 10; print values;" | SS -T sqrt.ss -
x = 2
| A | B | |
|---|---|---|
| 0 | B0 ? B0 : ((x/2)) | (A0+(x/A0))/2 |
| A | B | |
| 0 | 0 | 0 |
| eval: converged after 7 iterations | ||
| A | B | |
| 0 | 1.41421356237309492 | 1.41421356237309492 |
Finite element analysis is another application which requires iteration and can be set up in a spreadsheet. In the following small example, the value of each non-boundary cell is computed as the average of the cell's four nearest neighbors.
% cat cycles.ss // average of 4 nearest neighbors // R1C1:R5C5 = { (R[]C[-1] + R[]C[+1] + R[-1]C[] + R[+1]C[])/4 }; // fill r0c0:r0c6 1, 0; // boundary conditions, fill r1c0:r6c0 1, 0; // 1's top and left fill r1c6:r6c6 0, 0; // 0's right and bottom fill r6c1:r6c5 0, 0; // format "%6.4f"; format RC; % echo "print values; eval 1; eval 1000; print values;" | SS cycles.ss -
0 1 2 3 4 5 6 0 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 2 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 3 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 4 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 5 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 6 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000 eval: still changing after 1 iteration eval: converged after 75 iterations 0 1 2 3 4 5 6 0 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1.0000 1 1.0000 0.9374 0.8747 0.8040 0.7010 0.5000 0.0000 2 1.0000 0.8747 0.7576 0.6404 0.5000 0.2990 0.0000 3 1.0000 0.8040 0.6404 0.5000 0.3596 0.1960 0.0000 4 1.0000 0.7010 0.5000 0.3596 0.2424 0.1253 0.0000 5 1.0000 0.5000 0.2990 0.1960 0.1253 0.0626 0.0000 6 1.0000 0.0000 0.0000 0.0000 0.0000 0.0000 0.0000The spreadsheet may not converge when using operators ++, --, +=, *=, etc. and the rand, irand, or drand pseudo-random number generator functions, since they produce varying values on each evaluation. However, these operators and functions are still useful, in particular for Monte-Carlo simulations.
The following simple example generates pseudo-random values for a0, with b0 representing the sum, c0 the evaluation count, and d0 the average:
% cat rand.ss srand 34567; // just to make the docs reproducable, // remove to use default srand(time()) a0 = drand(); b0 += a0; d0 = b0/++c0; eval a0:d0 10; print values; % ss < rand.ss
eval: still changing after 10 iterations A B C D 0 0.91 5.37 10.00 0.54