Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Would an optimizing compiler be able to understand these chains such that it would be a net gain on execution time?


I'm not certain I understand what's being asked. I'm going to assume you mean, "Could an optimizing compiler for a language with a built-in exponentiation operator use short addition chains to speed up exponentiation at runtime?" In which case, again, the answer depends on whether the exponent is fixed or is allowed to vary.

For a fixed exponent, certainly; you could just spend additional time in the compiler finding short addition chains for all the exponents that are used. When exponents are allowed to vary, then we're in the case I described in my post above -- maybe using the power-tree method, or certain other methods, would improve on the binary method; but finding the shortest addition chain at runtime would not. (By which I mean, not with existing methods, and it seems unlikely that there's any fast way.)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: