119 lines
3.1 KiB
Markdown
119 lines
3.1 KiB
Markdown
[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)
|