Data.Number.Flint.Bernoulli

This module provides helper functions for exact or approximate calculation of the Bernoulli numbers, which are defined by the exponential generating function

\[\frac{x}{e^x-1} = \sum_{n=0}^{\infty} B_n \frac{x^n}{n!}.\]

Efficient algorithms are implemented for both multi-evaluation and calculation of isolated Bernoulli numbers. A global (or thread-local) cache is also provided, to support fast repeated evaluation of various special functions that depend on the Bernoulli numbers (including the gamma function and the Riemann zeta function).

Support for Bernoulli numbers

Generation of Bernoulli numbers

data BernoulliRev

Constructors

BernoulliRev !(ForeignPtr CBernoulliRev)

Instances

Storable CBernoulliRev

Defined in Data.Number.Flint.Bernoulli.FFI

Methods

sizeOf :: CBernoulliRev -> Int

alignment :: CBernoulliRev -> Int

peekElemOff :: Ptr CBernoulliRev -> Int -> IO CBernoulliRev

pokeElemOff :: Ptr CBernoulliRev -> Int -> CBernoulliRev -> IO ()

peekByteOff :: Ptr b -> Int -> IO CBernoulliRev

pokeByteOff :: Ptr b -> Int -> CBernoulliRev -> IO ()

peek :: Ptr CBernoulliRev -> IO CBernoulliRev

poke :: Ptr CBernoulliRev -> CBernoulliRev -> IO ()

type CBernoulliRev = CFlint BernoulliRev

newBernoulliRev :: CULong -> IO BernoulliRev

withBernoulliRev :: BernoulliRev -> (Ptr CBernoulliRev -> IO a) -> IO (BernoulliRev, a)

withNewBernoulliRev :: CULong -> (Ptr CBernoulliRev -> IO a) -> IO (BernoulliRev, a)

bernoulli_rev_init :: Ptr CBernoulliRev -> CULong -> IO ()

bernoulli_rev_init iter n

Initializes the iterator iter. The first Bernoulli number to be generated by calling bernoulli_rev_next is \(B_n\). It is assumed that \(n\) is even.

bernoulli_rev_next :: Ptr CFmpz -> Ptr CFmpz -> Ptr CBernoulliRev -> IO ()

bernoulli_rev_next numer denom iter

Sets numer and denom to the exact, reduced numerator and denominator of the Bernoulli number \(B_k\) and advances the state of iter so that the next invocation generates \(B_{k-2}\).

bernoulli_rev_clear :: Ptr CBernoulliRev -> IO ()

bernoulli_rev_clear iter

Frees all memory allocated internally by iter.

bernoulli_fmpq_vec_no_cache :: Ptr CFmpq -> CULong -> CLong -> IO ()

bernoulli_fmpq_vec_no_cache res a num

Writes num consecutive Bernoulli numbers to res starting with \(B_a\). This function is not currently optimized for a small count num. The entries are not read from or written to the Bernoulli number cache; if retrieving a vector of Bernoulli numbers is needed more than once, use bernoulli_cache_compute followed by bernoulli_fmpq_ui instead.

This function is a wrapper for the rev iterators. It can use multiple threads internally.

Caching

bernoulli_cache_compute :: CLong -> IO ()

bernoulli_cache_compute n

Makes sure that the Bernoulli numbers up to at least \(B_{n-1}\) are cached. Calling flint_cleanup() frees the cache.

The cache is extended by calling bernoulli_fmpq_vec_no_cache internally.

Bounding

bernoulli_bound_2exp_si :: CULong -> IO CLong

bernoulli_bound_2exp_si n

Returns an integer \(b\) such that \(|B_n| \le 2^b\). Uses a lookup table for small \(n\), and for larger \(n\) uses the inequality \(|B_n| < 4 n! / (2 \pi)^n < 4 (n+1)^{n+1} e^{-n} / (2 \pi)^n\). Uses integer arithmetic throughout, with the bound for the logarithm being looked up from a table. If \(|B_n| = 0\), returns LONG_MIN. Otherwise, the returned exponent \(b\) is never more than one percent larger than the true magnitude.

This function is intended for use when \(n\) small enough that one might comfortably compute \(B_n\) exactly. It aborts if \(n\) is so large that internal overflow occurs.

Isolated Bernoulli numbers

bernoulli_mod_p_harvey :: CULong -> CULong -> IO CULong

bernoulli_mod_p_harvey n p

Returns the \(B_n\) modulo the prime number p, computed using Harvey's algorithm [Har2010]. The running time is linear in p. If p divides the numerator of \(B_n\), UWORD_MAX is returned as an error code.

_bernoulli_fmpq_ui_zeta :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

_bernoulli_fmpq_ui_zeta num den n

Sets num and den to the reduced numerator and denominator of the Bernoulli number \(B_n\).

The zeta version computes the denominator \(d\) using the von Staudt-Clausen theorem, numerically approximates \(B_n\) using arb_bernoulli_ui_zeta, and then rounds \(d B_n\) to the correct numerator.

The multi_mod version reconstructs \(B_n\) by computing the high bits via the Riemann zeta function and the low bits via Harvey's multimodular algorithm. The tuning parameter alpha should be a fraction between 0 and 1 controlling the number of bits to compute by the multimodular algorithm. If set to a negative number, a default value will be used.

_bernoulli_fmpq_ui_multi_mod :: Ptr CFmpz -> Ptr CFmpz -> CULong -> CDouble -> IO ()

_bernoulli_fmpq_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()

_bernoulli_fmpq_ui num den n

Computes the Bernoulli number \(B_n\) as an exact fraction, for an isolated integer \(n\). This function reads \(B_n\) from the global cache if the number is already cached, but does not automatically extend the cache by itself.

bernoulli_fmpq_ui :: Ptr CFmpq -> CULong -> IO ()