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
520
Threedee Tales From Urban Bohemia
tanoku
2
760
My Mom told me that Git doesn't scale
tanoku
28
1.8k
Intergalactic Javascript Robots from Outer Space
tanoku
270
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
マルチアカウント環境での、そこまでがんばらない RI/SP 運用設計
wa6sn
0
240
AI時代のプログラミング教育 / programming education in ai era
kishida
22
20k
ニックトレイン登壇資料
ryotakurokawa
0
130
AWS CDKにおけるL2 Constructの仕組み / aws-cdk-l2-construct
gotok365
4
920
Going Structural with Named Tuples
bishabosha
0
150
AI Agentを利用したAndroid開発について
yuchan2215
0
200
PHPでお金を扱う時、終わりのない 謎の1円調査の旅にでなくて済む方法
nakka
3
960
SLI/SLOの設定を進めるその前に アラート品質の改善に取り組んだ話
tanden
2
660
小さく段階的リリースすることで深夜メンテを回避する
mkmk884
2
120
Scala 3 で GLSL のための c-like-for を実装してみた
exoego
1
170
なぜselectはselectではないのか
taiyow
2
280
CTFのWebにおける⾼難易度問題について
hamayanhamayan
1
930
Featured
See All Featured
Practical Tips for Bootstrapping Information Extraction Pipelines
honnibal
PRO
14
1.1k
Site-Speed That Sticks
csswizardry
4
450
Writing Fast Ruby
sferik
628
61k
The Art of Programming - Codeland 2020
erikaheidi
53
13k
How to train your dragon (web standard)
notwaldorf
91
5.9k
The Cult of Friendly URLs
andyhume
78
6.3k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
251
21k
Optimizing for Happiness
mojombo
377
70k
jQuery: Nuts, Bolts and Bling
dougneiner
63
7.7k
Into the Great Unknown - MozCon
thekraken
35
1.7k
Designing Experiences People Love
moore
140
23k
Building Applications with DynamoDB
mza
94
6.3k
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”