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
550
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
Team topologies and the microservice architecture: a synergistic relationship
cer
PRO
0
1.2k
『自分のデータだけ見せたい!』を叶える──Laravel × Casbin で複雑権限をスッキリ解きほぐす 25 分
akitotsukahara
1
600
#kanrk08 / 公開版 PicoRubyとマイコンでの自作トレーニング計測装置を用いたワークアウトの理想と現実
bash0c7
1
660
Systèmes distribués, pour le meilleur et pour le pire - BreizhCamp 2025 - Conférence
slecache
0
120
Webの外へ飛び出せ NativePHPが切り拓くPHPの未来
takuyakatsusa
2
460
Rubyでやりたい駆動開発 / Ruby driven development
chobishiba
1
530
スタートアップの急成長を支えるプラットフォームエンジニアリングと組織戦略
sutochin26
0
300
PostgreSQLのRow Level SecurityをPHPのORMで扱う Eloquent vs Doctrine #phpcon #track2
77web
2
420
Goで作る、開発・CI環境
sin392
0
190
なぜ適用するか、移行して理解するClean Architecture 〜構造を超えて設計を継承する〜 / Why Apply, Migrate and Understand Clean Architecture - Inherit Design Beyond Structure
seike460
PRO
1
720
明示と暗黙 ー PHPとGoの インターフェイスの違いを知る
shimabox
2
390
システム成長を止めない!本番無停止テーブル移行の全貌
sakawe_ee
1
150
Featured
See All Featured
Into the Great Unknown - MozCon
thekraken
39
1.9k
Making the Leap to Tech Lead
cromwellryan
134
9.4k
Build your cross-platform service in a week with App Engine
jlugia
231
18k
The Straight Up "How To Draw Better" Workshop
denniskardys
234
140k
Let's Do A Bunch of Simple Stuff to Make Websites Faster
chriscoyier
507
140k
JavaScript: Past, Present, and Future - NDC Porto 2020
reverentgeek
48
5.4k
個人開発の失敗を避けるイケてる考え方 / tips for indie hackers
panda_program
107
19k
Documentation Writing (for coders)
carmenintech
72
4.9k
The Pragmatic Product Professional
lauravandoore
35
6.7k
[RailsConf 2023 Opening Keynote] The Magic of Rails
eileencodes
29
9.5k
The Art of Programming - Codeland 2020
erikaheidi
54
13k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
46
9.6k
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”