# Computer Scientists Invent an Efficient New Way to Count | Quanta Magazine

<https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/>

- Host: [quantamagazine.org](https://links.thingelstad.xyz/hosts/quantamagazine.org/)
- Saved: May 21, 2024 (2024-05-22T00:37:14Z)
- Record: https://links.thingelstad.xyz/links/2f27cbad66c4/
- JSON: https://links.thingelstad.xyz/links/2f27cbad66c4.json

## What Jamie wrote

Wow, this is a fun algorithm to get an approximation of the number of unique elements in a list. 

> Next, move to Round 2. Continue as in Round 1, only now we’ll make it harder to keep a word. When you come to a repeated word, flip the coin again. Tails, and you delete it, as before. But if it comes up heads, you’ll flip the coin a second time. Only keep the word if you get a second heads. Once you fill up the board, the round ends with another purge of about half the words, based on 100 coin tosses.

This is the kind of problem that programmers, particularly those working at scale, have to deal with fairly regularly. It seems easy "well, just count the things", but counting, particularly unique things, in a list that is billions or billions of billions long is very resource intensive. And often an approximate count is fine.

## Facts

- Kind: [Page](https://links.thingelstad.xyz/kinds/page/)

## Appears in

- [WT289: Weekly Thing 289 / Queueing, Counting, Mapping](https://weekly.thingelstad.com/archive/289/), Notable

## Same host

- [Algorithm Solves Graph Isomorphism in Record Time | Quanta Magazine](https://links.thingelstad.xyz/links/b430abca62b8/) (quantamagazine.org, March 17, 2016)
- [How Public Key Cryptography Really Works | Quanta Magazine](https://links.thingelstad.xyz/links/59cb63907087/) (quantamagazine.org, November 17, 2024)
- [How Does Graph Theory Shape Our World? | Quanta Magazine](https://links.thingelstad.xyz/links/5cfdfb90c3db/) (quantamagazine.org, July 6, 2025)

## Saved the same week

- [Interviewed: my creative process – On my Om](https://links.thingelstad.xyz/links/e966c36d3f34/) (om.co, May 21, 2024)
- [The History of Tetris World Records](https://links.thingelstad.xyz/links/3aacd57ff727/) (kottke.org, May 21, 2024)
- [Thinking out loud about 2nd-gen Email – Gabriel Sieben](https://links.thingelstad.xyz/links/7c689027aa02/) (gabrielsieben.tech, May 21, 2024)
- [“Unprecedented” Google Cloud event wipes out customer account and its backups | Ars Technica](https://links.thingelstad.xyz/links/c7aa3d4099b0/) (arstechnica.com, May 21, 2024)
- [The Ideal Email Folder Structure – The Sweet Setup](https://links.thingelstad.xyz/links/3bf1aaedadef/) (thesweetsetup.com, May 21, 2024)

## Elsewhere

- Wayback Machine: https://web.archive.org/web/*/https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/