Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Oh, you're so random

Oh, you're so random

Randomness and pink ponies in Codemotion Rome 2012

Vicent Martí

March 25, 2012
Tweet

More Decks by Vicent Martí

Other Decks in Programming

Transcript

  1. View Slide

  2. select a random element

    View Slide

  3. select a random element
    ‘tis one is ok.

    View Slide

  4. View Slide

  5. View Slide

  6. Information
    Theory

    View Slide

  7. hard TOPIC
    Information
    Theory

    View Slide

  8. hard TOPIC
    dumb SPEAKER
    +
    Information
    Theory

    View Slide

  9. 0≤H(X)≤1
    where X is a discrete
    random variable

    View Slide

  10. 0≤H(X)≤1
    where X is a discrete
    random variable
    unpredictable

    View Slide

  11. 0≤H(X)≤1
    where X is a discrete
    random variable
    unpredictable
    always
    the same

    View Slide

  12. View Slide

  13. ask a
    question.

    View Slide

  14. View Slide

  15. bool is_random(char *bytes, size_t n)
    {
    }

    View Slide

  16. bool is_random(char *bytes, size_t n)
    {
    }
    AGHHH

    View Slide

  17. UNIFORM
    distribution

    View Slide

  18. UNIFORM
    distribution

    View Slide

  19. select a random element
    array[rand() % array.size]

    View Slide

  20. select a random element
    array[rand() % array.size]
    UNIFORM
    distribution

    View Slide

  21. select a random element
    array[rand() % array.size]
    UNIFORM
    distribution

    View Slide

  22. select a random element
    array[rand() % array.size]
    UNIFORM
    distribution
    AGHHH

    View Slide

  23. This is how you kill
    the RANDOM
    pnrg
    array

    View Slide

  24. This is how you kill
    the RANDOM
    a
    pnrg
    array

    View Slide

  25. This is how you kill
    the RANDOM
    a
    pnrg
    array

    View Slide

  26. This is how you kill
    the RANDOM
    a a
    pnrg
    array

    View Slide

  27. This is how you kill
    the RANDOM
    a a
    pnrg
    array

    View Slide

  28. This is how you kill
    the RANDOM
    a a a
    pnrg
    array

    View Slide

  29. This is how you kill
    the RANDOM
    a a a
    pnrg
    array

    View Slide

  30. This is how you kill
    the RANDOM
    a a a
    pnrg
    array

    View Slide

  31. This is how you kill
    the RANDOM
    a a a
    b
    pnrg
    array

    View Slide

  32. This is how you kill
    the RANDOM
    a a a
    b
    pnrg
    array

    View Slide

  33. This is how you kill
    the RANDOM
    a a a
    b b
    pnrg
    array

    View Slide

  34. This is how you kill
    the RANDOM
    a a a
    b b
    pnrg
    array

    View Slide

  35. This is how you kill
    the RANDOM
    a a a
    b b
    pnrg
    array

    View Slide

  36. This is how you kill
    the RANDOM
    a a a
    b b
    pnrg
    array

    View Slide

  37. how to FIX:

    View Slide

  38. how to FIX:
    1. Random is hard

    View Slide

  39. how to FIX:
    1. Random is hard
    2. Run away

    View Slide

  40. how to FIX:
    1. Random is hard
    2. Run away
    Math.random() // between 0.0 and 1.0
    Javascript

    View Slide

  41. how to FIX:
    1. Random is hard
    2. Run away

    View Slide

  42. 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

    View Slide

  43. Good.

    View Slide

  44. Good.
    (but I don’t care)

    View Slide

  45. View Slide

  46. “PRNGs
    and Hash
    functions
    are in the same
    family of algorithms”

    View Slide

  47. View Slide

  48. hash tables
    out of nowhere!

    View Slide

  49. hash tables
    out of nowhere!
    O(1)

    View Slide

  50. hash tables
    out of nowhere!
    O(1) uniform

    View Slide

  51. pathological
    average data set:
    O(1)

    View Slide

  52. pathological
    average data set:
    O(1)

    View Slide

  53. pathological
    average data set:
    O(1) O(n)

    View Slide

  54. ONE fix

    View Slide

  55. ONE fix
    INT_MAX % size == 0

    View Slide

  56. collide
    make them

    View Slide

  57. collide
    make them
    • Brute force

    View Slide

  58. collide
    make them
    • Brute force
    • MITM

    View Slide

  59. collide
    make them
    • Brute force
    • MITM
    • Equivalent substrings

    View Slide

  60. collide
    make them
    • Brute force
    • MITM
    • Equivalent substrings

    View Slide

  61. collide
    make them
    • Brute force
    • MITM
    • Equivalent substrings

    View Slide

  62. collide
    make them
    • Brute force
    • MITM
    • Equivalent substrings

    View Slide

  63. collide
    make them
    • Brute force
    • MITM
    • Equivalent substrings

    View Slide

  64. collide
    make them
    • Brute force
    • MITM
    • Equivalent substrings

    View Slide

  65. problem
    & that’s a

    View Slide

  66. problem
    & that’s a
    painful
    comparisons

    View Slide

  67. problem
    & that’s a
    painful
    comparisons
    ~700ms
    responses

    View Slide

  68. MANY fixes

    View Slide

  69. MANY fixes
    (but only one is right)

    View Slide

  70. MANY fixes
    (but only one is right)
    1. Limiting request size

    View Slide

  71. this is bad and you
    should feel bad!
    MANY fixes
    (but only one is right)
    1. Limiting request size

    View Slide

  72. MANY fixes
    (but only one is right)
    2. Changing the hash table

    View Slide

  73. MANY fixes
    (but only one is right)
    2. Changing the hash table
    (no comment)

    View Slide

  74. MANY fixes
    (but only one is right)
    3. Bring back the random

    View Slide

  75. View Slide

  76. “Randomness is
    too important
    to be left to
    chance”

    View Slide

  77. Thanks.
    “Randomness is
    too important
    to be left to
    chance”

    View Slide