TIL succinct data structures - data stored in a compact fashion as in a compression, but the compact form itself has useful properties.

The Rank/Select Bit Vector is a bit vector equipped with two fast operations - rank and select. The rank operator returns the number of set bits up to the n-th bit. The select operator returns the index of the n-th set bit, i.e. inverse of rank. The data structure has nice uses as in string lookup, etc.

The Wavelet Matrix is a generalization of rank/select bit vector on non-binary symbols. Another data structure of the class is the FM-index, whose operators extend to working on patterns (substrings) instead of symbols.

How can a calculator program perform an exact calculation involving arithmetic operations, roots, trigonometric functions, etc? It's a difficult task. Here is how it can be done.

• rational type: bignum for both nom and denom
• recursive real arithmetic (RRA):
  • represent a real number as a computation that maps from a precision value (a rational) to the rational result etc.
  • for composite expression, compute the precision value needed for each of its components (e.g. for 2pi to be shown with a precision of 0.01, pi needs to be calculated to 0.005 precision)
• determine the exact equality between RRA
  • undecidable but decidable for a finite set of ops (proven by Dan Richardson, 1994), but slow
• the optimization
  • represent every number as an exact rational times a RRA. (e.g. (3/2)pi)
  • hard code the common types of RRA (sin, log, ..) whose identity can be checked directly.
  • for uncommon types of RRA, just store RRA (e.g. pi * sqrt(2))

the result: the digits shown on screen are always 100% correct. 99% of calculation gets perfect UX.