RATIONAL ARITHMETIC WITH A ROUND-OFF

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

Computer calculations in floating-point arithmetic are always approximate. In contrast, calculations in rational arithmetic (for example, in computer algebra) are always absolutely precise and reproducible both on other computers and (theoretically) manually. Therefore, such calculations can be demonstrative in the sense that the proof obtained with their help is no different from the traditional one. However, such calculations are usually impossible in a sufficiently complex problem due to limited memory and time resources. We propose a mechanism for rounding off rational numbers in calculations in rational arithmetic, which solves this problem (of resources), i.e. the calculations can still be demonstrative, but no longer require unlimited resources. A number of examples of the implementation of standard numerical algorithms in this arithmetic are given. The results have applications to analytical number theory.

About the authors

V. P Varin

Keldysh Institute of Applied Mathematics RAS

Email: varin@keldysh.ru
Moscow, 125047 Russia

References

  1. Borwein J., Bailey D., Gigensohn R. Experimentation in Mathematics: computational paths to discovery. A K Peters, Natick. 2004.
  2. Арнольд В. И. Экспериментальная математика. М.: ФАЗИС, 2005.
  3. Hammer R., et.al. Numerical Toolbox for Verified Computing I. Springer, 1993.
  4. Appel K., Haken W. Solution of the Four Color Map Problem // Scientific American. 1977. V. 237. N 4. P. 108–121.
  5. Рухович Ф. Д. Внешние биллиарды вне правильных многоугольников: ручной случай // Изв. РАН. Сер. матем. 2022. Т. 86. No 3. С. 105–160.
  6. Варин В. П. Преобразование последовательностей в доказательствах иррациональности некоторых фундаментальных констант // Ж. вычисл. матем. и матем. физ. 2022. Т. 62. N 10. С. 1587–1614.
  7. Варин В. П. Аппроксимация дифференциальных операторов с учетом граничных усло- вий // Ж. вычисл. матем. и матем. физ. 2023. Т. 63. N 8. С. 1251–1271.
  8. Хинчин А. Я. Цепные дроби. М.: Гостехиздат, 1961.
  9. Воробьев Н. Н. Числа Фибоначчи. М.: Наука, 1984.
  10. Hairer, et. al. Solving Ordinary Differential Equations I. Nonstiff Problems. 2nd ed. Berlin, Springer. 1993.
  11. Weniger E. J. Nonlinear sequence transformations for the acceleration of convergence and the summation of divergent series // Comput. Phys. Rep. North-Holland. Amsterdam, 1989. V. 10. P. 189–371.
  12. Brent R. P. Computation of the Regular Continued Fraction for Euler’s Constant // Math. of Comput. 1977. V. 31. No 139. P. 771–777.
  13. Serret M. J.-A. Oeuvres de Lagrange. Vol. 2. Gauthier-Villars. Paris. (M DCCC LXVIII).
  14. Брюно А. Д. Разложение алгебраических чисел в цепные дроби // Ж. вычисл. матем. и ма- тем. физ. 1964. Т. 4. No 2. С. 211–221.
  15. Knuth D. E. The Art of Computer Programming. 3rd ed. Vol. 2. 1998. Addison Wesley Longman.
  16. Haas A. The relative growth rate for partial quotients // New York J. Math. 2008. V. 14. P. 139–143.
  17. Roth K. F. Rational approximations to algebraic numbers // Mathematika. 1955. V. 2. Part 1. No 3. P. 1–20.
  18. Stark H. M. An explanation of some exotic continued fractions found by Brillhart // in: A.O.L. Atkin, B.J. Birch (ed.), Computers in Number Theory. Science Research Council Atlas Symposium N 2. Oxford, Academic Press, 1971.
  19. Lévy P. Sur le lois de probabilité dont dépendent les qoutients complets et incomplets d’une fraction continue // Bull. Scc. Math. 1929. V. 57. P. 178–194.
  20. Borwein J., et. al. Neverending Fractions. An Introduction to Continued Fractions. Australian Mathematical Society Lecture Series: 23. 2014.
  21. Brun V. Ein Satz über Irrationalität // Arkiv for Mathematik og Naturvidenskab (Kristiania), 1910. V. 31. No 3. P. 3–6.
  22. Butler L. A. A useful application of Brun’s irrationality criterion // Expo. Math. 2015. V. 33. P. 121–134.

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Russian Academy of Sciences