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

It seems rather weird to use an explicit cache for the dynamic programming exponentiation.

When computing x^n, n is either even or odd. If it's even, then the result is (x^(n/2))^2, else it's odd and the result is x * (x^(n/2))^2. i.e.

  def pow(x, n):
    if x == 1:
      return x
    if (n & 1) == 1:
      return x * square(pow(x,n//2))
    else:
      return square(pow(x,n//2))
Does ~ the minimum number of multiplies, no LRU cache required.


For those wondering about that ~: 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.”


That'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




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

Search: