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
where each subexpression must be computed (no algebraic rewriting)?
Show hints (3)+
- Work bottom-up: how many registers does a subtree need given its two children's needs?
- Equal needs on both sides cost one extra register; unequal needs do not, if you start with the heavier side.
- Does it help to load first?
Answer
Reveal answer →Final answer
4
Create a free account to see the full worked solution and track your progress.
Interview format: Prop Trading