TAOCP 4.6.3 Exercise 32
Working
Section 4.6.3: Evaluation of Powers
Exercise 32. [**] [M30] (A. C. Yao, F. F. Yao, R. L. Graham.) Associate the "cost" $a_j a_k$ with each step $a_i = a_j + a_k$ of an addition chain (1). Show that the left-to-right binary method yields a chain of minimum total cost, for all positive integers $n$.
Verified: no
Solve time: 6m12s
Working