Cython wrapper for bernmm library#

AUTHOR:

David Harvey (2008-06): initial version

sage.rings.bernmm.bernmm_bern_modp(p, k)[source]#

Compute \(B_k \mod p\), where \(B_k\) is the \(k\)-th Bernoulli number.

If \(B_k\) is not \(p\)-integral, return \(-1\).

INPUT:

p – a prime
k – non-negative integer

COMPLEXITY:

Pretty much linear in \(p\).

EXAMPLES:

Sage

sage: from sage.rings.bernmm import bernmm_bern_modp

sage: bernoulli(0) % 5, bernmm_bern_modp(5, 0)
(1, 1)
sage: bernoulli(1) % 5, bernmm_bern_modp(5, 1)
(2, 2)
sage: bernoulli(2) % 5, bernmm_bern_modp(5, 2)
(1, 1)
sage: bernoulli(3) % 5, bernmm_bern_modp(5, 3)
(0, 0)
sage: bernoulli(4), bernmm_bern_modp(5, 4)
(-1/30, -1)
sage: bernoulli(18) % 5, bernmm_bern_modp(5, 18)
(4, 4)
sage: bernoulli(19) % 5, bernmm_bern_modp(5, 19)
(0, 0)

sage: p = 10000019; k = 1000
sage: bernoulli(k) % p
1972762
sage: bernmm_bern_modp(p, k)
1972762

Python

>>> from sage.all import *
>>> from sage.rings.bernmm import bernmm_bern_modp

>>> bernoulli(Integer(0)) % Integer(5), bernmm_bern_modp(Integer(5), Integer(0))
(1, 1)
>>> bernoulli(Integer(1)) % Integer(5), bernmm_bern_modp(Integer(5), Integer(1))
(2, 2)
>>> bernoulli(Integer(2)) % Integer(5), bernmm_bern_modp(Integer(5), Integer(2))
(1, 1)
>>> bernoulli(Integer(3)) % Integer(5), bernmm_bern_modp(Integer(5), Integer(3))
(0, 0)
>>> bernoulli(Integer(4)), bernmm_bern_modp(Integer(5), Integer(4))
(-1/30, -1)
>>> bernoulli(Integer(18)) % Integer(5), bernmm_bern_modp(Integer(5), Integer(18))
(4, 4)
>>> bernoulli(Integer(19)) % Integer(5), bernmm_bern_modp(Integer(5), Integer(19))
(0, 0)

>>> p = Integer(10000019); k = Integer(1000)
>>> bernoulli(k) % p
1972762
>>> bernmm_bern_modp(p, k)
1972762

sage.rings.bernmm.bernmm_bern_rat(k, num_threads=1)[source]#

Compute \(k\)-th Bernoulli number using a multimodular algorithm. (Wrapper for bernmm library.)

INPUT:

k – non-negative integer
num_threads – integer \(\geq 1\), number of threads to use

COMPLEXITY:

Pretty much quadratic in \(k\). See the paper “A multimodular algorithm for computing Bernoulli numbers”, David Harvey, 2008, for more details.

EXAMPLES:

Sage

sage: from sage.rings.bernmm import bernmm_bern_rat

sage: bernmm_bern_rat(0)
1
sage: bernmm_bern_rat(1)
-1/2
sage: bernmm_bern_rat(2)
1/6
sage: bernmm_bern_rat(3)
0
sage: bernmm_bern_rat(100)
-94598037819122125295227433069493721872702841533066936133385696204311395415197247711/33330
sage: bernmm_bern_rat(100, 3)
-94598037819122125295227433069493721872702841533066936133385696204311395415197247711/33330

Python

>>> from sage.all import *
>>> from sage.rings.bernmm import bernmm_bern_rat

>>> bernmm_bern_rat(Integer(0))
1
>>> bernmm_bern_rat(Integer(1))
-1/2
>>> bernmm_bern_rat(Integer(2))
1/6
>>> bernmm_bern_rat(Integer(3))
0
>>> bernmm_bern_rat(Integer(100))
-94598037819122125295227433069493721872702841533066936133385696204311395415197247711/33330
>>> bernmm_bern_rat(Integer(100), Integer(3))
-94598037819122125295227433069493721872702841533066936133385696204311395415197247711/33330