log.h

Contains useful functions for performing arithmetic in log space, such as computing the maximum of an array, computing sum-exp, log-sum-exp, and normalization. This file also contains log_cache, which caches the logarithms of positive integers. All functions in this file avoid loss of precision by performing operations in log space when feasible.

In the following example, the array `{ -100.0, -100.0, -100.0 + log(2.0), -100.0 + log(4.0) }`

of log probabilities is normalized and printed. The expected output is `[0.125000, 0.125000, 0.250000, 0.500000]`

.

#include <math/log.h> #include <core/io.h> using namespace core; int main() { double a[] = { -100.0, -100.0, -100.0 + log(2.0), -100.0 + log(4.0) }; normalize_exp(a, 4); print(a, 4, stdout); }

Classes, functions, and variables in this file | |
---|---|

#define | LOG_ZERO |

float | log_probability (float src) |

double | log_probability (double src) |

void | max (V & max, const T * src, unsigned int length, unsigned int skip) |

void | max (V & max, const T * src, const P * prior, unsigned int length, unsigned int skip) |

V | max (const T * src, unsigned int length, unsigned int skip) |

V | max (const T * src, const P * prior, unsigned int length, unsigned int skip) |

V | max (const Collection & src) |

V | max (const T * src, unsigned int length) |

V | sumexp (const T * src, unsigned int length, unsigned int skip, const V & shift) |

V | sumexp (const T * src, const P * prior, unsigned int length, unsigned int skip, const V & shift) |

V | sumexp (const Collection & src, const V & shift) |

void | normalize (const T * src, V * dst, unsigned int length, unsigned int skip, const V & normalization) |

void | normalize_exp (const T * src, V * dst, unsigned int length, unsigned int skip, const V & normalization) |

void | normalize_exp (const T * src, const P * prior, V * dst, unsigned int length, unsigned int skip, const V & normalization) |

V | logsumexp (const T * src, unsigned int length, unsigned int skip = 1) |

V | logsumexp (const T * src, const P * prior, unsigned int length, unsigned int skip = 1) |

V | logsumexp (const Collection & src) |

void | normalize (const T * src, V * dst, unsigned int length, unsigned int skip = 1) |

void | normalize_exp (const T * src, V * dst, unsigned int length, unsigned int skip = 1) |

void | normalize_exp (const T * src, const P * prior, V * dst, unsigned int length, unsigned int skip = 1) |

void | normalize_exp (T * x, unsigned int length) |

V | logsumexp (const V & first, const V & second) |

V | logdiffexp (const V & first, const V & second) |

struct | log_cache |

#define LOG_ZERO -1.0e16

This value is used for `log(0)`

in some operations to avoid floating-point infinities and improve performance.

float log_probability(

float | src | ) |

Returns `src`

. This function is defined so that the function in this file `max`

, `sum_exp`

, and `normalize`

behave correctly when `T`

is `float`

.

double log_probability(

double | src | ) |

Returns `src`

. This function is defined so that the function in this file `max`

, `sum_exp`

, and `normalize`

behave correctly when `T`

is `double`

.

template<typename T, typename V>

void max(V & | max, | |

const T * | src, | |

unsigned int | length, | |

unsigned int | skip | ) |

Computes the maximum log probability of the elements in *even* index. The computed maximum is stored in

`src`

with the given `length`

, only inspecting the elements at every `skip`

locations, until `length`

elements have been considered. For example, if `skip = 2`

, this function will find the maximum of the elements at every `max`

.T | the type of every element in |

V | the type of the log probabilities. |

template<typename T, typename P, typename V>

void max(V & | max, | |

const T * | src, | |

const P * | prior, | |

unsigned int | length, | |

unsigned int | skip | ) |

Computes the maximum sum of the log probability of the elements in `src`

and the elements in `prior`

with the given `length`

, only inspecting the elements in `src`

at every `skip`

locations, until `length`

elements have been considered. For example, if `skip = 2`

, this function will find the maximum of the elements at every *even* index. Note that `skip`

does not affect the inspection of elements in `prior`

. The computed maximum is stored in `max`

.

So more precisely, this function computes:

\[ max_i \{ f(\text{src}[i \cdot \text{skip}]) + g(\text{prior}[i]) \}. \]

where $ f(\cdot) $ is the function `V log_probability(const T&)`

and $ g(\cdot) $ is the function `V log_probability(const P&)`

.T | the type of every element in |

P | the type of every element in |

V | the type of the log probabilities. |

template<typename T, typename V = typename >

V max(const T * | src, | |

unsigned int | length, | |

unsigned int | skip | ) |

Returns the maximum log probability of the elements in *even* index.

`src`

with the given `length`

, only inspecting the elements at every `skip`

locations, until `length`

elements have been considered. For example, if `skip = 2`

, this function will find the maximum of the elements at every T | the type of every element in |

V | the type of the log probabilities. By default, if |

template<typename T, typename P, typename V = typename >

V max(const T * | src, | |

const P * | prior, | |

unsigned int | length, | |

unsigned int | skip | ) |

Returns the maximum sum of the log probability of the elements in `src`

and the elements in `prior`

with the given `length`

, only inspecting the elements in `src`

at every `skip`

locations, until `length`

elements have been considered. For example, if `skip = 2`

, this function will find the maximum of the elements at every *even* index. Note that `skip`

does not affect the inspection of elements in `prior`

. The computed maximum is stored in `max`

.

So more precisely, this function computes:

\[ max_i \{ f(\text{src}[i \cdot \text{skip}]) + g(\text{prior}[i]) \}. \]

where $ f(\cdot) $ is the function `V log_probability(const T&)`

and $ g(\cdot) $ is the function `V log_probability(const P&)`

.T | the type of every element in |

P | the type of every element in |

V | the type of the log probabilities. By default, if |

Returns the maximum log probability of the elements in the collection

`src`

.Collection | the type of a collection of items, each of type |

V | the type of the log probabilities. |

Returns the maximum log probability of the given native array

`src`

.T | the type of every element in |

template<typename T, typename V>

V sumexp(const T * | src, | |

unsigned int | length, | |

unsigned int | skip, | |

const V & | shift | ) |

This function returns

\[ \sum_{i=0}^{\text{length}-1} \exp\{ f(\text{src}[i * \text{skip}]) - \text{shift} \} \]

where $ f(\cdot) $ is the function `V log_probability(const T&)`

.T | the type of every element in |

V | the type of the log probabilities. |

template<typename T, typename P, typename V>

V sumexp(const T * | src, | |

const P * | prior, | |

unsigned int | length, | |

unsigned int | skip, | |

const V & | shift | ) |

This function returns

\[ \sum_{i=0}^{\text{length}-1} \exp\{ f(\text{src}[i * \text{skip}]) + g(\text{prior}[i]) - \text{shift} \} \]

where $ f(\cdot) $ is the function `V log_probability(const T&)`

and $ g(\cdot) $ is the function `V log_probability(const P&)`

.T | the type of every element in |

P | the type of every element in |

V | the type of the log probabilities. |

template<typename Collection, typename V>

V sumexp(const Collection & | src, | |

const V & | shift | ) |

This function returns

\[ \sum_{c\in\text{src}} \exp\{ f(c) - \text{shift} \} \]

where $ f(\cdot) $ is the function `V log_probability(const T&)`

.Collection | the type of a collection of items, each of type |

V | the type of the log probabilities. |

template<typename T, typename V>

void normalize(const T * | src, | |

V * | dst, | |

unsigned int | length, | |

unsigned int | skip, | |

const V & | normalization | ) |

Copies the log probabilities from

`src`

into `dst`

, subtracting `normalization`

from each element. This function assumes `dst`

is initialized and has sufficient capacity. This function only considers elements at every `skip`

positions, until `length`

elements have been considered. For example, if `skip = 2`

, only the elements at even indices are copied. Note that `src`

and `dst`

can be the same.T | the type of every element in |

V | the type of the log probabilities. |

template<typename T, typename V>

void normalize_exp(const T * | src, | |

V * | dst, | |

unsigned int | length, | |

unsigned int | skip, | |

const V & | normalization | ) |

Copies the log probabilities from

`src`

into `dst`

, subtracting `normalization`

from each element, and taking the natural exponent of the result. This function assumes `dst`

is initialized and has sufficient capacity. This function only considers elements at every `skip`

positions, until `length`

elements have been considered. For example, if `skip = 2`

, only the elements at even indices are copied. Note that `src`

and `dst`

can be the same.T | the type of every element in |

V | the type of the log probabilities. |

template<typename T, typename P, typename V>

void normalize_exp(const T * | src, | |

const P * | prior, | |

V * | dst, | |

unsigned int | length, | |

unsigned int | skip, | |

const V & | normalization | ) |

This function computes

\[ \exp\{ f(\text{src}[i * \text{skip}]) + g(\text{prior}[i]) - \text{normalization} \} \]

and stores the result in `dst[i]`

, where `i`

ranges from `0`

