Safe Haskell | Safe-Inferred |
---|---|

Language | Haskell2010 |

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).

## Synopsis

- data BernoulliRev = BernoulliRev !(ForeignPtr CBernoulliRev)
- 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_next :: Ptr CFmpz -> Ptr CFmpz -> Ptr CBernoulliRev -> IO ()
- bernoulli_rev_clear :: Ptr CBernoulliRev -> IO ()
- bernoulli_fmpq_vec_no_cache :: Ptr CFmpq -> CULong -> CLong -> IO ()
- bernoulli_cache_compute :: CLong -> IO ()
- bernoulli_bound_2exp_si :: CULong -> IO CLong
- bernoulli_mod_p_harvey :: CULong -> CULong -> IO CULong
- _bernoulli_fmpq_ui_zeta :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()
- _bernoulli_fmpq_ui_multi_mod :: Ptr CFmpz -> Ptr CFmpz -> CULong -> CDouble -> IO ()
- _bernoulli_fmpq_ui :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO ()
- bernoulli_fmpq_ui :: Ptr CFmpq -> CULong -> IO ()

# Support for Bernoulli numbers

# Generation of Bernoulli numbers

data BernoulliRev Source #

#### Instances

Storable CBernoulliRev Source # | |

Defined in Data.Number.Flint.Bernoulli.FFI 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 Source #

newBernoulliRev :: CULong -> IO BernoulliRev Source #

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

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

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

*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 () Source #

*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 () Source #

*bernoulli_rev_clear* *iter*

Frees all memory allocated internally by *iter*.

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

*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 () Source #

*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 Source #

*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 Source #

*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 () Source #

*_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 :: Ptr CFmpz -> Ptr CFmpz -> CULong -> IO () Source #

*_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.