Быстрое вычисление чисел Бернулли
Аннотация
Числа Бернулли часто встречаются в математическом анализе, теории чисел, комбинаторике и в других областях математики. В некоторых монографиях по теории чисел имеются отдельные главы, посвященные только числам Бернулли и их свойствам. Алгоритмы вычисления чисел Бернулли встроены во все популярные математические пакеты: Mathematica, Matlab, Magma, Pari GP и т.д.
В настоящей работе предлагается более быстрый, по сравнению с известными, алгоритм для вычисления чисел Бернулли. Суть нашего подхода заключается в усовершенствовании мультимодулярного метода Харвея за счет разрежения больших вычисляемых сумм, когда мы выражаем суммы по половине интервала через суммы в интервалах длины 1/12 или даже 1/15 длины интервала суммирования. В работе доказано, что такого сокращения интервалов суммирования удается достичь для подавляющего большинства простых чисел. При этом неудобные простые числа (а их не больше 0.01% при больших значениях n) можно просто исключить из списка тех, по модулю которых считается очередное число Бернулли.
Предлагаемый нами в статье алгоритм быстрого вычисления (ускорение более чем втрое, по сравнению с алгоритмом Харвея) чисел Бернулли по модулям простых чисел может быть успешно использовано и для нахождения иррегулярных простых чисел, иррегулярных пар (p, n), а также при вычислении инвариантов Ивасавы. При вычислении иррегулярных пар (p, n) и инвариантов Ивасавы приведенный в нашей работе алгоритм значительно (более чем в 10 раз) более эффективен.
Литература
[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.)
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.
