Representing Sets with Minimal Space: Jamie's Trit
James Dow Allen · viXra · 2020
The theoretical minimum storage needed to represent a set of size N drawn from a universe of size M is about N·(log[sub]2[/sub](M/N) + 1.4472) bits (assuming neither N nor M/N is very small). I review the technique of `quotienting' which is used to approach this minimum, and look at the actual memory costs achieved by practical designs. Instead of somehow implementing and exploiting 1.4472 bits of steering information, most practical schemes use two bits (or more). In the conclusion I mention a scheme to reduce the overhead cost from two bits to a single trit.