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
5
460
Threedee Tales From Urban Bohemia
tanoku
2
660
My Mom told me that Git doesn't scale
tanoku
28
1.7k
Intergalactic Javascript Robots from Outer Space
tanoku
268
27k
Ruby is Unlike a Banana
tanoku
96
11k
A talk about libgit2
tanoku
11
1.6k
Other Decks in Programming
See All in Programming
GrafanaのHTTP API を眺めてみよう
rinchoku
0
440
rtcamp 10 (vk-illuminati)
yumcyawiz
1
210
App Store Connect APIで 作業時間を増やそう
mot_techtalk
3
130
20241004 モノタロウ式~ドメインモデリングとリアーキテクチャ
monotaro
PRO
2
650
Serverless renderování Webových komponent
rarous
PRO
0
130
Vue3の一歩踏み込んだパフォーマンスチューニング2024
hal_spidernight
3
900
MLOps in Mercari Group’s Trust and Safety ML Team
cjhj
1
130
perl for shell, awk and sed programmers
mackee
2
920
Cloud Adoption Framework にみる組織とクラウド導入戦略
tomokusaba
2
670
ポケモンで考えるコミュニケーション / Communication Lessons from Pokémon
mackey0225
5
220
本編では話さない Zig の話
andpad
2
120
tsconfig.jsonの最近の新機能 ファイルパス編
uhyo
7
1.9k
Featured
See All Featured
Reflections from 52 weeks, 52 projects
jeffersonlam
346
20k
Design and Strategy: How to Deal with People Who Don’t "Get" Design
morganepeng
126
18k
What’s in a name? Adding method to the madness
productmarketing
PRO
22
3.1k
XXLCSS - How to scale CSS and keep your sanity
sugarenia
246
1.3M
Building a Modern Day E-commerce SEO Strategy
aleyda
38
6.9k
Building an army of robots
kneath
302
42k
Easily Structure & Communicate Ideas using Wireframe
afnizarnur
191
16k
Code Review Best Practice
trishagee
63
17k
Fantastic passwords and where to find them - at NoRuKo
philnash
50
2.8k
Side Projects
sachag
452
42k
Faster Mobile Websites
deanohume
304
30k
Being A Developer After 40
akosma
85
590k
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”