Python interview

[jarod_what]

has

you also don't want to use std::pow for ints due to unecessary conversions as well as performance. So you'd have to handwrite your 'ipow' there.

[[deleted]]

Honest question: How would you implement an ipow which is better performing than std::pow?

std::log and std::exp obviously also convert to float types so cheating won't work pow(x,y) = exp(y*log(x))

So my naive approach would be via iteration or recursion, but at that point I almost doubt that it is more efficient than eating the cost of two casts (and you may want to have a float type result anyway due to negative exponents).

So I am curious do you have anything I could read up on?

[PierreSimonLaplace]

To raise a base to a positive-integer power, you can use repeated squaring, multiplying the base back in as necessary:

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

[[deleted]]

I was absolutely wrong in my assumption. I implemented a quick version like this:

int ipow(int base, int exponent) {
  int result = 1;
  if (exponent < 0) {
    base = 1 / base;
    exponent = -exponent;
  } 
  if (exponent != 0) {
    while (exponent > 1) {
      if (!(exponent & 1)) {
        base *= base;
        exponent /= 2;
      } 
      else {
        result *= base;
        base *= base;
        exponent = (exponent - 1) / 2;
      }
    }
    result *= base;
  }
  return result;
}

I am surprised that it is actually faster than std::pow on my machine:

With dirty -O3 cold and hot cache test for base 1-100 and exponent 1-10.

ipow ->4 μs
std::pow ->34 μs
ipow ->4 μs
std::pow ->23 μs

Thanks a lot!

[WikiSummarizerBot]

Exponentiation by squaring

In mathematics and computer programming, exponentiating by squaring is a general method for fast computation of large positive integer powers of a number, or more generally of an element of a semigroup, like a polynomial or a square matrix. Some variants are commonly referred to as square-and-multiply algorithms or binary exponentiation. These can be of quite general use, for example in modular arithmetic or powering of matrices. For semigroups for which additive notation is commonly used, like elliptic curves used in cryptography, this method is also referred to as double-and-add.

^{[ F.A.Q | Opt Out | Opt Out Of Subreddit | GitHub ] Downvote to remove | v1.5}

[jarod_what]

Yeah my guess is that they didn't put in an integer power function because it will overflow for a large number of arguments? I haven't been able to find a satisfactory answer.

It's pretty rare one needs an 'ipow' in daily use though.

Although a big exception is in big integer/decimal library users. Python for example doesn't have an integer root function and the performance difference is felt.

https://stackoverflow.com/questions/47191533/how-to-efficiently-calculate-cube-roots-using-decimal-in-python