Implement a fast exponentiation function

Question

Mahdi · Accepted Answer

double recExp(b,p){
    if(p==1) return b;
    double t=recExp(b,int(p/2));
    return t*t*((p%2)?b:1);
}

KaiX · Answer

def expo(a, n):
    result = 1

    while (n != 0):
        if n % 2 == 1:
            result *= a

        a *= a
        n /= 2

    return result


This is a binary version. In calculating a to the b, it's easy to convert the number b into binary representation. It's also Log(N)

vkc · Answer

divide and conquer ?

Shane · Answer

long fast_pow_n(int x, int n)
{
  int temp_pow;
  if(n/2>=1)
  {
    (int) tem_pow=n/2;
    sub_result=fast_pow_n(x,temp_pow);
    temp_result=sub_result*sub_result;
    if(n%2==1)
      temp_result*=x;
    return temp_result;
  }
  else
  {
    return x;
  }
}

Google

Question d’entretien chez Google

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois