14 ms·
For those wondering about that ~: https://en.wikipedia.org/wiki/Addition_chain https://en.wikipedia.org/wiki/Addition_chain: ”There is no known algorithm whic
by Someone 8y ago
For those wondering about that ~: https://en.wikipedia.org/wiki/Addition_chain https://en.wikipedia.org/wiki/Addition_chain:
”There is no known algorithm which can calculate a minimal addition chain for a given number with any guarantees of reasonable timing or small memory usage. However, several techniques to calculate relatively short chains exist. One very well known technique to calculate relatively short addition chains is the binary method, similar to exponentiation by squaring.”
- morei 8y agoThat's why I said "~ the minimum" :) In particular, it does at most the same number of multiplies as the LRU cache version in the OP