Example
As an example of an unstable algorithm, consider the task of adding an array of 100 numbers. To simplify things, assume our computer only has two digits of precision (for example, numbers can be represented as 2.3, 77, 100, 110, 120, etc., but not 12.3 or 177).
The naive way to do this would be the following:
function sumArray(array) is let theSum = 0 for each element in array do let theSum = theSum + element end for return theSum end function
That looks reasonable, but suppose the first element in the array was 1.0 and the other 99 elements were 0.01. In exact arithmetic, the answer would be 1.99. However, on our two-digit computer, once the 1.0 was added into the sum variable, adding in 0.01 would have no effect on the sum, and so the final answer would be 1.0 – not a very good approximation of the real answer. Furthermore, we see that the algorithm depends on the ordering of elements within the array, in contrast to the exact arithmetic.
An example of a stable algorithm in this specific case is one that first sorts the array by the absolute values of the elements in ascending order and then sums them up using the pseudo code given above. This ensures that the numbers closest to zero will be taken into consideration first. Once that change is made, all of the 0.01 elements will be added, giving 0.99, and then the 1.0 element will be added, yielding a rounded result of 2.0 – a much better approximation of the real result.
However, for a larger array or for a computer with worse accuracy, sorting the array before adding the numbers together may not be enough. Consider for example the same task as above but with an array consisting of 1000 numbers instead of 100, and where all numbers have the value 1. In this case, sorting the numbers before summing them together will not have any effect since the numbers are all equally large. Once the calculated sum has reached 100, adding another number to it will no longer have any effect since the addition would be truncated down to 100 again. The calculated sum will therefore stop at 100 which is a very bad approximation of the actual sum which is 1000.
Instead, a stable algorithm for solving this more general problem can for example be a divide and conquer algorithm where the array is recursively split into two parts for which the sum is calculated respectively, and where these two sums then are summed together to give the final sum.
Read more about this topic: Numerical Stability
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)