×

zbMATH — the first resource for mathematics

On recurrences converging to the wrong limit in finite precision and some new examples. (English) Zbl 1448.65041
ETNA, Electron. Trans. Numer. Anal. 52, 358-369 (2020); addendum ibid. 52, 571-575 (2020).
Summary: In 1989, J. M. Muller [Arithmétique des Ordinateurs, Masson, Paris, 1989, https://hal-ens-lyon.archives-ouvertes.fr/ensl-00086707] gave a famous example of a recurrence where, for particular initial values, the iteration over real numbers converges to a repellent fixed point, whereas finite precision arithmetic produces a different result, the attracting fixed point. We analyze recurrences in that spirit and remove a gap in previous arguments in the literature, that is, the recursion must be well defined. The latter is known as the Skolem problem. We identify initial values producing a limit equal to the repellent fixed point, show that in every \(\varepsilon \)-neighborhood of such initial values the recurrence is not well defined, and characterize initial values for which the recurrence is well defined. We give some new examples in that spirit. For example, the correct real result, i.e., the repellent fixed point, may be correctly computed in bfloat, half, single, double, formerly extended precision (\(80\) bit format), binary128 as well as many formats of much higher precision. Rounding errors may be beneficial by introducing some regularizing effect.

MSC:
65G50 Roundoff error
11B37 Recurrences
65G30 Interval and finite arithmetic
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] M. ABADI, A.AGARWAL, P. BARHAM, E. BREVDO, Z. CHEN, C. CITRO, G. CORRADO, A. DAVIS, J. DEAN, M. DEVIN, S. GHEMAWAT, I. GOODFELLOW, A. HARP, G. IRVING, M. ISARD, Y. JIA, R. JÓZEFOWICZ, L. KAISER, M. KUDLUR, J. LEVENBERG, D. MANÉ, R. MONGA, S. MOORE, D. MURRAY, C. OLAH, M. SCHUSTER, J. SHLENS, R. STEINER, I. SUTSKEVER, K. TALWAR, P. TUCKER, V. VANHOUCKE, V. VASUDEVAN, F. VIÉGAS, O. VINYALS, P. WARDEN, M. WATTENBERG, M. WICKE, Y. YU,AND X. ZHENG,Tensorflow: large-scale machine learning on heterogeneous distributed systems, Preprint, CoRR, abs/1603.04467, 2016.https://arxiv.org/abs/1603.04467.
[2] V. D. BLONDEL,The presence of a zero in an integer recurrent sequence is NP-hard to decide, Linear Algebra Appl, 351/352 (2002), pp. 91-98. · Zbl 1007.93047
[3] J. DEAN, G. CORRADO, R. MONGA, K. CHEN, D. MATTHIEU, M. MAO, M. RANZATO, A. SENIOR, P. TUCKER, K. YANG, Q. LE,ANDA. NG,Large scale distributed deep networks, in Advances in Neural Information Processing Systems 25 (NIPS 2012), F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, eds., NIPS Proceedings, Curran Associates, Red Hook, 2012, pp. 1223-1231.
[4] N. J. HIGHAM,A multiprecision world, SIAM News, October 2017.
[5] P. HOLOBORODKO,Multiprecision Computing Toolbox for MATLAB 4.6.4.13348, Advanpix LLC., Yokohama, Japan, 2019.
[6] K. MAHLER,Eine arithmetische Eigenschaft der Taylorkoeffizienten rationaler Funktionen, Akad. Wetensch. Amsterdam, 38 (1935), pp. 50-60. · Zbl 0010.39006
[7] L. FOUSSE, G. HANROT, V. LEFÈVRE, P. PÉLISSIER,ANDP. ZIMMERMANN,MPFR: A multiple-precision binary floating-point library with correct rounding, ACM Trans. Math. Software, 33 (2007), Art. 13, 15 pages. · Zbl 1365.65302
[8] IEEE,IEEE Standard for Floating-Point Arithmetic 754-2008, The Institute of Electrical and Electronics Engineers, New York, August 2008.
[9] W. KAHAN,How futile are mindless assessments of roundoff in floating-point computations, Preprint, University of California, Berkeley, 2006. https://people.eecs.berkeley.edu/ wkahan/Mindless.pdf
[10] M. KASHIWAGI, Private communication, 2019. ETNA
[11] J.-M. MULLER,Arithmétique des Ordinateurs, Masson, Paris, 1989. https://hal-ens-lyon.archives-ouvertes.fr/ensl-00086707.
[12] J.M. MULLER, N. BRUNIE, F.DEDINECHIN, C.-P. JEANNEROD, M. JOLDES, V. LEFEVRE, G. MELQUIOND, R. REVOL,ANDS. TORRES,Handbook of Floating-Point Arithmetic, 2nd ed., Birkhäuser, Cham, 2018. · Zbl 1394.65001
[13] S. PRANESH,Low precision floating-point formats: the wild west of computer arithmetic, SIAM News, November 2019.
[14] T. SKOLEM,Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen, Oslo Vid. Akad. Skrifter I, 6 (1933), pp. 76-89. · Zbl 0008.10503
[15] G.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.