to `length - 1`

, and $ f(\cdot) $ is the function `V log_probability(const T&)`

and $ g(\cdot) $ is the function `V log_probability(const P&)`

. Note that `src`

and `dst`

can be the same.T | the type of every element in |

P | the type of every element in |

V | the type of the log probabilities. |

template<typename T, typename V = typename >

V logsumexp(const T * | src, | |

unsigned int | length, | |

unsigned int | skip = 1 | ) |

Returns the natural logarithm of the sum of the natural exponent of the elements in

`src`

, skipping every `skip`

elements, until `length`

elements have been considered.T | the type of every element in |

V | the type of the log probabilities. |

template<typename T, typename P, typename V = typename >

V logsumexp(const T * | src, | |

const P * | prior, | |

unsigned int | length, | |

unsigned int | skip = 1 | ) |

Returns the natural logarithm of the sum of the natural exponent of the elements in

`src`

, with the given `prior`

, skipping every `skip`

elements, until `length`

elements have been considered. Note that `skip`

does not affect the inspection of the elements in `prior`

.T | the type of every element in |

P | the type of every element in |

V | the type of the log probabilities. |

template<typename Collection, typename V = typename >

V logsumexp(const Collection & | src | ) |

Returns the natural logarithm of the sum of the natural exponent of the elements in the collection

`src`

.Collection | the type of a collection of items, each of type |

V | the type of the log probabilities. |

template<typename T, typename V>

void normalize(const T * | src, | |

V * | dst, | |

unsigned int | length, | |

unsigned int | skip = 1 | ) |

Computes the *normalized log probabilities* of the elements in

`src`

and stores them in `dst`

, skipping every `skip`

elements, until `length`

elements have been considered. Note that `src`

and `dst`

can be the same.T | the type of every element in |

V | the type of the log probabilities. |

template<typename T, typename V>

void normalize_exp(const T * | src, | |

V * | dst, | |

unsigned int | length, | |

unsigned int | skip = 1 | ) |

Computes the *normalized probabilities* of the elements in

`src`

and stores them in `dst`

, skipping every `skip`

elements, until `length`

elements have been considered. Note that `src`

and `dst`

can be the same.T | the type of every element in |

V | the type of the log probabilities. |

template<typename T, typename P, typename V>

void normalize_exp(const T * | src, | |

const P * | prior, | |

V * | dst, | |

unsigned int | length, | |

unsigned int | skip = 1 | ) |

Computes the *normalized probabilities* of the elements in

`src`

and stores them in `dst`

, skipping every `skip`

elements, until `length`

elements have been considered. Note that `skip`

does not affect the inspection of the elements in `prior`

. Also note that `src`

and `dst`

can be the same.T | the type of every element in |

P | the type of every element in |

V | the type of the log probabilities. |

Normalizes the elements in `src`

. Like all functions in this file, loss of precision is avoided by performing operations in log space when feasible.

Returns the natural logarithm of the sum of the natural exponents of

`first`

and `second`

.V | satisfies is_arithmetic. |

Returns the natural logarithm of

`exp(first) - exp(second)`

.V | satisfies is_arithmetic. |

template<typename V>

This structure caches natural logarithms of positive integers.

The following example displays a typical use-case of this cache. The expected output is `log(2) = 0.693147, log(183) = 5.209486, sum from i=1 to 999 of log(i) = 5905.220423`

.

#include <math/log.h> using namespace core; int main() { log_cache<double> cache(1000); printf("log(2) = %lf, ", cache.get(2)); printf("log(183) = %lf, ", cache.get(183)); double sum = 0.0; for (unsigned int i = 1; i < 1000; i++) sum += cache.get(i); printf("sum from i=1 to 999 of log(i) = %lf\n", sum); }

V | satisfies is_arithmetic. |

Public members | |
---|---|

log_cache (unsigned int initial_size) | |

bool | ensure_size (unsigned int requested_size) |

V | get (unsigned int x) const |

static log_cache< V > & | instance () |

log_cache::log_cache(

unsigned int | initial_size | ) |

Constructs the cache with the given `initial_size`

. The natural logarithms up to and includig `log(initial_size - 1)`

are precomputed and stored.

bool log_cache::ensure_size(

unsigned int | requested_size | ) |

Checks that the natural logarithms up to and including `log(requested_size - 1)`

are computed and stored.

V log_cache::get(

unsigned int | x | ) const |

Returns the natural logarithm of `x`

. This function assumes that `log(x)`

has already been computed, either by the constructor or by ensure_size, and no bounds checking is performed.