Skip to content
Get started

Registers for an expression tree

A machine evaluates expressions using registers only: every variable must be loaded into a register before use, and an operation R_i = R_i op R_j overwrites one operand register and frees the other. Intermediate results may not be stored to memory. What is the minimum number of registers needed to evaluate x−(a+b)(c+d)(e−f)(g+h)x - \frac{(a+b)(c+d)}{(e-f)(g+h)} where each subexpression must be computed (no algebraic rewriting)?

Show hints (3)+
  1. Work bottom-up: how many registers does a subtree need given its two children's needs?
  2. Equal needs on both sides cost one extra register; unequal needs do not, if you start with the heavier side.
  3. Does it help to load xx first?

Answer

Reveal answer →

4

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions