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.6k
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
560
Threedee Tales From Urban Bohemia
tanoku
3
840
My Mom told me that Git doesn't scale
tanoku
28
1.9k
Intergalactic Javascript Robots from Outer Space
tanoku
273
27k
Ruby is Unlike a Banana
tanoku
97
11k
A talk about libgit2
tanoku
11
1.7k
Other Decks in Programming
See All in Programming
高度なUI/UXこそHotwireで作ろう Kaigi on Rails 2025
naofumi
4
4.1k
Leading Effective Engineering Teams in the AI Era
addyosmani
5
420
Claude CodeによるAI駆動開発の実践 〜そこから見えてきたこれからのプログラミング〜
iriikeita
0
230
Web フロントエンドエンジニアに開かれる AI Agent プロダクト開発 - Vercel AI SDK を観察して AI Agent と仲良くなろう! #FEC余熱NIGHT
izumin5210
3
530
monorepo の Go テストをはやくした〜い!~最小の依存解決への道のり~ / faster-testing-of-monorepos
convto
2
490
品質ワークショップをやってみた
nealle
0
250
理論と実務のギャップを超える
eycjur
0
140
What's new in Spring Modulith?
olivergierke
1
150
PHPに関数型の魂を宿す〜PHP 8.5 で実現する堅牢なコードとは〜 #phpcon_hiroshima / phpcon-hiroshima-2025
shogogg
1
220
CSC509 Lecture 06
javiergs
PRO
0
260
コードとあなたと私の距離 / The Distance Between Code, You, and I
hiro_y
0
170
Devoxx BE - Local Development in the AI Era
kdubois
0
130
Featured
See All Featured
Creating an realtime collaboration tool: Agile Flush - .NET Oxford
marcduiker
33
2.3k
Improving Core Web Vitals using Speculation Rules API
sergeychernyshev
20
1.2k
A Tale of Four Properties
chriscoyier
161
23k
Keith and Marios Guide to Fast Websites
keithpitt
411
23k
The World Runs on Bad Software
bkeepers
PRO
72
11k
Navigating Team Friction
lara
190
15k
The Pragmatic Product Professional
lauravandoore
36
6.9k
Site-Speed That Sticks
csswizardry
12
900
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
26
3.1k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
248
1.3M
Building Better People: How to give real-time feedback that sticks.
wjessup
369
20k
Building a Modern Day E-commerce SEO Strategy
aleyda
44
7.8k
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”