Skip to content

Instantly share code, notes, and snippets.

@loyd

loyd/approximations.md

Last active June 14, 2023 08:47
Show Gist options
  • Save loyd/8356f1de41008408c23e2c1b4aac4e40 to your computer and use it in GitHub Desktop.
Save loyd/8356f1de41008408c23e2c1b4aac4e40 to your computer and use it in GitHub Desktop.
Download ZIP
Useful approximations
Raw
approximations.md

Useful approximations

Just random approximations sometimes useful in work for "mental" calculation.

Bloom filter, space

b(p) ≈ 1.44 * log₂(p)
  • b — bits per element
  • p — false positive probability
p b
5.0% 6
2.0% 8
1.0% 10
0.5% 11
0.1% 14

More info.

Birthday problem

p(n, d) ≈ 1 - exp(-n² / 2d)
  • p — colision probability
  • n — number of elements
  • d — "days", space size

More info.

Little's law

Only for stable systems!

L = λ * W
  • L — long-term average number
  • λ — average arrival rate
  • W — average processing time

More info.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment