Cython wrapper for bernmm library

AUTHOR:

• David Harvey (2008-06): initial version

sage.rings.bernmm.bernmm_bern_modp(p, k)

Compute $B_k\mathrm{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

Sage Live

from sage.rings.bernmm import bernmm_bern_modp
bernoulli(0) % 5, bernmm_bern_modp(5, 0)
bernoulli(1) % 5, bernmm_bern_modp(5, 1)
bernoulli(2) % 5, bernmm_bern_modp(5, 2)
bernoulli(3) % 5, bernmm_bern_modp(5, 3)
bernoulli(4), bernmm_bern_modp(5, 4)
bernoulli(18) % 5, bernmm_bern_modp(5, 18)
bernoulli(19) % 5, bernmm_bern_modp(5, 19)
p = 10000019; k = 1000
bernoulli(k) % p
bernmm_bern_modp(p, k)

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)

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

INPUT:

• k – non-negative integer

• num_threads – integer $\ge 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

Sage Live

from sage.rings.bernmm import bernmm_bern_rat
bernmm_bern_rat(0)
bernmm_bern_rat(1)
bernmm_bern_rat(2)
bernmm_bern_rat(3)
bernmm_bern_rat(100)
bernmm_bern_rat(100, 3)

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

Make live