SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
sdsl::binomial_coefficients< n > Struct Template Reference

A struct for the binomial coefficients $ n \choose k $. More...

#include <rrr_helper.hpp>

Classes

struct  impl
 

Public Types

enum  { MAX_LOG = (n > 128 ? 8 : (n > 64 ? 7 : 6)) }
 
typedef binomial_coefficients_trait< MAX_LOGtrait
 
typedef trait::number_type number_type
 
typedef binomial_table< MAX_SIZE, number_typetBinom
 

Static Public Attributes

static const uint16_t MAX_SIZE = (1 << MAX_LOG)
 
static struct sdsl::binomial_coefficients::impl data
 

Detailed Description

template<uint16_t n>
struct sdsl::binomial_coefficients< n >

A struct for the binomial coefficients $ n \choose k $.

data.table[m][k] contains the number ${m \choose k}$ for $ k\leq m\leq \leq n$. Size of data.table : Let $ maxlog = \lceil \log n \rceil $ and $ maxsize = 2^{maxlog} $ then the tables requires $ maxsize^2\times \lceil n/8 rceil $ bytes space. Examples: n <= 64: 64*64*8 bytes = 4 kB * 8 = 32 kB 64 < n <= 128: 128*128*16 bytes = 16 kB * 16 = 256 kB 128 < n <= 256: 256*256*32 bytes = 64 kB * 32 = 2048 kB = 2 MB The table is shared now for all n's in on of these ranges.

data.space[k] returns the bits needed to encode a value between [0..data.table[n][k]], given n and k. Size of data.space is $ (n+1) \times \lceil n/8 \rceil $ bytes. E.g. 64*8=512 bytes for n=63, 2kB for n=127, and 8kB for n=255.

BINARY_SEARCH_THRESHOLD is equal to $ n/\lceil\log{n+1}\rceil $

Precondition
The template parameter n should be in the range [7..256].

Definition at line 262 of file rrr_helper.hpp.

Member Typedef Documentation

◆ number_type

template<uint16_t n>
typedef trait::number_type sdsl::binomial_coefficients< n >::number_type

Definition at line 270 of file rrr_helper.hpp.

◆ tBinom

template<uint16_t n>
typedef binomial_table<MAX_SIZE, number_type> sdsl::binomial_coefficients< n >::tBinom

Definition at line 271 of file rrr_helper.hpp.

◆ trait

template<uint16_t n>
typedef binomial_coefficients_trait<MAX_LOG> sdsl::binomial_coefficients< n >::trait

Definition at line 269 of file rrr_helper.hpp.

Member Enumeration Documentation

◆ anonymous enum

template<uint16_t n>
anonymous enum
Enumerator
MAX_LOG 

Definition at line 264 of file rrr_helper.hpp.

Member Data Documentation

◆ data

template<uint16_t n>
binomial_coefficients< n >::impl sdsl::binomial_coefficients< n >::data
static

Definition at line 298 of file rrr_helper.hpp.

◆ MAX_SIZE

template<uint16_t n>
const uint16_t sdsl::binomial_coefficients< n >::MAX_SIZE = (1 << MAX_LOG)
static

Definition at line 268 of file rrr_helper.hpp.


The documentation for this struct was generated from the following file: