Быстрое вычисление чисел Бернулли

  • Rustem Rimovich Aidagulov Московский государственный университет имени М.В. Ломоносова; Институт машиноведения РАН имени А.А. Благонравова http://orcid.org/0000-0002-6579-429X
  • Sergei Timofeevich Glavatsky Московский государственный университет имени М.В. Ломоносова http://orcid.org/0000-0003-1857-6158

Аннотация

Числа Бернулли часто встречаются в математическом анализе, теории чисел, комбинаторике и в других областях математики. В некоторых монографиях по теории чисел имеются отдельные главы, посвященные только числам Бернулли и их свойствам. Алгоритмы вычисления чисел Бернулли встроены во все популярные математические пакеты: Mathematica, Matlab, Magma, Pari GP и т.д.
В настоящей работе предлагается более быстрый, по сравнению с известными, алгоритм для вычисления чисел Бернулли. Суть нашего подхода заключается в усовершенствовании мультимодулярного метода Харвея за счет разрежения больших вычисляемых сумм, когда мы выражаем суммы по половине интервала через суммы в интервалах длины 1/12 или даже 1/15 длины интервала суммирования. В работе доказано, что такого сокращения интервалов суммирования удается достичь для подавляющего большинства простых чисел. При этом неудобные простые числа (а их не больше 0.01% при больших значениях n) можно просто исключить из списка тех, по модулю которых считается очередное число Бернулли.
Предлагаемый нами в статье алгоритм быстрого вычисления (ускорение более чем втрое, по сравнению с алгоритмом Харвея) чисел Бернулли по модулям простых чисел может быть успешно использовано и для нахождения иррегулярных простых чисел, иррегулярных пар (p, n), а также при вычислении инвариантов Ивасавы. При вычислении иррегулярных пар (p, n) и инвариантов Ивасавы приведенный в нашей работе алгоритм значительно (более чем в 10 раз) более эффективен.

Сведения об авторах

Rustem Rimovich Aidagulov, Московский государственный университет имени М.В. Ломоносова; Институт машиноведения РАН имени А.А. Благонравова

старший научный сотрудник кафедры теоретической информатики, отделение математики, механико-математический факультет, кандидат физико-математических наук

Sergei Timofeevich Glavatsky, Московский государственный университет имени М.В. Ломоносова

доцент кафедры теоретической информатики, отделение математики, механико-математический факультет, кандидат физико-математических наук, доцент

Литература

[1] Borevich Z.I., Shafarevich I.R. Number Theory, (Pure and Applied Mathematics, Volume 20). Academic Press, 1986. 435 p. (In Eng.)
[2] Ireland K., Rosen M.A Classical Introduction to Modern Number Theory. Second Edition. In: Axler S., Ribet K. (eds). Graduate Texts in Mathematics. Springer-Verlag, New York. 1990; 84. (In Eng.) DOI: 10.1007/978-1-4757-2103-4
[3] Chowla S., Hartung P. An “exact” formula for the m-th Bernoulli number. Acta Arithmetica. 1972; 22:113-115. (In Eng.) DOI: 10.4064/aa-22-1-113-115
[4] Fillebrown S. Faster computation of Bernoulli numbers. Journal of Algorithms. 1992; 13(3):431-445. (In Eng.) DOI: 10.1016/0196-6774(92)90048-H
[5] Fee G., Plouffe S. An efficient algorithm for the computation of Bernoulli numbers. 2007. arXiv:math/0702300. Available at: https://arxiv.org/pdf/math/0702300.pdf (accessed 6.05.2019). (In Eng.)
[6] Wolfram Research, Inc., Mathematica, Version 6.0, Champaign, IL, 2007. (In Eng.)
[7] Stein W. Modular Forms, a Computational Approach. Graduate Studies in Mathematics. Vol. 79. American Mathematical Society, Providence, Rhode Island. 2007; p. 268. (In Eng.) DOI: 10.1090/gsm/079
[8] Harvey D. A Multimodular algorithm for computing Bernoulli numbers. 2008. arXiv:0807.1347. Available at: https://arxiv.org/abs/0807.1347 (accessed 6.05.2019). (In Eng.)
[9] Postnikov M.M. Fermat's Theorem: An Introduction to the Theory of Algebraic Numbers. Moscow: Nauka, 1978. (In Russ.)
[10] Whittaker E. T., Watson G. N. A course of modern analysis. Fourth Edition. Camb. Univ. Press, 1928. (In Eng.)
[11] Ônishi Y. Generalized Bernoulli-Hurwitz numbers and the universal Bernoulli numbers. Russian Mathematical Surveys. 2011; 66(5):871-932. (In Eng.) DOI: 10.1070/RM2011v066n05ABEH004763
[12] Johnson W. Irregular prime divisors of the Bernoulli numbers. Mathematics of Computation. 1974; 28:653-657. (In Eng.) DOI: 10.2307/2005943
[13] Kellner B. C. On irregular prime powers of Bernoulli numbers. 2004. arXiv:math/0409223. Available at: https://arxiv.org/abs/math/0409223v2 (accessed 6.05.2019). (In Eng.)
[14] Koblitz N. p-adic Numbers, p-adic Analysis and Zeta-Functions. In: Axler S., Ribet K. (eds). Graduate Texts in Mathematics. Springer-Verlag, New York. 1984; 58. (In Eng.) DOI: 10.1007/978-1-4612-1112-9
[15] Thangadurai R. Adams theorem on Bernoulli numbers revisited. Journal of Number Theory. 2004; 106:169-177. (In Eng.) DOI: 10.1016/j.jnt.2003.12.006
[16] Buhler J., Crandall R., Ernvall R., Mets¨ankyl¨a T., Shokrollahi M. A. Irregular Primes and Cyclotomic Invariants to 12 Million. Journal of Symbolic Computation. 2001; 31:89-96. (In Eng.) DOI: 10.1006/jsco.1999.1011
[17] Wagstaff, Samuel S., Jr. Prime divisors of the Bernoulli and Euler numbers. Number theory for the millennium, III (Urbana, IL, 2000). A K Peters, Natick, MA, 2002. Pp. 357-374. MR1956285 (In Eng.)
[18] Greenberg R. Iwasawa Theory — Past and Present. Advanced Studies in Pure Mathematics. 2001; 30:335-385. Available at: https://projecteuclid.org/download/pdf_1/euclid.aspm/1536853285 (accessed 6.05.2019). (In Eng.)
Опубликована
2019-07-25
Как цитировать
AIDAGULOV, Rustem Rimovich; GLAVATSKY, Sergei Timofeevich. Быстрое вычисление чисел Бернулли. Современные информационные технологии и ИТ-образование, [S.l.], v. 15, n. 2, p. 283-289, july 2019. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/514>. Дата доступа: 29 mar. 2024 doi: https://doi.org/10.25559/SITITO.15.201902.283-289.
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук