[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Numeric instabilities - a brief show-and-tell demonstration



PureBytes Links

Trading Reference Links

Before we lay this topic to rest I would like to offer, as promised, two
short programs (summary of results attached) to demonstrate some dangerous
pitfalls described in my recent propositions. These were, briefly:

-- 1. feedback processes (iterations) can lead to extreme numeric
      instabilities, with errors larger than the signal itself;
-- 2. most software developers, and of course users, are totally
      unaware of these problems;
-- 3. the said instabilities usually cannot be detected from within
      a software package but only through recalculation
      at a higher precision;
-- 4. the instabilities are the ineluctable consequence of
      floating-point representation; though they cannot be avoided,
      the use of higher precision can, to a degree, delay some of the
      detrimental effects.

The iteration example demonstrated below uses no advanced mathematics, only
very simple basic math as probably used every day in EL programming (square
a number, then subtract 2). The formula I chose generates normalized numbers
that will not grow out of bounds, but will stay roughly between -2 and 2,
for easier handling. In spite of this simplicity you will see that after
less than 30 iterations (no 35000 are necessary!) the single-precision
calculation will create errors of a magnitude of more than 100%, with all
further iteration results in single precision proving totally meaningless
and belonging purely to the realm of chance.

Double precision fares somewhat better, though it also soon succumbs to the
relentless powers of instability. After 58 iterations, double-precision
results become equally worthless.

Let me also draw your attention to the fact that the errors do not merely
crop up in the last, most insignificant decimal places, but sooner rather
than later mercilessly destroy even the most significant digits.

To compare single precision with double precision I used C++; this language
will be familiar to many. To be able to verify, in turn, the double
precision results from C++, I had to resort to the arbitrary-precision
capabilities of Mathematica. I used an internal precision of 50 decimal
digits, which is sufficient to ensure a 19 digits precision in the result
after the one-hundredth iteration.

Here are the programs, first C++, then Mathematica:

-------------------------------------------------
#include <condefs.h>
#include <iostream.h>

int main(int argc, char **argv)
{
    float a[101];             // single precision
    double b[101];            // double precision

    a[0]=b[0]=0.5;           // initial condition

    for (int i=1; i<=100; i++)  // 100 iterations
    {
        a[i] = a[i-1]*a[i-1] - 2;
        b[i] = b[i-1]*b[i-1] - 2;
        cout<<"i="<<i<<"  a["<<i<<"]="<<a[i]<<"  b["<<i<<"]="<<b[i]<<"\n";
    }

    getchar();
    return 0;
}
--------------------------------------------------

a[0] = 0.5`50
Table[{i, a[i]=N[a[i-1]^2-2, 50], Precision[a[i]]}, {i,1,100}]

--------------------------------------------------

Please find the results in the attached text file. Single and double
precision results are rounded to 6 significant places, the Mathematica
results are given to the precision guaranteed to be correct (>=19).

I would like to add that this example is by no means contrived in any way. I
could easily demonstrate thousands of similar cases, and there is no doubt
in my mind that every one of us who uses any single-precision software at
all will, unwittingly and without any fault of his, already have fallen prey
to this phenomenon one time or another.

Michael Suesserott













#       single     double                Mathematica 50-digit precision           prec. of result
----------------------------------------------------------------------------------------------
1     -1.75       -1.75       -1.7500000000000000000000000000000000000000000000000   50
2     1.0625      1.0625      1.0625000000000000000000000000000000000000000000000    49
3     -0.871094   -0.871094   -0.871093750000000000000000000000000000000000000000    49
4     -1.2412     -1.2412     -1.241195678710937500000000000000000000000000000000    49
5     -0.459433   -0.459433   -0.459433287149295210838317871093750000000000000000    48
6     -1.78892    -1.78892    -1.788921054659193252080098129885854518761334475130    49
7     1.20024     1.20024     1.20023853980296029103616942146559932822994385585      48
8     -0.559428   -0.559427   -0.55942744757165770517872120586641774767987466760     47
9     -1.68704    -1.68704    -1.68704093090346016954118610226457525896711600101     48
10    0.846105    0.846107    0.8461071025436134700976808284823970380034397252       47
11    -1.28411    -1.2841     -1.2841027710252511601194596297119578400659285765      47
12    -0.351073   -0.35108    -0.3510800734452713896386367758411034230112671787      46
13    -1.87675    -1.87674    -1.8767427820296628468434453038037188577989524178      47
14    1.52218     1.52216     1.522163469900438591414894800333710715286642548        46
15    0.317038    0.316982    0.316981629099343421669929432001286780069937610        45
16    -1.89949    -1.89952    -1.899522646813526279727394621229285368058538031       46
17    1.60805     1.60819     1.60818628575746449957845858701433495072292888         45
18    0.585826    0.586263    0.58626312969838926476668323027550982124226673         44
19    -1.65681    -1.6563     -1.65629554275624960726800210379235578984224126        44
20    0.745011    0.743315    0.7433149249542194708863988360088077971952959          44
21    -1.44496    -1.44748    -1.4474829223403030761269776745381301819987566         44
22    0.087905    0.095207    0.0952068104668238661115383583599189149853326          42
23    -1.99227    -1.99094    -1.9909356632407342775333821354445070851649882         44
24    1.96915     1.96383     1.9638248151638224859534533253066504813887021          44
25    1.87755     1.85661     1.856607904653221551367598957266904811841229           43
26    1.52521     1.44699     1.446992911620825807091150862298880145718986           42
27    0.326266    0.093788    0.09378848628091500503892233990641233248724            41
28    -1.89355    -1.9912     -1.991203719841134617886520965281182647668228          43
29    1.58553     1.96489     1.96489225390917172033807637748582517248492            42
30    0.513916    1.8608      1.86080156947226494970453084715090036079062            41
31    -1.73589    1.46258     1.4625824809504444800108283562940121929374             41
32    1.01331     0.139148    0.1391475135831572902564402379886938275275             39
33    -0.973196   -1.98064    -1.9806379694636250574059219921222561750316            41
34    -1.05289    1.92293     1.9229267660809917453708956799535634030597             40
35    -0.891423   1.69765     1.697647347710701146004063463571177411445              40
36    -1.20537    0.882007    0.88200651718917823955241209923397008885               39
37    -0.547096   -1.22206    -1.22206450363581583064458232449182553013              39
38    -1.70069    -0.506559   -0.50655834895334707644333089345636482020              38
39    0.892332    -1.7434     -1.74339863910565905486360252582371345504              39
40    -1.20374    1.03944     1.0394388148354640259056257841907185515                38
41    -0.551001   -0.919571   -0.9195669502134459308479819793235229667               37
42    -1.6964     -1.15439    -1.1543966240751418527148614298414483394               37
43    0.877765    -0.667388   -0.667368434323915621804071163497016435                37
44    -1.22953    -1.55459    -1.554619372868045521352040215536158293                37
45    -0.488261   0.416762    0.416841394496635151296945728730469405                 36
46    -1.7616     -1.82631    -1.826243251834100586201313995483550391                37
47    1.10324     1.33541     1.33516441486959013410631061106873241                  36
48    -0.782867   -0.21669    -0.21733598526594499959534575720583669                 35
49    -1.38712    -1.95305    -1.95276506950848093804351511407442882                 36
50    -0.0759     1.81439     1.81329141669246238938601189782980277                  35
51    -1.99424    1.292       1.2880257618505572696325139303314855                   35
52    1.97699     -0.330742   -0.3409896368092915292915504401586577                  34
53    1.90849     -1.89061    -1.8837260675886674553630289756862626                  35
54    1.64233     1.57441     1.548423897713064950270322632156628                    34
55    0.697253    0.478751    0.397616567008920227731829970366544                    33
56    -1.51384    -1.7708     -1.841901065640040850344743570647498                   34
57    0.291706    1.13572     1.39259953560591807319662988996508                     33
58    -1.91491    -0.710134   -0.06066653343018132066941779190874                    31
59    1.66687     -1.49571    -1.996319571721564692242194398219879                   33
60    0.778462    0.237146    1.98529183243857147525202470339640                     33
61    -1.394      -1.94376    1.9413836599473009593244145091349                      32
62    -0.056772   1.77821     1.7689705151103774870722631230910                      32
63    -1.99678    1.16203     1.129256683329874265313437467792                       31
64    1.98712     -0.649693   -0.724779343154812073581354268671                      30
65    1.94864     -1.5779     -1.474694903736079165018510014079                      31
66    1.79719     0.489766    0.17472505910516379525639777401                        29
67    1.2299      -1.76013    -1.969471153720697018327264533785                      31
68    -0.487351   1.09806     1.87881662533793338481672381761                        30
69    -1.76249    -0.794275   1.52995191164622034818656554568                        29
70    1.10637     -1.36913    0.3407528519499240346878434207                         28
71    -0.775949   -0.125489   -1.8838874938879931519910332470                        29
72    -1.3979     -1.98425    1.5490320896275834355996430025                         28
73    -0.045865   1.93726     0.399500414695997681931284904                          27
74    -1.9979     1.75297     -1.840399418657725879366409949                         28
75    1.99159     1.0729      1.387070020195695375611561491                          27
76    1.96643     -0.848879   -0.07603675907431322283483110                          26
77    1.86685     -1.2794     -1.994218411269474845764066846                         28
78    1.48514     -0.363124   1.976907071846148318520791627                          27
79    0.205629    -1.86814    1.90816157071531222971299343                           27
80    -1.95772    1.48995     1.6410805799547275150903640                            26
81    1.83265     0.219951    0.6931454699045448084149562                            25
82    1.35862     -1.95162    -1.5195493575508077672611988                           25
83    -0.154147   1.80883     0.309030250033072626448110                             24
84    -1.97624    1.27185     -1.904500304564496615960074                            25
85    1.90552     -0.382388   1.627121410086260369724522                             25
86    1.631       -1.85378    0.64752408316110028883401                              24
87    0.66017     1.4365      -1.58071256172637647737749                             24
88    -1.56418    0.063529    0.49865220279956356513869                              23
89    0.446646    -1.99596    -1.75134598064314293056994                             24
90    -1.80051    1.98387     1.0672127439148919724518                               23
91    1.24183     1.93575     -0.8610569592256472072250                              22
92    -0.45787    1.74713     -1.2585809129690821228291                              22
93    -1.79036    1.05247     -0.415974085509911731155                               21
94    1.20537     -0.892301   -1.826965560184192643144                               22
95    -0.547081   -1.2038     1.337803158099140830894                                21
96    -1.7007     -0.550866   -0.21028271017996520268                                20
97    0.892389    -1.69655    -1.955781181799368758919                               22
98    -1.20364    0.878269    1.82508003108053551238                                 21
99    -0.551245   -1.22864    1.33091711984892847188                                 20
100   -1.69613    -0.490437   -0.2286596200930329662                                 19