[rand.util.canonical]

# 29 Numerics library [[numerics]](./#numerics)

## 29.5 Random number generation [[rand]](rand#util.canonical)

### 29.5.8 Utilities [[rand.util]](rand.util#canonical)

#### 29.5.8.2 Function template generate_canonical [rand.util.canonical]

[ð](#lib:generate_canonical)

`template<class RealType, size_t digits, class URBG>
  RealType generate_canonical(URBG& g);
`

[1](#1)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L4404)

Let

- [(1.1)](#1.1)

r be numeric_limits<RealType>​::​radix,

- [(1.2)](#1.2)

R be g.max()âg.min()+1,

- [(1.3)](#1.3)

d be the smaller of digits and numeric_limits<RealType>​::​digits,[245](#footnote-245 "d is introduced to avoid any attempt to produce more bits of randomness than can be held in RealType.")

- [(1.4)](#1.4)

k be the smallest integer such that Rkâ¥rd, and

- [(1.5)](#1.5)

x be âRk/rdâ[.](#1.sentence-1)

An [*attempt*](#def:attempt "29.5.8.2 Function template generate_­canonical [rand.util.canonical]") is k invocations of g() to obtain values g0,â¦,gkâ1, respectively,
and the calculation of a quantity S given by Formula [29.1](#eq:rand.gencanonical):

S=kâ1âi=0(giâg.min())âRi(29.1)

[2](#2)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L4426)

*Effects*: Attempts are made until S<xrd[.](#2.sentence-1)

[*Note [1](#note-1)*:

When R is a power of r, precisely one attempt is made[.](#2.sentence-2)

â *end note*]

[3](#3)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L4433)

*Returns*: âS/xâ/rd[.](#3.sentence-1)

[*Note [2](#note-2)*:

The return value c satisfies0â¤c<1[.](#3.sentence-2)

â *end note*]

[4](#4)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L4441)

*Throws*: What and when g throws[.](#4.sentence-1)

[5](#5)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L4445)

*Complexity*: Exactly k invocations of g per attempt[.](#5.sentence-1)

[6](#6)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L4449)

[*Note [3](#note-3)*:

If the values gi produced by g are uniformly distributed,
the instantiation's results are distributed as uniformly as possible[.](#6.sentence-1)

Obtaining a value in this way
can be a useful step
in the process of transforming
a value generated by a uniform random bit generator
into a value
that can be delivered by a random number distribution[.](#6.sentence-2)

â *end note*]

[7](#7)

[#](http://github.com/Eelis/draft/tree/9adde4bc1c62ec234483e63ea3b70a59724c745a/source/numerics.tex#L4461)

[*Note [4](#note-4)*:

When R is a power of r,
an implementation can avoid using an arithmetic type that is wider
than the output when computing S[.](#7.sentence-1)

â *end note*]

[245)](#footnote-245)[245)](#footnoteref-245)

d is introduced to avoid any attempt
 to produce more bits of randomness
 than can be held in RealType[.](#footnote-245.sentence-1)
