-
Notifications
You must be signed in to change notification settings - Fork 3
/
Copy pathhow-random-numbers-work-in-swift.html
323 lines (282 loc) · 15.8 KB
/
how-random-numbers-work-in-swift.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
<!DOCTYPE html>
<html lang="en">
<head>
<script src="https://use.fontawesome.com/afd448ce82.js"></script>
<!-- Meta Tag -->
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<!-- SEO -->
<meta name="author" content="Bruno Rocha">
<meta name="keywords" content="Software, Engineering, Blog, Posts, iOS, Xcode, Swift, Articles, Tutorials, OBJ-C, Objective-C, Apple">
<meta name="description" content="Let's see how to use the new APIs, but most importantly, how they are implemented inside the Swift compiler.">
<meta name="title" content="How Random Numbers Work In Swift">
<meta name="url" content="https://swiftrocks.com/how-random-numbers-work-in-swift">
<meta name="image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4">
<meta name="copyright" content="Bruno Rocha">
<meta name="robots" content="index,follow">
<meta property="og:title" content="How Random Numbers Work In Swift"/>
<meta property="og:image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4"/>
<meta property="og:description" content="Let's see how to use the new APIs, but most importantly, how they are implemented inside the Swift compiler."/>
<meta property="og:type" content="website"/>
<meta property="og:url" content="https://swiftrocks.com/how-random-numbers-work-in-swift"/>
<meta name="twitter:card" content="summary_large_image"/>
<meta name="twitter:image" content="https://swiftrocks.com/images/thumbs/thumb.jpg?4"/>
<meta name="twitter:image:alt" content="Page Thumbnail"/>
<meta name="twitter:title" content="How Random Numbers Work In Swift"/>
<meta name="twitter:description" content="Let's see how to use the new APIs, but most importantly, how they are implemented inside the Swift compiler."/>
<meta name="twitter:site" content="@rockbruno_"/>
<!-- Favicon -->
<link rel="icon" type="image/png" href="images/favicon/iconsmall2.png" sizes="32x32" />
<link rel="apple-touch-icon" href="images/favicon/iconsmall2.png">
<link rel="preconnect" href="https://fonts.googleapis.com">
<link rel="preconnect" href="https://fonts.gstatic.com" crossorigin>
<link href="https://fonts.googleapis.com/css2?family=Source+Sans+3:ital,wght@0,200..900;1,200..900&display=swap" rel="stylesheet">
<!-- Bootstrap CSS Plugins -->
<link rel="stylesheet" type="text/css" href="css/bootstrap.css">
<!-- Prism CSS Stylesheet -->
<link rel="stylesheet" type="text/css" href="css/prism4.css">
<!-- Main CSS Stylesheet -->
<link rel="stylesheet" type="text/css" href="css/style48.css">
<link rel="stylesheet" type="text/css" href="css/sponsor4.css">
<!-- HTML5 shiv and Respond.js support IE8 or Older for HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/html5shiv/3.7.3/html5shiv.min.js"></script>
<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
<![endif]-->
<script type="application/ld+json">
{
"@context": "https://schema.org",
"@type": "BlogPosting",
"mainEntityOfPage": {
"@type": "WebPage",
"@id": "https://swiftrocks.com/how-random-numbers-work-in-swift"
},
"image": [
"https://swiftrocks.com/images/thumbs/thumb.jpg"
],
"datePublished": "2020-05-12T14:00:00+02:00",
"dateModified": "2020-05-12T14:00:00+02:00",
"author": {
"@type": "Person",
"name": "Bruno Rocha"
},
"publisher": {
"@type": "Organization",
"name": "SwiftRocks",
"logo": {
"@type": "ImageObject",
"url": "https://swiftrocks.com/images/thumbs/thumb.jpg"
}
},
"headline": "How Random Numbers Work In Swift",
"abstract": "Let's see how to use the new APIs, but most importantly, how they are implemented inside the Swift compiler."
}
</script>
</head>
<body>
<div id="main">
<!-- Blog Header -->
<!-- Blog Post (Right Sidebar) Start -->
<div class="container">
<div class="col-xs-12">
<div class="page-body">
<div class="row">
<div><a href="https://swiftrocks.com">
<img id="logo" class="logo" alt="SwiftRocks" src="images/bg/logo2light.png">
</a>
<div class="menu-large">
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-large">
<div class="menu-item">
<a href="blog">blog</a>
</div>
<div class="menu-item">
<a href="about">about</a>
</div>
<div class="menu-item">
<a href="talks">talks</a>
</div>
<div class="menu-item">
<a href="projects">projects</a>
</div>
<div class="menu-item">
<a href="software-engineering-book-recommendations">book recs</a>
</div>
<div class="menu-item">
<a href="games">game recs</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
</div>
<div class="menu-small">
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-small-1">
<div class="menu-item">
<a href="blog">blog</a>
</div>
<div class="menu-item">
<a href="about">about</a>
</div>
<div class="menu-item">
<a href="talks">talks</a>
</div>
<div class="menu-item">
<a href="projects">projects</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
<div class="menu-arrow-right"></div>
<div class="menu-header menu-header-small-2">
<div class="menu-item">
<a href="software-engineering-book-recommendations">book recs</a>
</div>
<div class="menu-item">
<a href="games">game recs</a>
</div>
<div class="menu-arrow-right-2"></div>
</div>
</div>
</div>
<div class="content-page" id="WRITEIT_DYNAMIC_CONTENT">
<!--WRITEIT_POST_NAME=How Random Numbers Work In Swift-->
<!--WRITEIT_POST_HTML_NAME=how-random-numbers-work-in-swift-->
<!--Add here the additional properties that you want each page to possess.-->
<!--These properties can be used to change content in the template page or in the page itself as shown here.-->
<!--Properties must start with 'WRITEIT_POST'.-->
<!--Writeit provides and injects WRITEIT_POST_NAME and WRITEIT_POST_HTML_NAME by default.-->
<!--WRITEIT_POST_SHORT_DESCRIPTION=Let's see how to use the new APIs, but most importantly, how they are implemented inside the Swift compiler.-->
<!--WRITEIT_POST_SITEMAP_DATE_LAST_MOD=2020-05-12T14:00:00+02:00-->
<!--WRITEIT_POST_SITEMAP_DATE=2020-05-12T14:00:00+02:00-->
<title>How Random Numbers Work In Swift</title>
<div class="blog-post">
<div class="post-title-index">
<h1>How Random Numbers Work In Swift</h1>
</div>
<div class="post-info">
<div class="post-info-text">
Published on 12 May 2020
</div>
</div>
<p>Before Swift 4.2, generating random numbers involved using raw C APIs. With the addition of the <b>RandomNumberGenerator</b> protocol in Swift 4.2, developers were graced with an easy way to generate random numbers. Let's see how to use the new APIs, but most importantly, <b>how they are implemented inside the Swift compiler</b>.</p>
<h2>RandomNumberGenerator</h2>
<div class="sponsor-article-ad-auto hidden"></div>
<p>Deep down, the generation of random numbers in Swift still works exactly like before. The difference is that Swift 4.2 introduced some nice abstractions on top of it in the form of protocols -- allowing you to create your own randomization algorithms if you need to.</p>
<p>The generation of random numbers in Swift begins with <b>RandomNumberGenerator</b> -- a protocol that does nothing but generate random <b>UInt64</b> values:</p>
<pre><code>public protocol RandomNumberGenerator {
mutating func next() -> UInt64
}</code></pre>
<p>Types that can access/generate random values are meant to receive an implementation of this protocol, generate a (possibly very big) random number and use it to determine which value to return (for example, by calculating <b>randomNumber % range.upperBound</b>).</p>
<p>The Swift Standard Library provides an all-purpose implementation of <b>RandomNumberGenerator</b> called <b>SystemRandomNumberGenerator</b>, which pulls a random number from the innards of the compiler.</p>
<pre><code>public struct SystemRandomNumberGenerator: RandomNumberGenerator {
public mutating func next() -> UInt64 {
var random: UInt64 = 0
swift_stdlib_random(&random, MemoryLayout<UInt64>.size)
return random
}
}</code></pre>
<p>The actual random mechanism used differs by platform, but is guaranteed to be type-safe in all of them. For Apple platforms, the compiler uses <b>arc4random_buf</b> (whose functionality requires a separate article):</p>
<pre><code>#if defined(__APPLE__)
SWIFT_RUNTIME_STDLIB_API
void swift::swift_stdlib_random(void *buf, __swift_size_t nbytes) {
arc4random_buf(buf, nbytes);
}</code></pre>
<h2>Swift Random APIs</h2>
<p>From Swift 4.2, numeric types like <b>Int</b>, <b>Float</b> and <b>Bool</b> can generate random numbers through the new <b>.random(in:)</b> APIs:</p>
<pre><code>let randomInt = Int.random(in: 1..<5)
let randomFloat = Float.random(in: 1..<10)
let randomBool = Bool.random()</code></pre>
<p>All of these APIs support taking a <b>RandomNumberGenerator</b> argument, but you're allowed to not provide one, as the compiler is rigged to use <b>SystemRandomNumberGenerator</b> by default. For example, here's how the default API for <b>Bool</b> is defined:</p>
<pre><code>public static func random() -> Bool {
var g = SystemRandomNumberGenerator()
return Bool.random(using: &g)
}</code></pre>
<h3>Bool.random()</h3>
<p>In the case of <b>Bool</b>, the full implementation of the API will get the raw <b>UInt64</b> value from the generator, bit shift it to the right 17 times, and return true if the first bit of the resulting value is <b>0</b>.</p>
<pre><code>public static func random<T: RandomNumberGenerator>(
using generator: inout T
) -> Bool {
return (generator.next() >> 17) & 1 == 0
}</code></pre>
<p>The reason the value is shifted exactly <b>17</b> times is that (some) weak RNGs have better randomness properties in the middle bits over the low/high bits, and the Swift team felt like protecting us from APIs that decided to use these RNGs instead of the default <b>SystemRandomNumberGenerator</b>. Before the PR that implemented this improvement, <b>Bool.random()</b> used to simply return <b>generator.next() % 2 == 0</b>.</p>
<h3>Int.random() and others</h3>
<p>The implementation of the random API for other numeric types is similar to <b>Bool</b>, with the difference being how the value is pre/post-processed. For example, for <b>..<</b> <b>Int</b> ranges, Swift calculates the distances between the bounds, generates a value, makes sure it's less than <b>upperBound</b> and adds <b>lowerBound</b> to it, resulting in a random value inside the requested range.</p>
<pre><code>// Note: The actual implementation is slightly different than this
// because it treats compiler edge cases and uses some different types.
let delta = range.upperBound &- range.lowerBound
return range.lowerBound + generator.next(upperBound: delta)</code></pre>
<p>An interesting note is that <b>generator.next(upperBound: delta)</b> isn't simply a <b>value % delta</b> calculation -- it uses <b>Daniel Lemire’s “Fast Random Integer Generation in Interval” algorithm</b>, which produces a higher quality result (for example, it avoids module bias).</p>
<pre><code>public mutating func next<T: FixedWidthInteger & UnsignedInteger>(
upperBound: T
) -> T {
var random: T = next()
var m = random.multipliedFullWidth(by: upperBound)
if m.low < upperBound {
let t = (0 &- upperBound) % upperBound
while m.low < t {
random = next()
m = random.multipliedFullWidth(by: upperBound)
}
}
return m.high
}</code></pre>
<p>A funny aspect of this algorithm is that it can, in theory, take <b>forever</b> to run as it has a <b>while</b> loop that continuously discards what it considers to be "low quality" values, but in reality, the odds of it being anything slower than "pretty much instant" are so low that you should never consider this.</p>
<h2>randomElement()</h2>
<p>To top it off, let's take a look at another API added in Swift 4.2: The <b>randomElement()</b> method for <b>Collections</b>, which returns a random element from the collection:</p>
<pre><code>let string = ["Swift", "Rocks", "by", "Bruno", "Rocha"].randomElement()
// Bruno</code></pre>
<div class="sponsor-article-ad-auto hidden"></div>
<p><b>randomElement()</b> is defined as a <b>Collection</b> extension, and simply grabs a random index through the <b>Int.random(in:)</b> method that we spelunked previously.</p>
<pre><code>public func randomElement<T: RandomNumberGenerator>(
using generator: inout T
) -> Element? {
guard !isEmpty else { return nil }
let random = Int.random(in: 0 ..< count, using: &generator)
let idx = index(startIndex, offsetBy: random)
return self[idx]
}</code></pre>
<p>Perhaps an interesting take here is that this is a global <b>Collection</b> extension, which means that this will work for <b>any</b> type of collection (usually, you would see something like this only for <b>RandomAccessCollections</b>). This also means that the runtime complexity of this method will vary depending on the collection, as <b>count</b> is only O(1) in <b>RandomAccessCollections</b>. In other types of collections, <b>count</b> is O(n).</p>
<h2>References and Good Reads</h2>
<a href="https://github.com/apple/swift/blob/master/stdlib/public/core/Random.swift">Random.swift</a>
<br>
<a href="https://github.com/apple/swift-evolution/blob/master/proposals/0202-random-unification.md">Random Unification</a>
<br>
</div></div>
<div class="blog-post footer-main">
<div class="footer-logos">
<a href="https://swiftrocks.com/rss.xml"><i class="fa fa-rss"></i></a>
<a href="https://twitter.com/rockbruno_"><i class="fa fa-twitter"></i></a>
<a href="https://github.com/rockbruno"><i class="fa fa-github"></i></a>
</div>
<div class="footer-text">
© 2025 Bruno Rocha
</div>
<div class="footer-text">
<p><a href="https://swiftrocks.com">Home</a> / <a href="blog">See all posts</a></p>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
<!-- Blog Post (Right Sidebar) End -->
</div>
</div>
</div>
<!-- All Javascript Plugins -->
<script type="text/javascript" src="js/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/bootstrap@5.0.2/dist/js/bootstrap.bundle.min.js" integrity="sha384-MrcW6ZMFYlzcLA8Nl+NtUVF0sA7MsXsP1UyJoMp4YLEuNSfAP+JcXn/tWtIaxVXM" crossorigin="anonymous"></script>
<script type="text/javascript" src="js/prism4.js"></script>
<!-- Main Javascript File -->
<script type="text/javascript" src="js/scripts30.js"></script>
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-H8KZTWSQ1R"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-H8KZTWSQ1R');
</script>
</body>
</html>