Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Oh, you're so random
Search
Vicent Martí
March 25, 2012
Programming
14
2.5k
Oh, you're so random
Randomness and pink ponies in Codemotion Rome 2012
Vicent Martí
March 25, 2012
Tweet
Share
More Decks by Vicent Martí
See All by Vicent Martí
Unicorns Die With Bullets Made of Glitter
tanoku
6
540
Threedee Tales From Urban Bohemia
tanoku
3
810
My Mom told me that Git doesn't scale
tanoku
28
1.9k
Intergalactic Javascript Robots from Outer Space
tanoku
271
27k
Ruby is Unlike a Banana
tanoku
97
11k
A talk about libgit2
tanoku
11
1.6k
Other Decks in Programming
See All in Programming
生成AIコーディングとの向き合い方、AIと共創するという考え方 / How to deal with generative AI coding and the concept of co-creating with AI
seike460
PRO
1
330
iOSアプリ開発で 関数型プログラミングを実現する The Composable Architectureの紹介
yimajo
2
210
XP, Testing and ninja testing
m_seki
3
180
Enterprise Web App. Development (2): Version Control Tool Training Ver. 5.1
knakagawa
1
120
Julia という言語について (FP in Julia « SIDE: F ») for 関数型まつり2025
antimon2
3
980
AIエージェントはこう育てる - GitHub Copilot Agentとチームの共進化サイクル
koboriakira
0
370
[初登壇@jAZUG]アプリ開発者が気になるGoogleCloud/Azure+wasm/wasi
asaringo
0
130
技術同人誌をMCP Serverにしてみた
74th
0
320
deno-redisの紹介とJSRパッケージの運用について (toranoana.deno #21)
uki00a
0
140
イベントストーミング図からコードへの変換手順 / Procedure for Converting Event Storming Diagrams to Code
nrslib
1
350
Benchmark
sysong
0
260
都市をデータで見るってこういうこと PLATEAU属性情報入門
nokonoko1203
1
570
Featured
See All Featured
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
15
1.5k
What's in a price? How to price your products and services
michaelherold
246
12k
[RailsConf 2023] Rails as a piece of cake
palkan
55
5.6k
Art, The Web, and Tiny UX
lynnandtonic
299
21k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
Imperfection Machines: The Place of Print at Facebook
scottboms
267
13k
Performance Is Good for Brains [We Love Speed 2024]
tammyeverts
10
930
Building Better People: How to give real-time feedback that sticks.
wjessup
367
19k
Facilitating Awesome Meetings
lara
54
6.4k
Making the Leap to Tech Lead
cromwellryan
134
9.3k
Building an army of robots
kneath
306
45k
GraphQLとの向き合い方2022年版
quramy
47
14k
Transcript
None
select a random element
select a random element ‘tis one is ok.
None
None
Information Theory
hard TOPIC Information Theory
hard TOPIC dumb SPEAKER + Information Theory
0≤H(X)≤1 where X is a discrete random variable
0≤H(X)≤1 where X is a discrete random variable unpredictable
0≤H(X)≤1 where X is a discrete random variable unpredictable always
the same
None
ask a question.
None
bool is_random(char *bytes, size_t n) { }
bool is_random(char *bytes, size_t n) { } AGHHH
UNIFORM distribution
UNIFORM distribution
select a random element array[rand() % array.size]
select a random element array[rand() % array.size] UNIFORM distribution
select a random element array[rand() % array.size] UNIFORM distribution
select a random element array[rand() % array.size] UNIFORM distribution AGHHH
This is how you kill the RANDOM pnrg array
This is how you kill the RANDOM a pnrg array
This is how you kill the RANDOM a pnrg array
This is how you kill the RANDOM a a pnrg
array
This is how you kill the RANDOM a a pnrg
array
This is how you kill the RANDOM a a a
pnrg array
This is how you kill the RANDOM a a a
pnrg array
This is how you kill the RANDOM a a a
pnrg array
This is how you kill the RANDOM a a a
b pnrg array
This is how you kill the RANDOM a a a
b pnrg array
This is how you kill the RANDOM a a a
b b pnrg array
This is how you kill the RANDOM a a a
b b pnrg array
This is how you kill the RANDOM a a a
b b pnrg array
This is how you kill the RANDOM a a a
b b pnrg array
how to FIX:
how to FIX: 1. Random is hard
how to FIX: 1. Random is hard 2. Run away
how to FIX: 1. Random is hard 2. Run away
Math.random() // between 0.0 and 1.0 Javascript
how to FIX: 1. Random is hard 2. Run away
how to FIX: 1. Random is hard 2. Run away
prng.rand(5..9) #=> one of [5, 6, 7, 8, 9] prng.rand(5...9) #=> one of [5, 6, 7, 8] Ruby
Good.
Good. (but I don’t care)
None
“PRNGs and Hash functions are in the same family of
algorithms”
None
hash tables out of nowhere!
hash tables out of nowhere! O(1)
hash tables out of nowhere! O(1) uniform
pathological average data set: O(1)
pathological average data set: O(1)
pathological average data set: O(1) O(n)
ONE fix
ONE fix INT_MAX % size == 0
collide make them
collide make them • Brute force
collide make them • Brute force • MITM
collide make them • Brute force • MITM • Equivalent
substrings
collide make them • Brute force • MITM • Equivalent
substrings
collide make them • Brute force • MITM • Equivalent
substrings
collide make them • Brute force • MITM • Equivalent
substrings
collide make them • Brute force • MITM • Equivalent
substrings
collide make them • Brute force • MITM • Equivalent
substrings
problem & that’s a
problem & that’s a painful comparisons
problem & that’s a painful comparisons ~700ms responses
MANY fixes
MANY fixes (but only one is right)
MANY fixes (but only one is right) 1. Limiting request
size
this is bad and you should feel bad! MANY fixes
(but only one is right) 1. Limiting request size
MANY fixes (but only one is right) 2. Changing the
hash table
MANY fixes (but only one is right) 2. Changing the
hash table (no comment)
MANY fixes (but only one is right) 3. Bring back
the random
None
“Randomness is too important to be left to chance”
Thanks. “Randomness is too important to be left to chance”